[Solved]: Halting problem

Problem Detail: 

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?

Asked By : Kevin

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12538

 Ask a Question

 Download Related Notes/Documents