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
163 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
169 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
423 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
428 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 ...
-2
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
112 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
183 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
220 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
243 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
212 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
168 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
185 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
746 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
138 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
149 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
181 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
177 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
233 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
221 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
190 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
179 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
464 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 ...
10
votes
4answers
621 views

What is undecidability

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will ...
1
vote
1answer
201 views

Does this number exist?

Consider the finite algorithm A, and the real number $0<T<1$. The output of A on input T is all possible theorems and provable propositions in ZFC, and only that. Q1. Can such an algorithm and ...
3
votes
3answers
450 views

Growth rate of primitive and $\mu$-recursive functions

Functions that are not primitive recursive but $\mu$-recursive are said to grow too fast to be primitive recursive. Are there functions $f$ and $F$ such that a function is primitive recursive ...
15
votes
5answers
2k views

Is it possible to solve any Euclidean geometry problem using a computer?

By "problem", I mean a high-school type geometry problem. If no, is there other set of axioms that allows that? If yes, are there any software that does that? I did a search, but was not able to ...
4
votes
2answers
799 views

Is this function a primitive recursive function?

Let $t \in \mathbb{N}$ and consider the function $f: \mathbb{N} \rightarrow \mathbb{N}$, defined by $f_t (m)= 2 \uparrow^{m} t$, where "$\uparrow$" is Knuth's up-arrow notation (which can be ...
3
votes
5answers
495 views

Recursion theory text, alternative to Soare

I want/need to learn some recursion theory, roughly equivalent to parts A and B of Soare's text. This covers "basic graduate material", up to Post's problem, oracle constructions, and the finite ...
2
votes
2answers
185 views

Recognizable or not?

This is related to a homework question for a class that I am TAing for. I'm using Sipser terminology here (recognizable for computably enumerable, decidable for computable). Given that $w^r$ is the ...
8
votes
1answer
9k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
5
votes
3answers
204 views

Approachable = provably approachable?

Question: Let’s call a real number $x$ approachable if there exists a Turing machine $M$ such that $M(1), M(2),\dots$ is a sequence than converge to $x$. If we can prove (edit: In ZFC) that the ...
3
votes
1answer
168 views

Reducing the complexity of a turing machine algorithm

i'm trying to solve this question: Given a turing machine that is decidable by at most 50 * n^4 steps, can we build a dif algorithm that can decide it in n^4 steps? Me and my friends thought about ...
3
votes
1answer
669 views

Turing machine configuration and computation history

These are a series of questions about Turing machines. First, are the number of a given Turing machine configurations (state + tape) countable? Secondly, given that a computation history is a ...
2
votes
1answer
123 views

Graph enumeration problems which admit recursive solutions

This is an attempt to refine my previous question into something precise enough to admit a resolution. Let $P\;$ be a graph property, let $T_n\left(P\;\right)$ be the set of isomorphism classes of ...
3
votes
2answers
873 views

Undecidable languages and mapping reducibility

I am using Sipser terminology here. Can anyone give examples of languages A and B such that we can prove B is undecidable using A in a proof by contradiction but we A is not $\leq_m$ B. An example ...
1
vote
2answers
148 views

Nondeterminism and computational models

So it is clear than the nondeterministic versions of computational models such as the Turing Machine is equivalent in "power" to the deterministic model. Other than showing this fact, what would be ...
1
vote
1answer
260 views

Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}? One case this is possible is when ...
5
votes
2answers
533 views

Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory?

Let $T_1$ and $T_2$ be two first-order logical theories (over the same signature) such that $T_1 \subseteq T_2$ and both are recursively axiomatized. My question is the following: is it possible that ...
8
votes
2answers
475 views

Is the group isomorphism problem decidable for abelian groups?

According to wikipedia the group isomorphism problem is an undecidable problem. When we restrict to (countable) abelian groups does it become decidable or does it remain undecidable? In case it ...
5
votes
4answers
942 views

The word problem for finite groups

The word problem for finite groups is decidable. Is it obvious that this is true? In particular, I'm not entirely sure about what it means for the problem to be decidable (in this case---I think I ...
3
votes
1answer
156 views

Algorithms to prove that polynomials don't have integer solutions

OK, I know that Matiyasevich's solution to Hilbert's 10th problem shows that there is no algorithm to decide whether or not a polynomial $p(x_1,\ldots,p_n)$ with integer coefficients has a solution ...
3
votes
1answer
213 views

Can a polynomial size CFG over large alphabet describe any of these languages:

Can a polynomial size CFG over large alphabet describe any of these languages: Each terminal appears 0 or 2 times Word repetition {www* | w \in \Sigma *} (word repetition of an arbitrary word w) ...
2
votes
1answer
254 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
5
votes
5answers
690 views

Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where ...