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).
Questions tagged [computability]
2395 questions
2
votes
1 answer
Prove there exists a recursive language which no TM accepts in n steps.
There is a problem I can't solve: Assume n is an integer. Prove that there exists a recursive language such that there is no Turing Machine which accepts it and makes a maximum of n steps for every input. I'll be glad to receive hints. Thanks!
Idan
- 782
2
votes
2 answers
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 reverse of $w$, and that
$$T = \{ \langle M\rangle…
starflyer
- 550
2
votes
1 answer
Kleene's s-m-n theorem without the "n"
I'm working through Cutland's Computability. Problem 4.4.5 says:
Show that for each $m$ there is a total ($m+1$)-ary computable function $s^m$ such that for all $n$,
$$\phi_{e}^{(m+n)} (\textbf{x},\textbf{y}) \simeq…
Luke
- 344
2
votes
2 answers
Natural problems not in the Arithmetical Heirarchy
What are some natural problems not in the Arithmetical Hierarchy?
Demi
- 329
2
votes
2 answers
Is the set of indices of partial computable functions with finite domains r.e.?
Let $W_x$ be the domain of the partial computable function $\varphi_x$. I know that the set
$$\operatorname{Fin} = \{x : W_x\text{ is finite}\}$$
is not computable (as a corollary of Rice's theorem, for instance). My question is,
Is the set…
Daniel
- 6,999
2
votes
0 answers
The smallest prime greater than $x$ (primitive recursive functions)
So, I want to construct the function $f(x)$ that returns the smallest prime greater than $x$.
First, I constructed the function $g(x,y)$ that returns the smallest prime strictly between $x$ and $y$ (or $y$ if there is no such prime) using primitive…
wet
- 605
2
votes
1 answer
For a Turing machine $M$ can we decide whether there's an input which at $M(x)$ never moves left?
After Reading again the answer to this question and the answer to this question,
I am wondering if the language $L=\{\langle M \rangle | M $is a Turing machine and $\exists$ input $x$ such that in $M(x)$running $M$ doesn't move left $\}$ can be…
Jozef
- 7,100
2
votes
2 answers
For a Turing machine and input $w$- Is "Does M stop or visit the same configuration twice" a decidable question?
I have the following question out of an old exam that I'm solving:
Input: a Turing machine and input w
Question: Does on running of M on w, at least one of the following things happen
-M stops of w
-M visits the same…
Jozef
- 7,100
2
votes
1 answer
Not all recursively enumerable sets are recursive
Is there a simple explanation which says why this is? I'm not looking for a proof or anything that contains too many technical terms.
I've come across the example of the Halting problem but I don't fully understand it.
The definitions I'm using of…
yuopiop
- 37
2
votes
1 answer
How many Turing degrees are there?
So I know there are precisely $2^{\aleph_0} $ Turing degrees, but is there a proof of this somewhere?
Christopher Rose
- 925
2
votes
2 answers
Is this set recursively enumerable/recursive?
I've recently started studying the ideas behind algorithms. That being said, I found myself browsing through different sorts of problems in order to get a better grasp on the subject.
Inspired by this question, I'm going to ask for a few more…
johndoe
- 21
2
votes
3 answers
Is the set of total recursive functions countable?
There are many reasons to hold that the set of total recursive functions is countable, and among them the two following seem to me to be very powerful and sound:
The set of total recursive functions is a strict subset of the set of partial…
G.M
- 71
- 3
2
votes
1 answer
Are there decidable problems which aren't in $NP$?
I'm currently attending a course introducing the basic notions of algorithms, complexity, decidability etc. My question is:
Is there a decidable problem $A$ which isn't in $NP$, i.e. it is always possible to verify a solution to $A$ with the help of…
Redundant Aunt
- 12,030
- 2
- 22
- 66
2
votes
1 answer
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
An algebraic expression is decidable. This is also…
user57159
2
votes
1 answer
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 is clearly no for primitive recursive functions,…
Ewan Delanoy
- 61,600