Proof: To see this, let L be a recursively enumerable language on Σ, and let M be
a Turing machine that accepts L. Let H be the Turing machine that solves the
halting problem. We construct from this the following procedure:
1. Apply H to w M w. If H says “no,” then by definition w is not in L.
2. If H says “yes,” then apply M to w. But M must halt, so it will eventually tell
us whether w is in L or not.
This constitutes a membership algorithm, making L recursive. But we
already know that there are recursively enumerable languages that are not
recursive. The contradiction implies that H cannot exist, that is, that the halting
problem is undecidable.
The simplicity with which the halting problem can be obtained from
Theorem 11.5 is a consequence of the fact that the halting problem and the
membership problem for recursively enumerable languages are nearly identical.
The only difference is that in the halting problem we do not distinguish between
halting in a final and nonfinal state, whereas in the membership problem we do.
The proofs of Theorem 11.5 (via Theorem 11.3) and 12.1 are closely related,
both being a version of diagonalization.
Reducing One Undecidable Problem to Another
The above argument, connecting the halting problem to the membership
problem, illustrates the very important technique of reduction. We say that a
problem A is reduced to a problem B if the decidability of A follows from the
decidability of B. Then, if we know that A is undecidable, we can conclude that
B is also undecidable. Let us do a few examples to illustrate this idea.
Example 12.1
The state-entry problem is as follows. Given any Turing machine M =
(Q,Σ,Γ,δ,q 0 , ,F) and any q ∈ Q, w ∈ Σ + , decide whether or not the state q is ever
entered when M is applied to w. This problem is undecidable.
To reduce the halting problem to the state-entry problem, suppose that we
have an algorithm A that solves the state-entry problem. We could then use it to
a Turing machine that accepts L. Let H be the Turing machine that solves the
halting problem. We construct from this the following procedure:
1. Apply H to w M w. If H says “no,” then by definition w is not in L.
2. If H says “yes,” then apply M to w. But M must halt, so it will eventually tell
us whether w is in L or not.
This constitutes a membership algorithm, making L recursive. But we
already know that there are recursively enumerable languages that are not
recursive. The contradiction implies that H cannot exist, that is, that the halting
problem is undecidable.
The simplicity with which the halting problem can be obtained from
Theorem 11.5 is a consequence of the fact that the halting problem and the
membership problem for recursively enumerable languages are nearly identical.
The only difference is that in the halting problem we do not distinguish between
halting in a final and nonfinal state, whereas in the membership problem we do.
The proofs of Theorem 11.5 (via Theorem 11.3) and 12.1 are closely related,
both being a version of diagonalization.
Reducing One Undecidable Problem to Another
The above argument, connecting the halting problem to the membership
problem, illustrates the very important technique of reduction. We say that a
problem A is reduced to a problem B if the decidability of A follows from the
decidability of B. Then, if we know that A is undecidable, we can conclude that
B is also undecidable. Let us do a few examples to illustrate this idea.
Example 12.1
The state-entry problem is as follows. Given any Turing machine M =
(Q,Σ,Γ,δ,q 0 , ,F) and any q ∈ Q, w ∈ Σ + , decide whether or not the state q is ever
entered when M is applied to w. This problem is undecidable.
To reduce the halting problem to the state-entry problem, suppose that we
have an algorithm A that solves the state-entry problem. We could then use it to