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)

3
votes
2answers
115 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
15 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
93 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
100 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
36 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
172 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: http://mathoverflow.net/questions/...
0
votes
1answer
113 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
64 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 $Q$...
1
vote
1answer
37 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
45 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
89 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 $\beta(x_1,\...
2
votes
1answer
66 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
356 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
47 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
133 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
245 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
209 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
79 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 if,...
0
votes
2answers
74 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 $\mathbb{Z}T]...
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
47 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
71 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 $c....
3
votes
1answer
41 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
30 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
137 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
75 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 ...
2
votes
1answer
95 views

Proving Richardson's theorem for constants

(I also asked this 18 hours ago on mathoverflow, but did not yet get any responses there.) Richardson's theorem is given in this wikipedia article. $\:$ In this answer, Eric Towers states that ...
1
vote
1answer
48 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
902 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 ...
8
votes
1answer
385 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
450 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 $t-...
6
votes
1answer
149 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
229 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 $t-...
1
vote
1answer
49 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
37 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
16 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
20 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 string. ...