All questions with tag [math: computability]


Turing reduction

I'm finding out algorithm concept. Research inquiry is: Are $A$ and also $B$ feasible to make sure that $A\not\le_{tt}B$ (difficult to lower making use of tt), yet $A\le_T B$. Yet I can not consider any kind of instance.
2022-07-25 20:47:10

Projecting onto (lightface) Borel sets

Suppose $A \subseteq \omega^{\omega} \times \omega^{\omega}$ is Borel. If we project $A$ onto $\omega^\omega$, we get a $\mathbf{\Sigma^{1}_{1}}$ set $\{y: \exists x (y,x) \in A\}$. What if we project it via some Borel set $B\subseteq \omega^{\omega}$? I.e. is $\{y: (\exists x\in B) \; (y,x)\in A\}$ Borel? What about if $B$ is lightface Borel? I...
2022-07-25 15:51:35

is the language of Turing machine encodings context-sensitive?

Say we have an encoding of the set of all Turing machines/Turing programs - - WLOG, allow is claim the encoding takes values in the binary characters. Call this set of binary characters that stand for Turing Machines TM. TM will certainly be decidable as a part of all the binary characters, B, and also the getting of B obtains us a reliable lis...
2022-07-25 15:33:37

Creating ways to encode recursive function.

This is from a workout in Boolos' Computability message. My trouble is as follows: I am seeking a method that inscribe numbers for recursive features. After that offered such an encoding for recursive features by all-natural numbers, allow d (x) = 1 if the one - area recursive function with encoding number x is defined and also has value 0 for a...
2022-07-25 10:57:28

Proof of a Theorem in Gao's 'Invariant Descriptive Set Theory'

Theorem 1.7.5 on p.35 of Gao's Invariant Descriptive Set Theory reads Theorem 1.7.5 (Kleene) If $A\subseteq X \times \omega^{\omega}$ is $\Pi^{1}_{1}$ and $$x \in B \Longleftrightarrow \exists y \in \Delta^{1}_{1}(x)\; (x,y) \in A,$$ then $B$ is also $\Pi^{1}_{1}$. Here $X = \omega^{m} \times (\omega^\omega)^n$ for some $m$ and $n$ (or eq...
2022-07-25 10:53:27

Finding a total function not in a computable sequence of functions

Suppose $f(x,y)$ is a total computable function. For each $m$, let $g_m$ be the computable function given by $g_m(y) = f(m,y)$. Construct a total computable function h such that for each $m$, $h \not= g_m$. My work: Is this a really simple question where I can just use the diagonal method? Define $$ h(m,y) = \begin{cases} g_m(y)+1 & \...
2022-07-25 10:40:18

Equivalence of sequences and subsets of natural numbers

For me, facts like the independence of the continuum hypotheses from ZFC cast a doubt on the "law of the excluded middle". (In this context, the doubt is that there might be no "final set theory" such that every proposition about sets is either true or false.) Now I'm looking for simpler (mathematical) examples that are easie...
2022-07-25 10:38:56

Notation in Sacks' 'Higher Recursion Theory'

I'm having trouble with the notation in Sacks' Higher Recursion Theory. I've asked specific questions from page 4. Instead of reading my question in detail and trying to understand my confusion (which would be appreciated), one could probably just read the blockquotes below and tell me exactly what they're supposed to mean in "everyday"...
2022-07-24 09:38:12

there is no partial recursive function f s.t. whenever N-W_e has one element, f converges and N-W_e = f(e)

question is as written in the title: show that there is no partial recursive function f s.t. whenever N-W_e has one element, f converges and N-W_e = f(e). W_e is the domain of the program coded by e. So if there is a converging function f such that f(e) = N-W_e, how do I get a contradiction?
2022-07-24 09:19:36

Boolean Expression

If the syntax of a language is: $a ::= n | x | a_1 + a_2 | a_1 \star a_2 | a_1 - a_2 $ $b ::= true | false | a_1 = a_2 | a_1 \leq a_2 | ¬ b | b_1 \wedge b_2 $ As $x_1 > x_2 $ is not allowed in the language, what expression matching to this would certainly be allowed in the language? All I can consider is it can not be $ a_1 \leq a_2$, ...
2022-07-24 06:35:22

