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)

5
votes
1answer
49 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
53 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
105 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 ...
0
votes
1answer
20 views

Show that a language is not turing decidable. [closed]

Hello I have this problem: A = {[M] : M is a TM and M accepts k-strings}. To show that it is not Turing decidable I should reduce A_TM to A. So I need to build a ...
2
votes
1answer
26 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. ...
1
vote
0answers
35 views
+250

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
18 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
66 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
195 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
31 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: ...
3
votes
1answer
33 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
50 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
34 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 ...
2
votes
1answer
25 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
30 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
8 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
95 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 ...
0
votes
1answer
53 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 ...
1
vote
0answers
30 views

Proving Richardson's theorem for constants

Richardson's theorem is given in this wikipedia article. $\:$ In this answer, Eric Towers states that An algebraic expression is decidable. This is also the Tarski-Seidenberg theorem. ...
1
vote
1answer
32 views

Is PA+ TM doesnt halts consistent?

Suppose there isnt a proof in PA whether some TM halts or not. Suppose further that TM doesnt halt and PA is consistent. Is PA+TM halts necesserely consistent? Is PA+TM doesnt halt necesserely ...
3
votes
1answer
868 views

Halting problem is solvable

When we say "the halting problem isn't solvable", to what type of axioms/logic system are we referring to? Otherwise we could have an infinite set of axioms, each one saying whether a given Turing ...
6
votes
1answer
230 views

$F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$

Consider the ring $F[t, t^{-1}]$ (the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$). Theorem 1. Assume that the characteristic of $F$ is zero. Then the existential theory ...
9
votes
1answer
380 views

Algorithm to answer existential questions - Reduction

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
6
votes
1answer
111 views

FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number? One could use Gödel encoding to translate FRACTRAN ...
4
votes
1answer
141 views

The existential theory is undecidable

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
1
vote
1answer
43 views

Proof of a classical Theorem of Martin-Löf on complexity dips for Kolmogorov complexity,

I have a question on the first Theorem from the article Complexity of Oscillations in Infinite Binary Sequences by P. Martin-Löf, which could be downloaded from the publisher or from here. Theorem ...
2
votes
1answer
36 views

Intuition on Martin-Löf-Test for finite strings

The followng example is from An Introduction to Kolmogorov Complexity and Its Applications, Example 2.4.1. and is concerned with Martin-Löf-Tests for finite strings: A string $x_1 x_2 \ldots x_n$ ...
1
vote
1answer
29 views

Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity

Denote by $C(n)$ the plain Kolmogorov complexity of $n$ and the length of a binary encoding of $n$ by $l(n)$, why do we have $$ C(n\mid l(n)) \ge C(n) - C(l(n))? $$ If I have a shortest program $p$ ...
1
vote
0answers
13 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all ...
2
votes
0answers
15 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the ...
3
votes
0answers
42 views

Induction Can't Prove Complexity?

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 ...
1
vote
0answers
31 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
11
votes
1answer
141 views

Every non-increasing sequence of polynomial towers stabilizes — Finitary proof

In this question we are concerned only with positive integers $\mathbb N$ and other finitary objects that can be encoded using integers. A term function means a total computable function $\mathbb ...
1
vote
0answers
26 views

Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often

In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written: The key point is not that the universal description method ...
2
votes
1answer
24 views

Relationship between computability and growth rate

Let $f:{\mathbb N}\to{\mathbb N}$ be an arbitrary function. Is there always a computable function $g:{\mathbb N}\to{\mathbb N}$ such that $g \geq f$ (i.e. $g(n)\geq f(n)$ for every $n$) ? The answer ...
9
votes
1answer
120 views

Non-computable function having computable values on a dense set of computable arguments

A rational complex number is a complex number whose both real and imaginary parts are rational numbers. Note that a rational complex number is a finitary object that can be an input or an output of an ...
2
votes
0answers
31 views

Decidability - Complexity

Can someone tell me where I can get some information about the following? We have linear differential equations with polynomial coefficients depending on x. $a_n(x)y^{(n)}+ \dots ...
0
votes
1answer
42 views

Values of the Sudan function

I am talking about the first discovered recursive function which is not primitive recursive. I would like to know the exact values of $\ f(3,3,3), f(2,0,4), f(2,7,1), f(2,3,2)$ (where $f$ is the ...
4
votes
5answers
145 views

Where does this argument showing there are uncountably many TMs fail?

This argument comes up once every while on Lambda the Ultimate. I want to know where the flaw is. Take a countable number of TMs all generating different bitstreams. Construct a Cantor TM which runs ...
0
votes
2answers
28 views

Rice's Theorem when only finite number of instructions run

Rice's theorem says that there is no computable method F(m,p) to determine, if given as input a TM m, and some non-trival property p, if the language accepted by m has property p. To quote another ...
0
votes
1answer
32 views

Hardness of index sets for computable structures

Suppose we have a computable structure $M$ and we want to show that its index set $I(M)$ is (many-one) $\Gamma$-hard for some complexity class $\Gamma$ (like $\Sigma^0_2$). To do this, we need to show ...
3
votes
0answers
100 views

What does “Turing-complete” really mean?

People talk about various programming languages or computational models being "Turing-complete." But what does that technically mean? The technical definition is buried under tons of informal ...
2
votes
1answer
38 views

Why is $f(x)=x^{2}+1$ a primitive recursive function?

I'm trying to find out why $f:\mathbb{N}\rightarrow\mathbb{N},f(x)=x^{2}+1$ is a primitive recursive function. For $f(S(y))$ I can't seem to get it to fit the axioms known to me about primitive ...
6
votes
0answers
56 views

Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter). I have ...
2
votes
1answer
63 views

Does semantic inconsistency guarantee syntactic inconsistency?

I'm wondering about the possibility of circumventing the problem of incompleteness posed by Roger Penrose in his book "Shadows of the Mind". It occurred to me (and, Googling has revealed to me, ...
0
votes
0answers
9 views

Generalizing equal turing machine problem

I know that $EQ_{TM} = \{<M_1,M_2> | L(M_1)=L(M_2)\} \notin RE \cup CO-RE$ Can I generalize and say that $L' = \{<M> | L(M) = C \} \notin RE \cup CO-RE$ Where C is the language of any ...
0
votes
0answers
10 views

Turing Machine Membership problem and how to prove its undecidable

ATM = {$<m, w>$ | M is a Turing Machine that accepts string w}. How can I prove that ATM is undecidable? Here's what I have so far: Any decidable problem is accepted by a Turing Machine. It ...
0
votes
0answers
13 views

Question about the effect of the basic primitive recursive projection function.

Projections are said to allow us to use "any argument in any order", and the function below can be proved to be a PR function by projections and the composition rule. Let $ i_0,\cdots,i_{m-1} \in n = ...
1
vote
1answer
57 views

What is the meaning of 'recursive' in Boolos, Burgess and Jeffreys? (Computability and Logic)

In the book Computability and Logic by Boolos, Burgess and Jeffrey (page 71 - 5th edition) it defines a recursive function as follows: The functions that can be obtained from the basic functions ...