Exercises — Halting problem — undecidability proof by diagonalization

$HALT=\{⟨P,w⟩\mid P\text{ halts on input }w\}$ Undecidable. No total program (one that always halts with a yes/no answer) decides membership in $HALT$ for every pair.

• Blank 1: loop forever
• Blank 2: halt

D always does the opposite of H's prediction about P running on its own code.

1 → (b), 2 → (c), 3 → (a). See Decidable vs Recognizable Languages: every decidable language is recognizable, but $HALT$ is recognizable and not decidable.

If D(D) halts, the only branch that halts is the else. The else runs exactly when H(D,D) == LOOP. So H claimed D(D) runs forever — but we assumed it halts. H is wrong, contradicting "H correct." ∎

If D(D) loops, the if-branch was taken (that is the only branch that loops). The if-branch runs exactly when H(D,D) == HALT. So H claimed D(D) halts — but we assumed it loops. H is wrong again. Both cases fail, so the equivalence $D(D)\text{ halts}⟺H(D,D)=\text{LOOP}⟺D(D)\text{ loops}$ holds, and a statement equal to its own negation is impossible.

• A: halts — it prints once and stops (any input).
• B: loops forever — the empty while True never exits.
• C: halts — n starts finite and strictly decreases to $0$, so the loop runs exactly $\text{len}(w)$ times.

Deciding specific programs is easy. Undecidability only forbids one algorithm that is correct for all programs at once.

D's behaviour on input $⟨P_k⟩$ is defined to be the flip of the diagonal cell $(k,k)$ — i.e. the flip of "how $P_k$ behaves on itself." So D and $P_k$ differ in column $k$. This holds for every $k$: D differs from $P_1$ in column 1, from $P_2$ in column 2, and so on down the amber diagonal.

A program that differs from every row cannot be any row — yet the list was supposed to contain all programs, including D. Contradiction. This is exactly Cantor's Diagonal Argument applied to the program×program table.

The proof needs H(D,D) to return a value so that D can then act on it. If H were allowed to loop forever on some inputs, then on the fatal input H(D,D) might simply never return — and D would just hang inside its if test. No answer, no contradiction. The paradox is triggered precisely by H being forced to always give a definite HALT/LOOP. That is why we assume H is a total decider, not a mere recognizer.

Recognizer R(⟨P,w⟩): run a Universal Turing Machine to simulate $P$ on $w$ step by step; if the simulation halts, output yes.

• On a yes-instance ($P$ halts on $w$): the simulation eventually stops → R outputs yes. ✔
• On a no-instance ($P$ loops): the simulation runs forever → R never outputs anything. ✘

So R confirms membership but can never confirm non-membership. That one-sided behaviour is the definition of a recognizer that is not a decider.

Reduction $HALT\le HAL{T}_{\epsilon }$ (see Reductions and Mapping Reducibility). Given any $⟨P,w⟩$, construct a new program:

P_w(x):          # ignores its input x
    run P on the hardcoded string w

Then $P_w$ halts on empty input $⟺P$ halts on $w$. If a decider $E$ for $HAL{T}_{\epsilon }$ existed, we could decide $HALT$ by building $P_w$ and running $E(⟨P_w⟩)$. But $HALT$ is undecidable — contradiction. Hence $HAL{T}_{\epsilon }$ is undecidable. ∎

Given $⟨P⟩$, build:

Q(x):
    run P on empty input      # first, do P's empty-input computation
    accept                    # only reached if that computation halted

$Q$ accepts every string (in particular 01) $⟺P$ halts on empty input; if $P$ loops on empty input, $Q$ never accepts anything, so it does not accept 01. Thus $⟨P⟩\in HAL{T}_{\epsilon }⟺⟨Q⟩\in A_{01}$. A decider for $A_{01}$ would decide $HAL{T}_{\epsilon }$ — impossible. So $A_{01}$ is undecidable. ∎ (This is a hand-built instance of what Rice's Theorem proves in general.)

A reduction $A\le B$ transfers decidability from $B$ to $A$ (if $B$ decidable then $A$ decidable), and undecidability from $A$ to $B$. To conclude $B$ undecidable you reduce a known-undecidable $A$ into $B$ (i.e. $A\le B$ with $A=HALT$). Reducing $HALT$ into a decidable $L$ is impossible in the first place — you can never actually build such a mapping, because it would make $HALT$ decidable, which it isn't. The student is assuming the very thing that cannot exist. Direction is everything.

Build:

G():                        # G takes no useful input; call G on ⟨G⟩
    if T(⟨G⟩) == YES:       # T predicts G halts on its own code
        loop forever
    else:
        halt

Run G on $⟨G⟩$:

• If G halts on its own code → the else ran → T(⟨G⟩)=NO (T said it doesn't self-halt) — but it did. Wrong.
• If G loops on its own code → the if ran → T(⟨G⟩)=YES (T said it self-halts) — but it looped. Wrong.

Either way T is wrong on the single input $⟨G⟩$, so no correct total T exists. The self-halting language is undecidable — a direct diagonal, no reduction needed.

Line 3 is illegal. There is no single finite $k$ that bounds every halting computation: halting programs can run arbitrarily long (a program can halt after $10$ steps, $10^{100}$ steps, or after Ackermann-many steps). Picking a universal cutoff $k$ would itself require knowing the running times in advance — i.e. deciding halting. Line 3 smuggles in the answer it claims to compute. Everything else is fine; the whole "proof" collapses on that one assumption.

(a) Church–Turing Thesis: it asserts that any effective/mechanical procedure is captured by a Turing machine. Because of it, "no Turing machine decides $HALT$" upgrades to "no algorithm whatsoever — in any language, on any hardware — decides halting." The impossibility is absolute, not Turing-specific. (b) Rice's Theorem: it generalizes the halting result — every non-trivial semantic property of a program's behaviour (does it halt? accept 01? compute a constant?) is undecidable. Halting is the flagship special case; Exercises 4.1–4.2 are hand-built instances of what Rice proves wholesale.

The engine of all of this: $D(D)$ halts $⟺$ $D(D)$ does not halt. If you can rebuild that line and the two-case trace from memory, you own the proof.