# proof that halting problem is undecidable

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?

• 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).
– rici
Sep 2 at 18:41
• @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? Sep 4 at 9:56
• @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? Sep 5 at 14:09
• yes, in order to decide, the machine must halt. Until it halts, the decision hasn't been made.
– rici
Sep 5 at 15:35
• 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
– rici
Sep 5 at 18:05