Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

learn more… | top users | synonyms (1)

0
votes
0answers
21 views

Incomparable hyperdegrees in $\Delta^1_2$, where one of the two is given

In classical recursion theory, given a set $x \le_T 0'$, one can construct a set $y \le_T 0'$ such that $x$ and $y$ are incomparable. Is the following analogous statement in hyperarithmetical theory ...
3
votes
1answer
80 views

$\Pi^1_1$ singletons and $\Delta^1_2$ wellorders on $\omega$ in $L$

I have been trying to show the supremum $\delta^1_2$ of ordinals that are $\Delta^1_2$ wellorders on $\omega$ is exactly equal to the least ordinal $\delta$ such that $L_\delta$ contain all $\Pi^1_1$ ...
1
vote
0answers
30 views

Having trouble with the basic interpretation of “s-m-n theorem”

enter image description here This is the definition, the issue is, I still don't understand the basics. Here is my interpretation. If we have a computable function f(x,y), we can assign all the ...
2
votes
1answer
57 views

Recursive function $f$ with $\operatorname{range}(f) = \{x\mid \phi_{x}\text{ is total}\}$ [closed]

I don't understand how the proof for this exercise (and this kind of exercises in general) holds: There is no recursive function $f$ with $\operatorname{range}(f) = \{x\mid \phi_{x}\text{ is ...
2
votes
3answers
110 views

Why are all finite sets recursive?

Obviously a finite set for which the members are explicitly given or for which a computable rule is available will be recursive. (By which I mean its characteristic function is computable.) However, ...
0
votes
0answers
143 views

Language decidable separates two disjoint co-Turing recognizable languages

Hello this is the problem: Let A and B be two disjoint languages. Say that language C separates A and B if A in C and B in (not C). Show that any two disjoint co-Turing-recognizable languages are ...
0
votes
1answer
35 views

What does it mean to prove a problem cannot be solved by a Turing machine?

You sometimes see claims that no Turing machine exists which solves a particular problem, for example, no Turing machine exists which, given an arithmetic statement, outputs correctly either "true" or ...
2
votes
1answer
55 views

Are there decidable problems which aren't in $NP$?

I'm currently attending a course introducing the basic notions of algorithms, complexity, decidability etc. My question is: Is there a decidable problem $A$ which isn't in $NP$, i.e. it is always ...
2
votes
1answer
71 views

Corollary of Kleene's recursion theorem - can we find a constructive proof?

It is not a homework assignment, rather it is a question arising from teaching myself. In a lecture note by Weber, following statement gives as a corollary of Kleene's recursion theorem: For ...
1
vote
0answers
58 views

How to prove a programming language is not Turing complete?

How does one prove that a programming language is not Turing complete? I know one may attempt to show that every program that could be written in the programming language in question is primitive ...
1
vote
0answers
16 views

A preordered set related to realisability logic

Let $\Lambda$ be any partial combinatory algebra. For each set $X$, define a binary relation on $\mathscr{P} (\Lambda)^X$ as follows: Given $P, Q : X \to \mathscr{P} (\Lambda)$, $P \le_X Q$ iff ...
1
vote
2answers
30 views

If a c.e. set $X$ is such that every $\Sigma^0_2$ set is c.e. in $X$, then $X \equiv 0'$

Is it true that if a c.e. set $X$ (of naturals) is such that every $\Sigma^0_2$ set $Y$ is c.e. in $X$, then $X \equiv 0'$? An obvious and naive trial to prove this would be to take $Y := 0''$. ...
3
votes
2answers
107 views

Proofs about theorem-provers in ZFC, in ZFC

Is the following statement provable in ZFC for some $A$: "$A$ is an algorithm which, when given as input a proposition $p$ in the language of ZFC, outputs 'yes' only if $p$ is provable in ZFC, 'no' ...
1
vote
1answer
21 views

Is there a typical amount of clauses (in a 3CNF SAT expression)? Do SAT solvers regularlary solve expressions (or attempt to) with many?

I'm curious as to in what settings we would be interested in finding out whether a boolean expression in 3CNF with a large number of clauses is satisfiable (I''m not sure how "large number" is defined ...
1
vote
1answer
14 views

Does any non-admissible numbering form a PCA?

Given a numbering $\varphi_0, \varphi_1, \dotsc$ of the unary partial recursive functions, define a PAS as $\mathbb N$ with application $x \cdot y \simeq \varphi_x(y)$. If the numbering is admissible ...
4
votes
1answer
87 views

