HALT_TM is undecidable

The halting problem is the most famous undecidable problem in computer science. Every introductory book mentions it. Here is the precise statement: no program can examine an arbitrary program + input and reliably tell you whether that program will eventually halt or run forever.

Practically, this means:

• Compilers cannot warn about every infinite loop.
• Static analyzers cannot guarantee termination of arbitrary code.
• "Will this regex match?" or "Will this script finish?" — undecidable in general.

A reduction is the workhorse of complexity theory. We say "problem A reduces to problem B" if a solver for B gives us a solver for A. Notation: A ≤ B.

The contrapositive is what we exploit: if A is unsolvable, then B is unsolvable too (because solving B would solve A — but A cannot be solved).

For HALT_TM we present the Turing reduction first (intuitive), then the mapping reduction (in Q4 below) for completeness.

Assume R is a decider for HALT_TM. Define:

S decides A_TM: it always halts (step 3 is safe because R confirmed M halts), and it outputs the correct answer. But Problem 3 told us no decider for A_TM exists. Contradiction ⇒ R does not exist ⇒ HALT_TM is undecidable. ∎

Suppose we have these two specific inputs:

Every row terminates with a definite yes or no. Look closely at row 1: S never tried to simulate M₁. R told us up front it would loop, so we shortcut to reject without ever running M₁. That shortcut is what makes S a decider rather than just a recognizer.

• E_TM (Problem 6) · undecidable. Reduce A_TM by building M' that accepts only w.
• REGULAR_TM, CFL_TM (Problem 7) · undecidable via similar reductions.
• EQ_TM · not recognizable, not co-recognizable. Reduces both ways.
• PCP, tiling, word problem for groups · all reduce from A_TM or HALT_TM.
• Rice's theorem (Problem 14) · the master generalization: every non-trivial language property reduces from A_TM.

All of these proofs share the structure: "If you could solve me, you could solve A_TM — which you can't."

1. Reducing in the wrong direction. To prove B undecidable, reduce a known undecidable problem to B (not the other way around). "A ≤ B" means B is at least as hard as A.
2. Forgetting why simulation is now safe. Direct simulation of M(w) only terminates because R already confirmed M halts. Without R, step 3 could loop.
3. Believing HALT is even harder than A_TM. Both have the same degree of unsolvability; reductions go both ways.
4. "R rejected, so M halts but rejects." No — R rejecting means M does not halt at all. R is a decider for HALT, not for accept.
5. Mixing up Turing and mapping reductions. Turing reductions can do extra work after the call; mapping reductions cannot. For undecidability, either kind suffices.

• Q1. What if M loops? Why is step 3 safe?
  We reach step 3 only when R said M halts. So the direct simulation is guaranteed to terminate. The danger of looping is fully absorbed by R.
• Q2. Could we skip R and just simulate M directly?
  No — if M loops on w, the simulation never returns. Without R there is no way to tell halting from "not yet halted". R is what makes S a decider, not just a recognizer.
• Q3. Why is this a "Turing reduction" and not a mapping reduction?
  S calls R as a subroutine and then does more work (step 3). A mapping reduction would produce a single ⟨M', w'⟩ from ⟨M, w⟩ such that membership in HALT_TM directly answers membership in A_TM. Both kinds of reduction show undecidability; mapping reductions are stricter.
• Q4. Construct a mapping reduction A_TM ≤_m HALT_TM.
  Given ⟨M, w⟩, output ⟨M', w⟩ where M' on input x simulates M on w; if M accepts, M' halts; if M rejects, M' loops. Then M accepts w ⇔ M' halts on w ⇔ ⟨M', w⟩ ∈ HALT_TM.
• Q5. Is HALT_TM at least recognizable?
  Yes. Simulate M on w; accept the moment it halts. If it never halts, the recognizer loops — that's allowed for recognizers.

Total time: 10 minutes.

• (1 min) Open with the practical hook: "Why can't your IDE warn you about every infinite loop?"
• (2 min) State the goal. Define A ≤ B at the level of intuition before writing it precisely.
• (3 min) Walk through the construction of S. Emphasize three regions on the picture: input → R box → simulator box → output.
• (2 min) Run the visualization. Let it play through the 5 stages with the pause control.
• (2 min) Wrap with the worked example table. Highlight row 1 — the "shortcut" — as the heart of the trick.