Date: Wed, 08 Jan 1997 20:50:03 GMT Server: NCSA/1.4.2 Content-type: text/html
The halting problem is defined to be:
Theorem: The halting problem is undecidable.
Proof: The proof is by contradiction.
Suppose that the halting problem is decidable.
Then there must be a Turing machine H with the
property that H halts on all inputs, and accepts if and only if
M halts on input x.
(Recall that
is the binary representation of the Turing machine M.)
We define a new Turing machine D which does the following on inputs of
the form .
There are two possibilities, D halts on input or D does
not halt on input
.
We will come to a contradiction in both cases.
If D halts on input , then by the definition of H,
H accepts
. By the definition of D, D does not halt on input
.
If D does not halt on input , then by the definition of H,
H halts on input
without accepting.
By the definition of D, D halts on input
.