Halting problem is undecidable

The halting problem

Given a Turing machine M and an input w, decide whether M halts (stops) when started on w. As a language: HALT = { ⟨M, w⟩ : M halts on input w }. The question is whether HALT is decidable, that is, whether some TM always halts and answers correctly.

HALT is recursively enumerable: simulate M on w and accept if the simulation halts. But, as shown below, it is not recursive.

Theorem: HALT is undecidable

Proof (by contradiction, diagonalisation). Suppose a TM H decides HALT: H(⟨M, w⟩) halts and accepts if M halts on w, and halts and rejects if M loops on w.

Build a new TM D that takes the description ⟨M⟩ of a machine as input:

1. Run H on ⟨M, ⟨M⟩⟩ (ask: does M halt when given its own description?).
2. If H accepts (M halts on ⟨M⟩), then D loops forever.
3. If H rejects (M loops on ⟨M⟩), then D halts.

 <M> ─► [ H ] ── accept ─► loop forever
              └─ reject ─► halt
              (this whole box is machine D)

Now run D on its own description ⟨D⟩:

• Suppose D halts on ⟨D⟩. Then H accepted ⟨D, ⟨D⟩⟩, and by step 2 D loops forever. Contradiction.
• Suppose D loops on ⟨D⟩. Then H rejected ⟨D, ⟨D⟩⟩, and by step 3 D halts. Contradiction.

Either way we get a contradiction, so the machine H cannot exist. The halting problem is undecidable.

Consequences

• No program can check, for every program and input, whether it terminates.
• Many other problems are undecidable by reduction from HALT (for example, whether a TM accepts the empty string, whether a TM's language is empty, program equivalence).
• The complement of HALT is not even RE.