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)

17
votes
2answers
2k views

Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
7
votes
2answers
210 views

Complexity of the set of computable ordinals

According to http://en.wikipedia.org/wiki/Analytical_hierarchy The set of all natural numbers which are indices of computable ordinals is a $\Pi^1_1$ set which is not $\Sigma^1_1$. However, "the ...
1
vote
2answers
148 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
19
votes
4answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
3
votes
2answers
136 views

Upper and Lower bounds on proof length

Given a First Order language say, for arithmetic $\langle 0, 1, +,\cdot ,^\wedge, S \rangle$, Can one establish any lower or upper bounds on the length of proofs from certain recursively enumerable ...
2
votes
1answer
90 views

Puzzle: Generate the Highest Bounded Number Using a Limited Number of Characters

A friend and I were sitting in our cubes at work and trying to create the greatest bounded number we could using only a few characters. We came up with $A(G,G)$, which is the Ackermann function with ...
2
votes
1answer
89 views

One-reducibility extending to onto function

I'm working on the following problem from Soare: If $A$ is one-reducible to $B$ ($A \leq_1 B$) and $A, B$ c.e., $A$ infinite then $A$ is one-reducible to $B$ via some $f$ such that $f(A)=B$. I know ...
2
votes
1answer
128 views

Sipser's definition of a space constructable function

I have a problem with definition of space constructable function. As I understood we use this definition just for simplification of further proofs and idea behind this definition is very clear, but ...
2
votes
1answer
119 views

Looking for Wald Theorem

From the paper "What is a Random Sequence?" by Sergio B. Volchan, Math. Monthly 109, january 2002 Definition 3.1 An infinite binary sequence $x=x_1 x_2 \dots$ is random if it is collective; i.e., ...
3
votes
3answers
434 views

Proving that $\{x|\varphi_x \; \text{is extendible to a total computable function} \} \neq \omega$

The problem that I'm working on is to prove that $$ Ext=\{ x \ | \ \varphi_x \text{is extendible to a total computable function}\} $$ is not equal to $\omega$. Here $\varphi_x$ is the $x$-th partial ...
2
votes
2answers
143 views

Undecidable countable structure built on decidable relation?

My question is, is there a relation $R$ on the integers that's decidable (i.e. the function ${\mathbb Z}^2 \to \lbrace \text{true},\text{false} \rbrace, \ (i,j) \mapsto i R j$ is computable) , but ...
6
votes
7answers
722 views

Is there at least one irrational number with the property that it cannot be defined by a finite string of information?

Ok, so maybe that wasn't the best way of phrasing the question, but I think it's specific enough. Let me explain myself a bit more below in case I am wrong. So I'm assuming (although I've never ...
2
votes
0answers
215 views

Further question on “uncountable” Turing Machine

Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the ...
6
votes
3answers
306 views

Is the set of all deducible formulas decidable?

Consider any standard, "sufficiently expressive" first-order theory (say, $ZFC$ or Peano arithmetic) so that all the usual arithmetization and incompleteness results hold. The set $D$ of deducible ...
3
votes
3answers
471 views

Placing some sets in the arithmetic hierarchy

I'm working on the following problem: let $W_e$ be the computably enumerable set which is the domain of the $e$-th Turing program, and $K$ be the Halting problem, at which level of the arithmetic ...
3
votes
1answer
404 views

Understanding of pumping lemma

It seems like I missed something in pumping lemma. Please, help me out Let's take the simple example from Sipser's book Prove that language $L = \{0^n1^n | n>=0 \}$ is nonregular. Following the ...
24
votes
5answers
3k views

Are some real numbers “uncomputable”?

Is there an algorithm to calculate any real number. I mean given $a \in \mathbb{R}$ is there an algorithm to calculate $a$ at any degree of accuracy ? I read somewhere (I cannot find the paper) that ...
1
vote
3answers
249 views

Cardinality of the recursive subsets of the naturals

What is the cardinality of the set of recursive subsets of natural numbers?
3
votes
3answers
821 views

Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular? I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
8
votes
1answer
723 views

