In the book Formal languages and automata by Peter Linz, 4th edition (Jones & Bartlett Learning), on pages 300-301, there is a proof for the fact that the halting problem is undecidable.

The proof is as follows:

We show that there is no TM $H$ that solves the halting problem.

  1. Assume there is a TM $H$ that solves the halting problem.
  2. We require that:
  • H's input is $w_M w$
  • $H$ halt in either $q_Y$ or $q_N$ appropriately (illustrate): $$ q_0 w_M w \vdash_H^* x_1 q_Y x_2, $$ if $M$ halts on $w$, and $$ q_0 w_M w \vdash_H^* y_1 q_N y_2, $$ if $M$ does not halt on $w$.
  1. Modify $H$, producing $H^{\prime}$, where $q_Y$ is not final (illustrate): $q_0 w_M w \vdash_{H^{\prime}}^* \infty$ if $M$ halts on $w$, and $q_0 w_M w \vdash_{H^{\prime}}^* y_1 q_N y_2$ if $M$ does not halt on $w$.

  2. Modify $H^{\prime}$, producing $\widehat{H}$, which: (a) copies $w_M$ : Make $M$ 's input a description of itself (b) behaves like $H^{\prime}$ thereafter: $$ q_0 w_M \vdash_{\widehat{H}}^* q_0 w_M w_M \vdash_{\widehat{H}}^* \infty, $$ if $M$ halts on $w_M$, and $$ q_0 w_M \vdash_{\widehat{H}}^* q_0 w_M w_M \vdash_{\widehat{H}}^* y_1 q_N y_2, $$ if $M$ does not halt on $w_M$.

  3. If $\widehat{H}$ 's input is a description of itself, then $$ q_0 w_{\widehat{H}} \vdash_{\widehat{H}}^* \infty, $$ if $\widehat{H}$ halts on $w_{\widehat{H}}$ (a contradiction), and $$ q_0 w_{\widehat{H}} \vdash_{\widehat{H}}^* y_1 q_N y_2, $$ if $\widehat{H}$ does not halts on $w_{\widehat{H}}$ (a contradiction).

My question:

During an exam I said that we are doing the reverse of the original machine, but I was told that we are not doing the reverse since we are not modifying anything on the side of the "no" answer. However: does that piece of the automaton also lead to a contradiction? Or is it just the yes branch that returns opposite answer? On the Internet I read that when we get a "no" answer we return a "yes" answer, and when we get a "yes" answer we start an infinite loop. However, this is not what is happening here, is it? Would someone like to clarify this?

  • $\begingroup$ In the proof you outline the machine supposedly returns No if the target machine doesn't halt. But that's a contradiction, because given itself as input, it halts (returning No) if it doesn't halt. (And it doesn't halt if it does halt). $\endgroup$
    – rici
    Sep 2 at 18:41
  • $\begingroup$ @rici thank you. So if I understood correctly, we didn't have to change anything when it returned a "no"-answer because in the beginning we already required that 𝐻 halts in either 𝑞𝑌 or 𝑞𝑁 ? And that's because we supposed that it is decidable, so it always has to halt? $\endgroup$
    – Ronald
    Sep 4 at 9:56
  • $\begingroup$ @rici And the fact that it halts in those states is necessary because if we had a loop the problem would’t be decidable since being decidable means that you halt for every input. Am I correct? $\endgroup$
    – Ronald
    Sep 5 at 14:09
  • $\begingroup$ yes, in order to decide, the machine must halt. Until it halts, the decision hasn't been made. $\endgroup$
    – rici
    Sep 5 at 15:35
  • 1
    $\begingroup$ This is mathematics, not programming. We're not actually modifying anything; we're describing how to construct $\widehat{H}$. And the point I made earlier stands: If $H$ existed, we could produce $\widehat{H}$ using a simple algorithm. We don't have to run the algorithm; that implication is simply true. But $\widehat{H}$ cannot exist. So it must be the case that $H$ doesn't exist. en.wikipedia.org/wiki/Mathematical_proof#Proof_by_contradiction $\endgroup$
    – rici
    Sep 5 at 18:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy