Chapter 36 — Key Takeaways (Reference Card)
Computability and the Halting Problem. The one-page re-grounding card: model, definitions, the proof in a box, the reduction recipe, and the engineering consequences. Reread before an exam.
Core definitions (memorize)
| Term | One-line definition |
|---|---|
| Turing machine | $(Q,\Sigma,\Gamma,\delta,q_0,q_{\text{accept}},q_{\text{reject}})$: finite states + unbounded tape + transition $\delta\colon Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$. The formal model of any algorithm. |
| 3 fates of a TM | accept · reject · loop forever (the third has no DFA analog and is the source of undecidability). |
| Church–Turing thesis | Claim, not theorem: every mechanically computable function is Turing-computable. Lets "no TM" = "no algorithm, any language, ever." |
| Turing complete | A language computes exactly the Turing-computable functions (Python = C = λ-calculus = TM in raw power). |
| decidable (recursive) | A TM halts on every input and answers yes/no correctly. |
| recognizable (r.e. / semi-decidable) | A TM accepts every "yes"; may loop forever on "no." |
| undecidable | Not decidable: no TM halts on all inputs and decides it. |
| halting problem | $\mathrm{HALT}=\{\langle P,x\rangle : P \text{ halts on } x\}$. Undecidable. |
| reduction $A\le B$ | Algorithm mapping $A$-instances to $B$-instances preserving the answer; "$B$ is at least as hard as $A$." |
The class hierarchy (containment)
$$\text{decidable} \;\subsetneq\; \text{recognizable} \;\subsetneq\; \text{all languages}$$
- Every decider is a recognizer that always halts → decidable $\subseteq$ recognizable.
- $\mathrm{HALT}$ is recognizable but not decidable → the containment is strict.
- Most languages are not even recognizable (Ch. 10 counting: countably many TMs, uncountably many languages).
| Halts on YES inputs? | Halts on NO inputs? | |
|---|---|---|
| Decider | yes (accept) | yes (reject) |
| Recognizer | yes (accept) | maybe loops forever |
The halting proof — in a box
Theorem (Turing 1936): $\mathrm{HALT}$ is undecidable.
| Step | Move |
|---|---|
| 1. Assume | A decider $H$ exists: $H(P,x)$ always halts, returns "halts"/"loops" correctly. |
| 2. Build | $D(P)$: run $H(P,P)$; if "halts" → loop; if "loops" → halt. (Do the opposite.) |
| 3. Diagonalize | Run $D$ on its own description: consider $D(D)$. |
| 4. Contradict | $D$ halts on $D$ $\iff$ $H(D,D)=$"halts" $\iff$ $D$ loops on $D$. Self-negating. |
| 5. Conclude | Only assumption was "$H$ exists" → $H$ cannot exist. $\blacksquare$ |
One-liner: $H$ would let us build "do the opposite of what $H$ predicts about me," which then halts iff it doesn't.
It's Cantor's diagonal: rows = all programs $P_n$; diagonal entry = "$P_n$ on input $P_n$"; flip = $D$ does the opposite. Same as Ch. 10's $g(n)=1-f_n(n)$, aimed at programs.
Reduction recipe (to prove $B$ undecidable)
GOAL: show B is undecidable.
1. Assume (for contradiction) a decider E for B exists.
2. Build a finite, mechanical program-builder: from <P, x> construct P'
such that (P' is a YES-instance of B) <=> (P halts on x).
*** Building P' must NOT run P -- just emit source code. ***
3. Then "build P', run E, (flip if needed)" is a DECIDER for HALT.
4. HALT is undecidable (36.4) -> contradiction -> B is undecidable. ∎
Direction rule: reduce HALT → B (i.e. $\mathrm{HALT}\le B$). NOT $B\to\mathrm{HALT}$.
⚠️ $B \le \mathrm{HALT}$ proves nothing about $B$'s undecidability — many decidable problems also reduce to HALT.
Difficulty flow: $A\le B$ ⇒ solver-for-$B$ gives solver-for-$A$ ⇒ solvability flows down, impossibility flows up.
Catalogue of undecidable problems (all by reduction from HALT)
| Problem | Question | Practical fallout |
|---|---|---|
| HALT | Does $P$ halt on $x$? | No perfect termination checker |
| EMPTY | Does $P$ accept no input? | — |
| Equivalence | Do $P_1,P_2$ compute the same function? | No compiler can certify optimization correct in all cases |
| Dead code | Can this line ever run? | No perfect dead-code detector |
| Bug properties | Ever null-deref / throw / overflow? | No perfect static analyzer |
| Post Correspondence Problem | String-tiling match exists? | (classic reduction target) |
| Hilbert's 10th | Integer root of a polynomial? | Undecidable (Matiyasevich 1970, Tier 2) |
| Rice's theorem | Any nontrivial property of a program's behavior | Almost all behavioral analysis is impossible in general |
"When is it actually decidable?" decision aid
| If the question is… | Then it is… | Because |
|---|---|---|
| "$P$ halts ever on $x$?" | undecidable | the general unbounded case (36.4) |
| "$P$ halts within $N$ steps?" | decidable | simulate $\le N$ steps and answer |
| about a DFA / regex (Ch. 35) | decidable | finite memory, must halt on finite input |
| in a non-Turing-complete language | often decidable | no unbounded loops (total languages, recursion-free SQL) |
| a nontrivial behavioral property of arbitrary code | undecidable | Rice's theorem |
a syntactic property (e.g. "uses a goto?") |
decidable | inspect the text, don't run it |
Litmus test for undecidability: Could a solver for this problem be turned into a halting-detector? If yes → undecidable.
Common pitfalls
| Pitfall | Reality |
|---|---|
| "Just run $P$ and watch it stop." | Only a recognizer: loops forever when $P$ loops; never decides "no." |
| "Simulate for a million steps, then answer." | Always halts but wrong — some program halts at step $10^6+1$. No fixed bound works. |
| "$x$ isn't on the list — just add it." (Ch. 10) | Re-running the diagonal on the patched list escapes again. Defeats all lists. |
| "TM is too weak to model real computers." | TM simulates any CPU and any language (slowly). Simplicity aids proofs; loses no power. |
| Reducing $B \le \mathrm{HALT}$ to prove $B$ undecidable. | Wrong direction. Reduce $\mathrm{HALT}\le B$. |
| "Undecidable = unsolved / very hard." | Undecidable = provably no algorithm, distinct from intractable (Ch. 37) and from open. |
Engineering consequences
- Perfect bug-finders / optimizers / equivalence-checkers / termination-checkers are impossible, not unbuilt.
- Real tools must be sound but incomplete (every warning real, misses some bugs) or complete but unsound (catches all bugs, some false alarms). Cannot be both.
- Coping strategies: (1) bound the resource (timeouts, gas, step limits); (2) restrict the language (total/non-Turing-complete); (3) be conservative (type/borrow/termination checkers reject the unprovable); (4) ask a human (proof assistants check a supplied proof).
Cross-references & lineage
- Builds on: Ch. 5 (proof by contradiction), Ch. 10 (countable/uncountable, diagonalization), Ch. 35 (DFA, language, Chomsky hierarchy).
- Sets up: Ch. 37 (reduction → NP-completeness; the inner boundary P vs. NP).
- Threshold concept: undecidability — a specific, named problem no algorithm can ever solve.
Toolkit additions (computability.py)
| Function | Purpose |
|---|---|
run_tm(delta, tape, ...) |
Turing-machine simulator; returns ACC / REJ / LOOP? (the LOOP? is the undecidable gap made visible — a bounded simulator can't decide halting). |
applied_to_self(program) |
Runs a program on its own description — the self-reference behind the §36.4 paradox. |
Lineage: Ch. 10's diagonal_escape (a row no table contains) → this chapter's diagonal fired at
programs (the halting paradox).