Recognizing and Using Chaitin's Constant

As far as I understand, Chaitin's constant is the probability that a given universal Turing machine will halt on a random program. I understand that Chaitin's constant is not computable--if it were, ...
3
votes
1answer
225 views

Decidability of equality of CFL's

Following problem is decidable: Given a context-free grammar $G$, is $L(G) = \varnothing$? Following problem is undecidable: Given a context-free grammar $G$, is $L(G) = A^{\ast}$? Is there a ...
6
votes
2answers
2k views

Question about the definition of “Prefix free”

I am trying to understand the definition of "Prefix free", but I do not understand the definition nor the example that wikipedia provides. I was hoping for clarification. Below is an excerpt from ...
7
votes
3answers
1k views

Prove Gödel's incompleteness theorem using halting problem

How can you prove Gödel's incompleteness theorem from the halting problem? Is it really possible to prove the full theorem? If so, what are the differences between original proof and proof by ...
4
votes
4answers
514 views

How many cpus needed to check a 100 million digit prime number efficiently?

If I had access to potentially large number of CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the ...
5
votes
2answers
404 views

Does every infinite $\Sigma^1_1$ set have an infinite $\Delta^1_1$ subset?

The question is exactly that in the title: Does every infinite $\Sigma^1_1$ set of natural numbers have an infinite $\Delta^1_1$ subset? Some background: The lower-level analog of this question, Does ...
1
vote
3answers
396 views

How is Kleene's T predicate defined?

What I don't understand is how to extract information from the number that encode the computation history. I know it's defined in Kleene's Introduction to Metamathematics. But what page? References ...
12
votes
2answers
2k views

Can someone explain the Y Combinator?

The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in ...
3
votes
2answers
465 views

Algorithm to determine if a Diophantine Equation has an infinite number of solutions

In their paper , Marker and Slaman, proved the decidability of the the theory of the natural numbers with the quantifier "for all but finitely many", One can obviously encode the question of whether ...
2
votes
1answer
160 views

bijective projection N <-> algorithms

I thought I'd might be interesting to do some "automated algorithm/turing-automata finding" (I had the busy beaver in mind). I thought about trying many in a specific language (brainfuck or smallfuck) ...
4
votes
1answer
131 views

A technique for deciding satisfiability in fragments of first-order logic

By Goedels completeness theorem satisfiability in first-order logic is $\Pi_1$. So to obtain decidability in some fragment, it is enough to show that satisfiability is $\Sigma_1$ in this fragment. I ...
2
votes
1answer
170 views

If $f$ is primitive recursive (but not necessarily bijective) and $M$ primitive recursive, is $f(M)$ primitive recursive?

In this post I wondered, whether a language over a finite alphabet is “stable” with respect to primitive recursiveness, recursiveness and recursive enumerability under different enumerations of the ...
1
vote
2answers
277 views

What is the importance of mentioning —U? (Turing 1936)

I'm trying to get my head around page 252 of Turing's "On Computable Numbers [...]", specifically near the end of the page where he talks about -U (logical negation of U, the German blackletter U). ...
3
votes
1answer
1k views

Proof that the set of incompressible strings is undecidable

I would like to see a proof or a sketch of a proof that the set of incompressible strings is undecidable. Definition: Let x be a string, we say that x is c-compressible if K(x) $\leq$ |x|-c. If x is ...
2
votes
3answers
180 views

A notion of topology for computability

A topology on a space $X$ is defined as a subset of the power-set of X, that is closed under arbitrary unions, finite intersections and includes the empty set and the full space. Is anybody aware of ...
4
votes
2answers
493 views

An “uncountable” Turing Machine?

A proof of the insolubility of the halting problem is a diagonalization, which I'm sure most of you have seen. I am not very familiar with set theory, but it strikes me as similar to Cantor's proof of ...
3
votes
1answer
507 views

Questions about the proof that minimal Turing machines are not recursively enumerable & proof that Kolmogorov complexity is uncomputable