A homogeneous set of some kind

Let $f : \mathbb{N}^k \to \mathbb{N}$ be a computable total function such that $f (\vec{x}) > \max \vec{x}$ for all $\vec{x}$. Question. Why is there a decidable set $A$ such that $\operatorname{im} {\left. f \right|_{A^k}} = \mathbb{N} \setminus A$? It feels like there should be an inductive process which gives the solution. Let $A_0 =...
2022-07-24 06:29:24

Most computationally intensive algorithm.

I am trying to develop a benchmark to stress the CPUs on the Server for some HPC (High Performance computing) application. Please help me with some Algorithm that is believed to very CPU intensive. I saw algorithms to calculate primes using Newton's method - any better idea than this ?
2022-07-22 15:27:36

Solve equation on the PC

A close friend of mine asked me to aid him and also make a tiny application to address a trouble. This trouble can be lowered to this formula system: aX = Yb ; Y > c ; Y < d ; X is a number (X has absolutely nothing after.) ; Y * 10000 is a number (Y runs out after that 4 figures after.) ; eg. for a = 185.5 b = 1000000c = 4.3 d = 4.4 a r...
2022-07-21 09:03:01

A revisit to the question: Can total recursive functions be recursively enumerated?

There is not a clear answer in literature on the question: Can total computable functions be computable enumerated?, i.e., is a set of encodings of total computable functions computably enumerable (c.e.)? On the shaking ground, I am tossing an algorithm that encodes all total recursive functions and the set of codes is c.e.. Is the algorithm a f...
2022-07-21 09:02:02

A question on essentially undecidable first-order theories

I am trying to show the following equivalence: a (consistent) first-order theory $T$ is essentially undecidable if and only if every complete extension of $T$ is undecidable. By "$T$ is essentially undecidable" I mean that any consistent extension of $T$ is undecidable. So clearly the forward direction is obvious. So far, my idea for ...
2022-07-20 17:21:02

What philosophical consequence of Goedel's incompleteness theorems?

I intend to write a thoughtful essay focused concerning Goedel is incompleteness theory. Nonetheless I can not locate any kind of actual thoughtful effects that I can write majority a web page around. I read guides of Franzen (Incomplete overview of its usage and also misuse) and also Peter Smith (Introduction to Goedel is Theorems). I actually ...
2022-07-20 01:34:59

Recurrence relation for the digits of the integer square root in binary

I was exploring an inquiry on the Electrical Engineering Stack Exchange website, readily available below: In brief, the OP wants the opportunity of creating a digitial circuit which applies the integer square origin function making use of ju...
2022-07-17 17:17:07

Understanding of recursive functions

Computability is usually specified in regards to recursive functions, recursively enumerable collections, recursive collections. Is the factor behind this-- the following: a function that can be calculated is a recursive function-- ie. components of such function can be streamlined and also replaced, and afterwards once more streamlined, repla...
2022-07-17 17:16:37

Existence of recursively inseparable sets that are recursively enumerable

A set $A \subseteq \mathbb{N}$ is recursively enumerable if there exists a $\mu$-recursive function which enumerates it. Two sets $A, B \subseteq \mathbb{N}$ are recursively inseparable if there does not exists a set $C \subseteq \mathbb{N}$ such that $A \subseteq C$ and $B \cap C = \varnothing$. That is to say, any superset of $A$ will necessar...
2022-07-17 17:00:53

Proving Recursive Functions are Representable in R

I am trying to prove that all recursive functions are representable in the theory $R$ whose language is $L$ and whose theorems are the consequences in $L$ of the following infinitely many sentences: $\mathbf{i}\ne\mathbf{j}$ for all $i,j$ such that $i\ne j$ $\mathbf{i}+\mathbf{j}=\mathbf{k}$ for all $i,j,k$ such that $i+j=k$ $\mathbf{i}\cdot\ma...
2022-07-17 15:15:40