I have some concerns about the Halting problem. This is the proof I know:

Let $h(M, i)$ be a function, $M$ being Turing machine and $i$ input for the Turing machine. Let $h(M, i)$ output true whenever $M(i)$ halts. Let $h(M,i)$ output false if $M(i)$ does not halt.

Then define $p(M)$ on Turing machine $M$. $p(M)$ will halt whenever $h(M, M)$ equals false and $p(M)$ will not halt whenever $h(M, M)$ is true.

What will $p(p)$ do? Now, suppose $p(p)$ halts not. Then $h(p, p)$ is true so $p(p)$ will halt. Suppose $p(p)$ halts. Then $h(p, p)$ is false so $p(p)$ will not halt.

So $p(p)$ will either halt and halt not.

But, I think it will loop endlessly. $h(M, i)$ calls $M(i)$ and $p(M)$ will call $h(M, M)$. This is not a problem. But evaluating $p(p)$ results in calling $h(p, p)$ - which will check the value of $p(p)$. But therefor, $p(p)$ is called again, so there was a cycle and the program will continue in an infinite loop.

What am I thinking wrong?


1 Answer 1


First of all, you cannot "think wrong" :)

As for the proof - you make the wrong assumption that $h$ decides the halting problem by simply running $M$ on $i$. This is not necessarily the case (in fact, it is definitely not the case).

Observe that the naive "implementation" of $h$ is not a decider - if $M$ does not halt on $i$ then $h$ never halts. Therefore, $h$ is clearly not this naive machine.

We assume by way of contradiction that there exists some (cleverer) implementation $h$ that does manage to decide the halting problem. Then, when $h$ is given $(p,p)$, it does whatever it does to decide, but that yields the contradiction.

To resolve the issue you brought up in the comment:

Consider the machine $h$, think of it as java code, if that's more comfortable. You then modify the code of $h$ to construct the code of $p$. Now, you send to $p$ the code of itself - just like you would send any other input. It just so happens that $p$ causes $h$ to run on some code which is partially the code of $h$ itself, but that shouldn't be any problem for $h$, it just reads it like any other input, and does whatever it does to decide.

  • $\begingroup$ Thank you for your quick and decent answer :)! But I mean that $h(p, p)$ needs to check $p(p)$, and $p(p)$ needs to check $h(p, p)$. Therefor there is an infinite loop, so whatever this clever implementation of $h$ is, it must check the value of $p(p)$ and therefor causing a loop? $\endgroup$ Commented Jun 8, 2013 at 18:33
  • $\begingroup$ Updated my answer to address this. $\endgroup$
    – Shaull
    Commented Jun 8, 2013 at 18:43
  • $\begingroup$ Thanks! So I can see $p$ as a sort of extension of $h$? :) $\endgroup$ Commented Jun 8, 2013 at 19:08
  • $\begingroup$ $p$ is a modification of the code of $h$. I wouldn't call it an extension, since it doesn't really extend, just changes. But you can think of $h$ as a sub-procedure of $p$. $\endgroup$
    – Shaull
    Commented Jun 8, 2013 at 19:09

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.