Markov's paper on insolubility of the homeorphy problem

I am looking for an English translation of Markov's 1958 paper, On insolubility of the homeorphy problem, which I remember coming across on a website for a computational topology course (taught by ...
2
votes
1answer
88 views

Is there a way to decide whether a differential equation is solvable or not?

Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson had negatively settled Hilbert 10th problem, I wonder if there is an analog result to the differential equations ?
2
votes
1answer
96 views

Parity of TREE(3)?

The number TREE(3) is somewhat famous for being incomprehensible big. But since it's just a finite number it must have a parity. Is the parity of TREE(3) known?
1
vote
1answer
32 views

Recursive languages , please check whether my explain is correct?

Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows. $$L = \begin{cases} (0+1)^* & \text{if } P = NP \\ \phi & \text{otherwise} \end{cases}$$ Which of the following ...
6
votes
0answers
170 views

Anti-random reals

EDIT: This has now been crossposted at MO: http://mathoverflow.net/questions/219366/antirandom-reals. This is partially motivated by my question at mathoverflow: ...
0
votes
1answer
105 views

enumerability exercise in boolos book

problem 2.2 of Computability and Logic written by Boolos(p.20, fifth edition) Show that if for some or all of the finite strings from a given finite or enumerable alphabet we associate to the string ...
0
votes
1answer
60 views

Proving finite-automata transition function for string concatenation

I'm having a few problems with this proof and I'm not sure where to start. In our class, a Deterministic Finite Automata, or DFA, is defined as a 5-tuple $$M = (Q,\Sigma,\delta, q_0, F) $$ Where ...
1
vote
1answer
36 views

Let $G(x,y)=2^x(2y+1)-1$ and show that $G$ is computable

Show that $G$ is a computable bijection and that the functions $G(G_1(z))$,$G_2(z))=z$ for all $z$ is computable. To show that it is computable, do we show that the above function $G$ is primitive ...
4
votes
0answers
72 views

Show undecidability by reducing from Hilbert's $10^{th}$ problem

To show that the existential theory of $\mathbb{Z}$ in the language $\{0, 1; +, \mid , \mid_p\}$ (where $x \mid_p y \Leftrightarrow \exists r \in \mathbb{N} : y=\pm xp^r$) is undecidable we have to ...
0
votes
2answers
76 views

Is the reduction correct?

Is the following formulation of the reduction correct? EDIT: Undecidability of an (positive) existential theory $T$ is proved often by reducing an other (positive) existential theory $T'$, which ...
2
votes
1answer
42 views

How to define $x \in \mathbb N$ in the reals

I just learned today about Tarski Seidenberg theorem which implies the decidability of the reals (only with the field operations). I also know about Gödel incompleteness theorem, which implies that ...
1
vote
1answer
85 views

Existential theory

We have that a formula $\alpha(x_1,x_2,\dots, x_k)$ is existential if it is of the form $$\exists t_1\exists t_2\cdots \exists t_l\beta(x_1,\dots,x_k, t_1,\dots,t_l)$$ where the formula ...
2
votes
1answer
63 views

What is a recursive measure?

About halfway through "A frequentist understanding of sets of measures" by Fierens, Rêgo, and Fine (pdf available here) I encountered the claim that "there is a recursive probability measure such that ...
10
votes
4answers
343 views

Countable choice and term extraction

The constructive Axiom of Countable Choice (ACC) is widely accepted due to its computational content. It states that: $$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: ...
6
votes
1answer
154 views

Simplify these “basis functions” for universal computation?

Background: The following three functions (which map naturals to naturals) form a "complete basis" for universal computation, in the sense that any Turing machine can be simulated by iterating some ...
-2
votes
1answer
45 views

$f^{-1}(S)$ of a recursively enumerable set [closed]

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a computable function and let $S \subseteq \mathbb{N}$ be recursively enumerable. How does one show that the inverse image $f^{-1}(S)$ is also recursively ...
1
vote
0answers
44 views

Does this method show that the projections $K$ and $L$ of an enumeration are primitive recursive?

In the fifth edition of Boolos et al's Computability and Logic, Exercise 6.5 asks the following (modified to provide background definitions): Define $K(n)$ and $L(n)$ to be the first and second ...
5
votes
1answer
132 views

From Primitive Recursive to Recursive by Iterating over more than one Argument?

