Date: Wed, 08 Jan 1997 20:50:03 GMT Server: NCSA/1.4.2 Content-type: text/html The Halting Problem



next up previous
Next: About this document

The Halting Problem

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 .

  1. Copy the input to form the string .
  2. Run H on the input .
    1. If H halts without accepting then D halts.
    2. If H halts and accepts then D simply loops forever.

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 .





James Fix
Tue Mar 12 11:18:16 PST 1996