7.1The halting problem
The idea
The halting problem is the first undecidable problem: no machine can tell, for every program and input, whether it stops.
Think of it like this: A barber who shaves everyone who does not shave themselves: who shaves the barber? A decider cannot exist for the same reason.
Why it exists
It is the anchor for every other undecidability proof.
How it works
- Assume a decider H for "M accepts w" exists.
- Build D: on input ⟨M⟩, run H on ⟨M, ⟨M⟩⟩ and do the opposite.
- Run D on ⟨D⟩: D accepts iff D does not accept. Contradiction.
- So A_TM is undecidable but still recognisable (RE).
Worked example: The diagonal
Flip the diagonal of the table of "Mᵢ accepts ⟨Mⱼ⟩" to get a row that differs from every row, so it is not any machine.
Now play with it
- →Step through the diagonal argument.
| ⟨M1⟩ | ⟨M2⟩ | ⟨M3⟩ | ⟨M4⟩ | ⟨M5⟩ | |
|---|---|---|---|---|---|
| M1 | 1 | 0 | 1 | 0 | 1 |
| M2 | 0 | 0 | 1 | 1 | 0 |
| M3 | 1 | 1 | 1 | 0 | 0 |
| M4 | 0 | 1 | 0 | 0 | 1 |
| M5 | 1 | 0 | 0 | 1 | 1 |
- Rows are Turing machines M₁…M₅, columns are inputs ⟨M₁⟩…⟨M₅⟩. Entry 1 means "Mᵢ accepts ⟨Mⱼ⟩".
- Look only at the diagonal: does Mᵢ accept its own description?
- Define D by flipping the diagonal: D accepts ⟨Mᵢ⟩ exactly when Mᵢ does NOT.
- D differs from every row Mᵢ at column i, so D is not any Mᵢ. But D would be a TM if a decider for acceptance existed: contradiction. So no such decider exists.
Check yourself
A_TM is
Exam notes (the dense version)
ATM = {⟨M, w⟩ : M accepts w} is RE but not recursive. The proof is by diagonalisation: a decider would let you build a machine D that does the opposite of every machine on its own description, which cannot be any machine. Its complement is not even RE.
Previous year questions: Decidability & Undecidability (7)
PYQs are grouped by topic, so this is the full set for Decidability & Undecidability; try the ones that match this subtopic. Open all 7 on the topic page.