1 · Why this matters · the BIG picture
This is the most important undecidability proof in computer science. Every other "you cannot
write a program to detect X" theorem ultimately reduces to this one. Compilers cannot tell you whether your loop
terminates; static analyzers cannot prove arbitrary correctness; antivirus software cannot detect every possible
malware behavior — all of it traces back to the impossibility shown here.
We proved (Problem 2) that ATM is recognizable: simulate, see what happens.
Today we prove it is not decidable: no algorithm always halts with the correct yes/no answer.
That is the cleanest possible gap between "recognize" and "decide".
What we are about to prove
There is no Turing machine H such that, for every ⟨M, w⟩, H halts and accepts iff M accepts w.
Equivalently: no general-purpose halting checker can possibly exist.
The proof technique — diagonalization — is the same one Cantor used (Problem 1) to show
the reals are uncountable. Same trick, different victim: now the diagonal kills a hypothetical decider.
2 · Setup · the assumption we are about to break
Assume for contradiction that some TM H decides ATM. That means:
- H always halts on every input.
- H(⟨M, w⟩) = accept iff M accepts w.
- H(⟨M, w⟩) = reject iff M does not accept w (either rejects or loops).
From H we will construct a new TM D that does this:
The contradiction machine D
D = "on input ⟨M⟩:
1. run H(⟨M, ⟨M⟩⟩) — does M accept its own description?
2. if H accepts: reject;
3. if H rejects: accept."
Key point: D is itself a TM. We built it from H using two simple steps (run, flip). Since D is a TM,
it has its own encoding ⟨D⟩. Now we feed ⟨D⟩ to D itself. Watch what happens.
Vocabulary check
- Decider · TM that halts on every input. Outputs accept or reject.
- ⟨M⟩ · M's description, as a finite string.
- Diagonal cell (i, i) · row i = machine Mi, column i = input ⟨Mi⟩ — the case where the machine is fed itself.
3 · The proof · feed D to itself
Compute D(⟨D⟩) two ways and watch them disagree.
| Case |
By definition of D |
But also (D is a TM) |
| D accepts ⟨D⟩ | ⇒ H said D rejects ⟨D⟩
⇒ D rejects ⟨D⟩. | Direct contradiction. |
| D rejects ⟨D⟩ | ⇒ H said D accepts ⟨D⟩
⇒ D accepts ⟨D⟩. | Direct contradiction. |
Either way D contradicts itself. The only assumption we made was the existence of H. So H cannot exist. ∎
The visualization below makes this concrete: we list TMs M1, M2, … as rows and their encodings
⟨M1⟩, ⟨M2⟩, … as columns. Cell (i, j) records whether Mi accepts ⟨Mj⟩.
D's behavior is the flipped diagonal. Since D is a TM, D must appear somewhere as a row in this table —
and that row contradicts the flipped diagonal at its own column. No such row can exist.
4 · Animated demo · auto-plays · loops
5 · Worked example · a tiny "what if H existed" trace
Suppose H existed and let's imagine 4 specific TMs M1…M4 with this acceptance behavior on their own descriptions:
| i |
Mi(⟨Mi⟩) (what H says) |
D(⟨Mi⟩) (flipped) |
| 1 | accept | reject |
| 2 | reject | accept |
| 3 | accept | reject |
| 4 | reject | accept |
D's row of answers is reject, accept,
reject, accept.
Since D is a TM, it sits in the list at some index — say D = M3. Then row 3 says
D(⟨M3⟩) = accept, but D's row also says D(⟨M3⟩) = reject. Same input, two answers. Impossible.
The exact index does not matter; the contradiction lives at wherever D appears.
6 · Connections · the cascade of undecidability
- HALTTM · undecidable. Reduce ATM to it (Problem 5).
- ETM (is M's language empty?) · undecidable. Reduce ATM via a "filter" trick (Problem 6).
- EQTM (do two TMs accept the same language?) · undecidable, and not even recognizable (Problem 8).
- Rice's theorem · every non-trivial language property of TMs is undecidable. Diagonal is the engine (Problem 14).
- Gödel's incompleteness · the same self-reference and diagonal pattern proves no consistent strong-enough axiom system can prove all true arithmetic statements.
7 · Common pitfalls · what students miss
- "But D might not exist as a TM." It does: D is just "run H, flip the answer." H is a TM, flipping a bit is trivial, composition of TMs is a TM.
- "Maybe H is just very slow." The proof allows H to take arbitrarily long. It only requires H to always halt. Any decider faces the contradiction.
- Confusing the diagonal flip with simulation. The diagonal cell Mi(⟨Mi⟩) is a yes/no fact, decided by H by hypothesis. D consults H, it does not simulate Mi.
- "This only kills decidability for one input." One contradiction is enough. Mathematics does not allow even one inconsistency.
- "What about a probabilistic H?" Same argument applies to any always-halting procedure. Randomness does not help; the diagonal still flips.
8 · Q&A defence notes
Q1. Why is D itself a Turing machine?
D is built from H by composition: run H, flip the bit. If H is a TM, D is too. Every effectively-computable procedure is a TM (Church–Turing).
Q2. Why does the diagonal cell create a contradiction?
It's the unique cell where D's input is its own description. D is forced to disagree with itself there.
Q3. Compare with Cantor's diagonal (Problem 1).
Same structure. Cantor disagrees with fi at column i for arbitrary functions. Here we disagree with the TM at column = its own description.
Q4. Why does this not also kill the universal TM?
The universal TM is a recognizer, not a decider. Recognizers may loop. The contradiction in D depends on H being a decider — always halting.
Q5 (bonus). Is ATM co-recognizable?
No. If it were, we could combine the recognizer (U) and the co-recognizer to decide ATM. Since it's undecidable, the complement of ATM is not recognizable.
9 · How to present this in class
Total time: 12 minutes.
- (1 min) Recap Problem 1 (Cantor) and Problem 2 (recognizable). State the goal: ATM is recognizable but not decidable.
- (2 min) Write the assumption: H decides ATM. Emphasize "always halts".
- (2 min) Construct D on the board: 3-line pseudocode.
- (3 min) Run the visualization. Pause at the moment D appears in gold below the table.
- (2 min) Do the worked example as a case split: D accepts ⟨D⟩ ⇒ … ; D rejects ⟨D⟩ ⇒ …
- (2 min) Tie it back to compilers / static analysis. "This is why your IDE cannot warn you that your loop never terminates — for every input."