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)

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
427 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
138 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
707 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
211 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
303 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
452 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
400 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
2k 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
240 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
807 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
683 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
224 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
1k 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
458 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
401 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
378 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 ...
10
votes
2answers
1k 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
456 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
155 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
129 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
169 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
275 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
177 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
478 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
486 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 ...
5
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
185 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
226 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 ...
2
votes
4answers
2k 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
252 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
223 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
197 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
850 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
143 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 ...
2
votes
1answer
151 views

Recursive set that contains in a way all the other recursive ones?

I am wondering, whether there a exists a recursive set $S\subseteq \mathbb{N}^2$, such that for every recursive set $T \subseteq \mathbb{N} \ \exists c \in \mathbb{N}: \ T=\left\{n \in \mathbb{N }| ...
3
votes
3answers
184 views

Why can't we diagonalize out, if we deal with partial functions?

We know, that all (partial) recursive functions are countable (since one can for example interpret them as some simple programs; and the set of those programs are themselves countable), so one can try ...
2
votes
2answers
184 views

How do we know that there is a function from $\mathbb{N}$ to $\mathbb{N}$ that is not partial computable?

A partial computable function is also known as effectively computable, and is defined as any function that can be computed by a Turing machine with $Dom(f) \subseteq \Sigma^*$, where $\Sigma^*$ is the ...
1
vote
2answers
281 views

Concerning the countability of the set of primitive recursive functions

If we generally would define the smallest set, that has to have some properties, as the set obtained by intersecting all the sets that have those properties (if the intersection is non-empty) and the ...
5
votes
1answer
228 views

What is the power of a recursive language vs. that of one that is recursively enumerable?

I am simply wondering, as the title states, what the central differences are between recursive and recursively enumerable languages? If I am not mistaken a recursive language is a is Turing decidable ...
0
votes
3answers
201 views

Why are the primitive recursive functions a subset of the recursive ones?

I am trying to show, that the set $PR$ of primitive recursive functions is a subset of $R$, the recursive functions. Could someone help me, complete the proof of that assertion ? My idea: Since $PR$ ...
1
vote
2answers
186 views

Why is the set of primitive recursive functions well defined?

The set of primitive recursive functions is defined as the smallest subset $F\subseteq \cup _{k\in \mathbb{N}} \{f:\mathbb{N}^k \rightarrow \mathbb{N}\}$, satisfying the properties 1) $F$ contains ...
8
votes
4answers
492 views

Consequences of solving the Halting problem

What impact would a device (ie super-computer or relativistic computer or other method) that solves the halting problem have on math? Would there be any mathematical problems left to solve? What ...