1
$\begingroup$

Suppose I wish to find out whether $\{M: \text{M is a Turing machine that does XXX}\}$ is recursive, where $XXX$ can be anything about the Turing machine. I have a bad proof that proves that all such sets are not recursive, but I don't know why this proof is wrong.

I propose the following Turing machine, for some Turing machine $N$ and input $y$:

$M': \text{M' does XXX if N halts on y, otherwise M' does not do XXX}$.

Suppose that $\{M: \text{M is a Turing machine that does XXX}\}$ is recursive; then whether $M'$ does $XXX$ is known. Hence whether $N$ halts on $y$ is known (i.e. the Halting problem is decidable), which leads to a contradiction. Hence we conclude that $\{M: \text{M is a Turing machine that does XXX}\}$ is not recursive.

But sets like $\{M: \text{M is a Turing machine that has at least two states}\}$ are clearly recursive.

May I ask what is wrong with this proof?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

The claim is wrong. Consider the following language $L = \{M : M $ is a Turing machine that halts within the first 100 steps of execution on input 0$\}$.

$L$ is recursive. You can run $M$ for 100 steps and check if it halts.

The error in your proof: Your Turing machine $M'$ is not implementable, because you can't test whether $N$ halts on $y$.

You might be interested in Rice's theorem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you very much! Then could I ask why this Turing machine below works (taken from page 60 of Papadimitriou's Computational Complexity 1st ed.)? It and many similar (correct) examples also seem to use the "do XXX if $N$ halts on $y$, otherwise no" approach. "For the set $\{M: \text{M halts on all inputs}\}$, fix $M$ and input $x$. Construct $M'$ such that on input $y$, if $y=x$ then run $M(x)$, and otherwise halt." My question is, you can also rephrase this Turing machine as "if $y=x$ and $M(x)$ does not halt, then don't halt; otherwise halt." $\endgroup$
    – Kindness
    Commented Jun 5 at 12:15
  • $\begingroup$ @Kindness, That excerpt does not contain "if N halts on y then... otherwise ..." If you want to show it is a Turing machine, you have to show that it can be implemented as a Turing machine. Not every idea of the form "If N halts on y then do T1 else do T2" can be implemented as a Turing machine; some can, some can not. You have to check and prove that your idea is implementable. The textbook example is; your example in your question isn't. $\endgroup$
    – D.W. ♦
    Commented Jun 5 at 19:10
  • $\begingroup$ Thank you very much for the clarification! $\endgroup$
    – Kindness
    Commented Jun 5 at 19:13
  • $\begingroup$ "Your Turing machine M′ is not implementable, because you can't test whether N halts on y." - I'm pretty sure that was the point. $\endgroup$
    – Criticizing Israel not allowed
    Commented Jun 8 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.