Now is a Turing machine, so it has a description in {0,1}*, say, . This
string, in addition to being the description of , also can be used as input string.
We can therefore legitimately ask what would happen if is applied to From
the above, identifying M with , we get
if applied to halts, and
if applied to does not halt. This is clearly nonsense. The contradiction tells
us that our assumption of the existence of H, and hence the assumption of the
decidability of the halting problem, must be false.
One may object to Definition 12.1, since we required that, to solve the
halting problem, H had to start and end in very specific configurations. It is,
however, not hard to see that these somewhat arbitrarily chosen conditions play
only a minor role in the argument, and that essentially the same reasoning could
be used with any other starting and ending configurations. We have tied the
problem to a specific definition for the sake of the discussion, but this does not
affect the conclusion.
It is important to keep in mind what Theorem 12.1 says. It does not preclude
solving the halting problem for specific cases; often we can tell by an analysis of
M and w whether or not the Turing machine will halt. What the theorem says is
that this cannot always be done; there is no algorithm that can make a correct
decision for all w M and w.
The arguments for proving Theorem 12.1 were given because they are
classical and of historical interest. The conclusion of the theorem is actually
implied in previous results as the following argument shows.
Theorem 12.2
If the halting problem were decidable, then every recursively enumerable
language would be recursive. Consequently, the halting problem is undecidable.