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
