if M applied to w does not halt. Here q y and q n are both final states of H.
Theorem 12.1
There does not exist any Turing machine H that behaves as required by
Definition 12.1. The halting problem is therefore undecidable.
Proof: We assume the contrary, namely, that there exists an algorithm, and
consequently some Turing machine H, that solves the halting problem. The input
to H will be the string w M w. The requirement is then that, given any w M w, the
Turing machine H will halt with either a yes or no answer. We achieve this by
asking that H halt in one of two corresponding final states, say, q y or q n . The
situation can be visualized by a block diagram like Figure 12.1. The intent of this
diagram is to indicate that, if H is started in state q 0 with input w M w, it will
eventually halt in state q y or q n . As required by Definition 12.1, we want H to
operate according to the following rules:
if M applied to w halts, and
if M applied to w does not halt.
Next, we modify H to produce a Turing machine H’ with the structure shown
in Figure 12.2. With the added states in Figure 12.2 we want to convey that the
transitions between state q y and the new states q a and q b are to be made,
regardless of the tape symbol, in such a way that the tape remains unchanged.
The way this is done is straightforward. Comparing H and H’ we see that, in
situations where H reaches q y and halts, the modified machine H’ will enter an
infinite loop. Formally, the action of H’ is described by
if M applied to w halts, and