# Halting problem

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?

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.

• 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? – www.data-blogger.com Jun 8 '13 at 18:33
• Updated my answer to address this. – Shaull Jun 8 '13 at 18:43
• Thanks! So I can see $p$ as a sort of extension of $h$? :) – www.data-blogger.com Jun 8 '13 at 19:08
• $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$. – Shaull Jun 8 '13 at 19:09