Is the only way a function can be recursive and not primitive recursive by growing faster than primitive recursion allows (as with Ackerman's function)? If so, then consider the following. Primitive ...
0
votes
1answer
223 views

What is meant by “finite algorithm” in Turing's definition of the computable numbers?

In a comment thread on SlateStarCodex, I made a philosophical point the "realness" of the reals, in the process of which I attempted to summarize the definition of Turing-computable numbers: ...
1
vote
2answers
203 views

How does Turing's thesis imply the existence of a universal Turing machine?

In the fifth edition of Boolos et al's Computability and Logic, Exercise 4.5 asks the following: A universal Turing machine is a Turing machine $U$ such that for any other Turing machine $M_n$ and ...
1
vote
1answer
38 views

Show that there is such an algorithm

Let $L_P = \{+, \geq; 0, 1\} $. The first-order theory of $\mathbb{N}$ in the language $L = L_P \cup \{exp_2\}$, where $exp_2$ the function which sends a natural number $n$ to $2^n$, is decidable. ...
2
votes
0answers
78 views

Injury-free proof of Cof being $\Sigma^0_3$-complete

How can I prove, without using priority argument, that Cof, the set of indices of cofinite c.e. sets, is $\Sigma^0_3$-complete? I know an injury-free proof of Rec being $\Sigma^0_3$-complete, where ...
3
votes
1answer
26 views

Let $\Gamma$ be a $\kappa$-based monotone operator where $\kappa$ is regular. Then the closure ordinal of $\Gamma$ is $\kappa$.

A monotone operator $\Gamma: \mathcal{P}(A) \to \mathcal{P}(A)$ is an operator such that, if $X \subseteq Y \subseteq A$, then $\Gamma(X) \subseteq \Gamma(Y)$. A monotone operator is $\kappa$-based ...
0
votes
2answers
72 views

Decidability of certain first-order statements

Is it possible to construct an algorithm that can formally prove any statement in some countable first-order theory except for exactly those which aren't provable in the theory? Why or why not? Edit: ...
0
votes
1answer
51 views

Why does this equivalence stand?

I am reading the proof of the following theorem: THEOREM A. Let $R$ be an integral domain of characteristic zero; then the diophantine problem for $R[T]$ with coefficients in ...
2
votes
2answers
202 views

Why is there a $p\in \mathbb{N}$ such that $mr - p < \frac{1}{10}$?

I am reading the following part of the paper of Denef : Let $R$ be a commutative ring with unity and let $D(x_1,\dots , x_n)$ be a relation in $R$. We say that $D (x_1,\dots , x_n)$ is diophantine ...
1
vote
1answer
35 views

Proof involving recursive enumerability

Consider the set $S = \{x : \phi^1_x(x) \ \ \text{is undefined/does not converge\} }$ This is supposed to be a set that is not recursively enumerable. How do we prove this? My thoughts so far: ...
4
votes
1answer
45 views

Total Turing reducibility

For $x, y\in 2^\omega$, say $x$ is totally reducible to $y$ - and write "$x\le_{Tot}y$" - if there is some Turing machine $\Phi_e$ which is total on every oracle (that is, $\Phi_e^z$ is total for all ...
4
votes
1answer
68 views

Do proof assistants like Coq really need to actually perform computations to prove n <= m, or is there a more optimal algorithm?

For example, trying to prove that 100,000 <= 1,000,000. But Coq has a stack overflow, meaning it's actually trying to perform the 100k computations. ...
1
vote
1answer
59 views

Computably enumerable closed under inverse image

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a computable function and let $A \subseteq \mathbb{N}$ be computably enumerable. I'm trying to find a reason why the inverse image $f^{-1}(A)$ is also ...
3
votes
1answer
40 views

Problem with Soare's book on re sets.

On page 16 of his "RE sets and degrees" he introduces the notion of a (Turing) computable function indexed by e with input x and output y taking fewer than s steps to complete, WHERE s has to be ...
2
votes
1answer
34 views

The diophantine problem for $R[T]$ is solvable iff the diophantine problem for $R$ is solvable

One part of the paper that I am reading is the following: Let $R$ be a commutative ring with unity and let $R'$ be a subring of $R$. We say that the diophantine problem for $R$ with coefficients ...
0
votes
0answers
27 views

FPT algorithm equivalent definitions

On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover. But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ ...
5
votes
2answers
130 views

Is there a turing machine for which halting is equivalent to the Axiom of Choice or its negation?

As seen in "A Turing machine for which halting is outside ZFC", Gödel's incompletness theorem can that there a turing machines for which halting can not be decided. My question is, is there a turing ...
-1
votes
2answers
74 views

Can Incompleteness be Computable?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...