Exercises: Computability and the Halting Problem

These move from tracing machines and sorting problems into categories, up through the halting-problem proof, reductions, and the engineering consequences. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; reconstruct each argument yourself before you peek. Remember the chapter's discipline: a decider must halt on every input; a recognizer need only accept the "yes" instances.

Part A — Warm-ups: tracing and vocabulary (⭐)

36.1 † The even-length machine from §36.1 has rule book entries for $q_{\text{even}}$ and $q_{\text{odd}}$. Trace its computation on the input aaaa, writing each configuration (tape with the head's state marked) exactly as the chapter does for aa. Does it accept or reject, and is that the right answer?

36.2 State the three possible fates of a Turing machine on a given input. Which one has no counterpart in the DFAs of Chapter 35, and why is that fate the source of undecidability?

36.3 † For each problem, say whether it is decidable or (per the chapter) undecidable, in one phrase: (a) "Is the integer $n$ prime?"; (b) "Does DFA $M$ accept the string $w$?"; (c) "Does program $P$ halt on input $x$?"; (d) "Is graph $G$ connected?"; (e) "Do programs $P$ and $Q$ compute the same function on all inputs?"

36.4 Fill in the blank with decidable, recognizable, or undecidable, and give the one-word reason: "Every decidable language is also __, because a decider is just a recognizer that additionally always ____."

36.5 † Write the halting problem as a language $\mathrm{HALT}$, using the angle-bracket encoding $\langle P, x\rangle$ from §36.4. In one sentence, explain what the notation $\langle P, x\rangle$ means and why feeding a program to another program as data is even possible (cite the Chapter 10 fact the chapter invokes).

Part B — Prove it (⭐⭐)

36.6 † (Scaffolded — fill in the missing steps.) Complete this proof that the halting problem is undecidable. Fill each blank.

• Assumption. Suppose for contradiction a decider $H$ exists: for every program $P$ and input $x$, $H(P,x)$ always ______ and correctly reports "halts" or "loops."
• Construction. Define a program $D$ that takes one input $P$: it runs $H(P, P)$, and does the opposite — if $H$ says $P$ halts on $P$, then $D$ __; if $H$ says $P$ loops on $P$, then $D$ ____.
• The diagonal move. Now run $D$ on ______.
• Case 1. If $D$ halts on input $D$, then $H(D,D)$ reports "__", so by $D$'s rule $D$ ____ — a contradiction.
• Case 2. If $D$ loops on input $D$, then $H(D,D)$ reports "__", so by $D$'s rule $D$ ____ — again a contradiction.
• Conclusion. The biconditional "$D$ halts on $D$ $\iff$ __" is self-contradictory; the only assumption was ____, so it is false. $\blacksquare$

36.7 Prove that the language $\overline{\mathrm{HALT}} = {\langle P, x\rangle : P \text{ does \textbf{not} halt on } x}$ is not recognizable. You may use, as a given, the chapter's facts that (i) $\mathrm{HALT}$ is recognizable, and (ii) if a language $L$ and its complement $\overline{L}$ are both recognizable then $L$ is decidable. Lay out the one-line contradiction.

36.8 † Prove that the class of decidable languages is closed under complement: if $L$ is decidable, so is $\overline{L}$. (Hint: take a decider for $L$ and describe the small modification that decides $\overline{L}$. Why does this same trick fail for recognizable languages — i.e., why can't you swap accept/reject on a recognizer?)

36.9 A language $L$ is co-recognizable if its complement $\overline{L}$ is recognizable. Prove: $L$ is decidable if and only if $L$ is both recognizable and co-recognizable. (One direction is immediate; for the other, describe a decider that runs the two recognizers "in parallel," alternating steps, and argue it always halts.)

36.10 † Prove that there exists a language that is not recognizable, without naming a specific one, by a counting argument that reuses Chapter 10. (Hint: how many Turing machines are there? How many languages over $\{0,1\}$? Which cardinalities are these, and what does the comparison force?)

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, matching the book's convention. Keep each solution short (≤ 30 lines).

36.11 † Generalize the §36.1 simulator. Write run_tm(delta, tape, start="q0", accept="ACC", reject="REJ", blank="_", max_steps=10_000) that returns "ACC", "REJ", or "LOOP?" when the step budget is exhausted. Then encode the Turing machine that decides whether a string of a's has length divisible by 3 (states q0, q1, q2 tracking length mod 3; accept on the end-blank iff in q0). Show the expected output for inputs "aaa" and "aaaa". In one sentence, explain what the "LOOP?" return value has to do with §36.4.

36.12 Write applied_to_self(program) that runs a program on its own description (returns program(program)), and a helper name_of(f) returning f.__name__. Show that applied_to_self(name_of) halts and produces the string "name_of". Then explain, in two sentences, why this harmless self-application becomes a paradox in the proof's program $D$ but not here.

36.13 † Write a Python function halts_within(step_fn, state, n) that simulates at most n steps, where step_fn(state) returns the next state or None when the program has halted. It must return True if a halt is observed within n steps and the string "unknown" otherwise — never the string "loops". Trace it on a countdown_step program for (state=3, n=10) and (state=8, n=5). Explain why returning "unknown" (not "loops") is the honest answer, citing the Find-the-Error callout in §36.4.

36.14 (Bridges to §36.5.) Write a Python program-builder build_P_prime(P_name, x) that, given the name of a program P and an input x, returns the source code string of the gadget $P'$ from the EMPTY reduction: $P'$ ignores its own input, runs $P$ on $x$, and accepts if that run halts. Print the emitted source for build_P_prime("P", "data"). The function must emit text only — it must never call P. In one sentence, say why "emit, don't run" is essential for the reduction to be a valid algorithm.

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which step fails and why — name the exact flawed move, don't just say "it's wrong."

36.15 † Claim: "The halting problem is decidable. Proof: given $\langle P, x\rangle$, run $P$ on $x$ for $10^9$ steps. If it halted, output 'halts'; otherwise output 'loops.' This procedure always terminates, so it decides $\mathrm{HALT}$." — Find the flaw. (Which of halts-on-all-inputs and correct does this procedure satisfy, and which does it violate?)

36.16 Claim: "To prove the program-equivalence problem undecidable, reduce it to the halting problem: given two programs, ask whether each halts, and compare. Since equivalence reduces to $\mathrm{HALT}$, equivalence is undecidable." — Find the flaw. (Pay attention to the direction of the reduction; recall the §36.5 pitfall.)

36.17 † Claim: "Running a program $P$ on input $x$ and watching it is a decider for the halting problem: if $P$ halts you see it stop (answer 'halts'); if it does not, then since it isn't stopping you answer 'loops.'" — Find the flaw. (At exactly what moment does the 'loops' branch fire, and can it ever fire correctly?)

36.18 Claim: "The Church–Turing thesis is a theorem, proved by showing Turing machines, the lambda calculus, and general recursive functions all compute the same functions." — Find the flaw. (What exactly was proved, and what part of the thesis can never be proved? Use the chapter's wording.)

Part E — Model it & Conjecture and test (⭐⭐⭐)

36.19 † (Model it.) A continuous-integration vendor advertises a tool that "guarantees to flag every test in your suite that will hang forever, and never falsely flags a test that finishes." Translate this advertised behavior into the language of this chapter: name the decision problem the tool claims to decide (write it as a language), state whether a sound-and-complete version can exist, and identify which chapter result settles it. Then describe the honest behavior a real such tool must adopt instead (cite a coping strategy from §36.6).

36.20 (Model it.) A smart-contract platform charges "gas" for each execution step and aborts a contract once its gas runs out. Explain, using the decidable/undecidable language of the chapter, which undecidable question the gas mechanism sidesteps and which decidable question it answers instead. Write both questions as precise decision problems, and name the §36.6 coping strategy at work.

36.21 † (Conjecture and test, then prove.) Consider the bounded question $\mathrm{HALT}_N = \{\langle P, x\rangle : P \text{ halts on } x \text{ within } N \text{ steps}\}$ for a fixed constant $N$. (a) Using the halts_within code from Exercise 36.13, write three lines that test whether $\mathrm{HALT}_N$ seems decidable for $N = 1000$ on a handful of small programs you make up. (b) Conjecture whether $\mathrm{HALT}_N$ is decidable for every fixed $N$. (c) Prove your conjecture. (d) Explain in one sentence why this does not contradict the undecidability of $\mathrm{HALT}$ (which has no step bound).

36.22 (Conjecture and test.) Let applied_to_self be as in Exercise 36.12. Conjecture: "For every Python function f that takes one argument, applied_to_self(f) either halts or runs forever — and we can always tell which by inspecting f." Write a f for which inspection is easy (clearly halts) and a g for which it is not easy (e.g., g searches for a counterexample to a famous open conjecture). Then argue from §36.4 why no general inspector exists, and identify which earlier exercise's claim this refutes.

Part F — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

36.23 † (Ch. 5 + 36.) The halting proof is a proof by contradiction whose engine is a self-negating biconditional. Compare it to the classic Chapter 5 proof that $\sqrt{2}$ is irrational. For each proof, state (i) the single assumption made for contradiction and (ii) the contradictory fact that ends it. What structural feature do the two proofs share?

36.24 (Ch. 10 + 36.) In Chapter 10 you built a function $g$ with $g(n) = 1 - f_n(n)$ to escape any proposed list $f_0, f_1, f_2, \dots$ of functions $\mathbb{N} \to \{0,1\}$. Write a precise dictionary between that proof and the halting proof: what plays the role of the list, of the diagonal entry $f_n(n)$, and of the flip $1 - f_n(n)$? In one sentence, say why both flips produce a contradiction (of different statements).

36.25 † (Ch. 35 + 36.) For the DFAs of Chapter 35, the emptiness problem "does DFA $M$ accept no string?" is decidable (reachability of an accepting state). Yet §36.5 proved the emptiness problem for Turing machines / general programs is undecidable. Explain precisely what changes between the two settings to flip a decidable problem into an undecidable one. (Hint: what can you always do with a DFA that you cannot always do with a Turing machine?)

36.26 (Ch. 14 + 36.) Chapter 14 measured how long a (halting) algorithm runs; this chapter asks whether a halting algorithm exists at all. Place these four questions in the right box of a 2×2 grid whose axes are {decidable, undecidable} and {we asked "how fast?", we did not}: (a) "Sort $n$ numbers"; (b) "Does $P$ halt on $x$?"; (c) "Is $n$ prime?"; (d) "Are $P$ and $Q$ equivalent?" Then write one sentence on how Chapter 37 will subdivide the decidable column.

36.27 (Deep Dive — Rice's theorem.) Rice's theorem says every nontrivial semantic property of programs (a property of the function a program computes, held by some programs but not all) is undecidable. (a) Explain why "the program's source code contains the token while" is not a semantic property, so Rice's theorem does not apply to it. (b) Sketch how to derive undecidability of "does $P$ compute the constant-zero function?" by reduction from $\mathrm{HALT}$, following the EMPTY template of §36.5 (state the gadget $P'$; you need not write every line).

36.28 (Deep Dive — recognizable vs. co-recognizable.) Using Exercises 36.7 and 36.9, draw the containment picture: place decidable, recognizable, and co-recognizable as regions, mark where $\mathrm{HALT}$ and $\overline{\mathrm{HALT}}$ sit, and identify the region that equals the intersection recognizable $\cap$ co-recognizable. Justify each placement in one phrase.

36.29 (Deep Dive — toward Chapter 37.) The chapter says reductions reappear in Chapter 37 to prove problems NP-complete rather than undecidable. In one short paragraph, state the single thing that a Chapter 37 reduction must add that a Chapter 36 (undecidability) reduction does not require, and explain why that addition matters when "hard" means "intractable" rather than "impossible."

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each undecidability proof, the rubric rewards: the correct reduction direction ($\mathrm{HALT} \le B$), a gadget that is a finite program-builder (emits code, never runs it), an explicit appeal to §36.4 for the contradiction, and a clean statement of what would otherwise become decidable.