This thread can be broken up into two questions. First I am trying to understand the proof that $MIN_{TM}$ is not recursively enumerable. If M is a Turing machine, then we say that the length of ...
-3
votes
2answers
1k views

Example of function which is not computable

I am looking for a concrete example of a function $$f: N^k \rightarrow N$$ $$(n_1, n_2, \cdots n_k) \mapsto f(n_1, n_2, \cdots n_k)$$ which is not computable. Source: Computability, An introduction ...
3
votes
3answers
113 views

Why isn't it enough to enforce $w \in A \Rightarrow f(w) \in B$ before allowing a reduction from A to B?

From my textbook, I can see that A language A is mapping reducible to language B if there is a computable function such that for every $w$, $w \in A \Leftrightarrow f(w) \in B$. Now, what I fail to ...
3
votes
2answers
126 views

Slick way to define p.c. $f$ so that $f(e) \in W_{e}$

Is there a slick way to define a partial computable function $f$ so that $f(e) \in W_{e}$ whenever $W_{e} \neq \emptyset$? (Here $W_{e}$ denotes the $e^{\text{th}}$ c.e. set.) My only solution is to ...
6
votes
1answer
1k views

Easy proofs of the undecidability of Wang's tiling problem?

Wang tiles are (by Wikipedia): "equal-sized squares with a color on each edge which can be arranged side by side (on a regular square grid) so that abutting edges of adjacent tiles have the same ...
2
votes
1answer
188 views

Construction of a sequence of theorems with increasing and unbounded “difficulty”?

Let's define the "difficulty" of a theorem as the logarithm of the size of its shortest proof divided by the logarithm of the size of the theorem itself. For example, if a theorem has difficulty less ...
5
votes
3answers
227 views

Recursive function that outputs its own code

This problem is probably a rather trivial one, since I have the impression, that it is a textbook-style one, but nonetheless somehow it won't give in. Here it is: I have to show that there exists a ...
3
votes
4answers
3k views

Example of a not recursively enumerable set $A \subseteq \mathbb{N}$

Can someone give me an example if a not recursively enumerable set $A \subseteq \mathbb{N}$ ? I came up with this question, when trying to show, that there exist partial functions $f: \mathbb{N} ...
0
votes
1answer
257 views

The busy beaver grows fast!

If $\Sigma$ denotes the busy beaver function, how can I then show, that there is an $t\in \mathbb{N}$ such that for all $x\geqslant t$ we have $\Sigma(x)>f(x)$, where $f$ is an arbitrary partial ...
1
vote
3answers
228 views

Algorithm to tell if a partial recursive function is 0 everywhere

Is there a (partial) recursive function that tells me, if a partial recursive function encoded by the number $c$ is the constant zero function ?
0
votes
1answer
171 views

Question about the “source code” of a recursive function

How can I show, that for every recursive function $f: \mathbb{N} \rightarrow \mathbb{N}$ we have a number (source code) $c$ such that $\forall x \in \mathbb{N}: f_U (c,x)=f_U (f(c),x)$, where $f_U: ...
3
votes
1answer
204 views

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive?

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive ? I'm not particularly interested in a detailed proof or counterexample, just a quick argument why this affirmation should ...
3
votes
3answers
1k views

To Prove an undecidable language on halting

I am student learning Computational Complexity this semester. The text book is Sanjeev Arora et al. Computational Complexity, Cambridge University Press. I cannot solve the first problem in Chapter ...
3
votes
2answers
872 views

How can I prove that this set is recursively enumerable?

Let $g _c (x)$ be the output of a program that is encoded by $c \in \mathbb{N}$ for the given input $x$. $g_c$ can obviously be undefined, in case the program encoded by $c$ doesn't halt. If we define ...
2
votes
1answer
144 views

Weaker definition of recursively enumerable sets

If I understand a set to be recursively enumerable, if it is a projection of a recursive set, meaning it is a set of the form $\left\{ (x_1, \dots,x_{l-1}) |\exists x_l: (x_1, \dots,x_{l-1},x_l) \in ...