Halting problem — undecidability proof by diagonalization: Worked examples

This page is the exhaustive drill room for the Halting Problem — Undecidability by Diagonalization. The parent proved one result: no total program decides $H A L T$ . Here we walk every kind of situation that idea can appear in — the self-referential core, the "just simulate it" trap, degenerate programs, reductions, and exam twists — so you never meet a case you haven't already seen.

Before we start, three plain-word reminders (every symbol earned):

We write $⟨ P, w ⟩$ for "the pair (program $P$ , input $w$ ) packaged as one string," and $H A L T = {⟨ P, w ⟩ ∣ P halts on w}$ . Prerequisites live at Turing Machines, Decidable vs Recognizable Languages, and Cantor's Diagonal Argument.

The scenario matrix

Every halting-problem situation you can be asked about falls into one of these cells. The examples below hit all of them.

Cell	Scenario class	What makes it tricky	Example
C1	Concrete program that obviously halts	Shows "some" cases are trivially decidable	Ex 1
C2	Concrete program that obviously loops	Same, opposite sign	Ex 1
C3	"Just simulate and watch" attempt	Fails only in the loop case → semi-decidable	Ex 2
C4	The self-referential diagonal $D (D)$	Both branches contradict	Ex 3
C5	Degenerate decider: $H$ always says `HALT`	A "trivial" $H$ is wrong on a looper	Ex 4
C6	Degenerate decider: $H$ always says `LOOP`	Wrong on a halter	Ex 4
C7	Reduction: empty-input halting	Transfers undecidability	Ex 5
C8	Reduction: does $P$ ever print `7`?	Rice-flavoured property	Ex 6
C9	Word problem (real-world "will it end?")	Translating English → $H A L T$	Ex 7
C10	Exam twist: "recognizable but not decidable?"	Sign of asymmetry between YES and NO	Ex 8

Worked examples

Worked example Example 2 — Cell C3: "simulate and watch" is only half a decider

Statement. Proposed decider S(P,w): simulate $P$ on $w$ ; when it stops, print HALT. Does S decide $H A L T$ ?

Forecast: guess whether S is (i) a full decider, (ii) a semi-decider, (iii) neither.

When $P$ halts on $w$ : the simulation eventually stops, S prints HALT. Correct. Why this step? Confirms S handles the YES side perfectly.
When $P$ loops on $w$ : the simulation also loops. S never reaches a print. It never says LOOP. Why this step? This is the exact spot a decider is forbidden to be — running forever with no output.
So S says HALT correctly but can never say LOOP. It is a semi-decider (recognizer), not a decider. Why this step? Names the property: $H A L T$ is recognizable (see Decidable vs Recognizable Languages) yet undecidable.

Verify: A decider must always halt. S fails that on every looping input, so it is not a decider — consistent with the impossibility theorem. (It did satisfy the theorem's escape hatch: recognition is allowed.)

Worked example Example 3 — Cell C4: the diagonal

$D (D)$ , both branches Statement. Assume a true decider H(P,w) exists. Build

D(P):
    if H(P, P) == HALT: loop forever
    else:               halt

Trace D(D) in both cases and locate the contradiction. Use the figure.

Forecast: guess which case (halts / loops) escapes contradiction. (Trap: neither does.)

Case A — suppose D(D) halts. Halting means the else branch ran, which needs H(D,D)=LOOP, i.e. $H$ predicted D(D) loops. But we supposed it halts. Contradiction. Why this step? We read the code backwards from the observed behaviour to what H must have said.
Case B — suppose D(D) loops. Looping means the if branch ran, needing H(D,D)=HALT. But we supposed it loops. Contradiction. Why this step? The mirror sign; every possibility is now covered.
Combine: $D (D) halts ⟺ H (D, D) = LOOP ⟺ D (D) loops$ . A statement equal to its own negation. Why this step? This is the " $x ⟺ \neg x$ " core — impossible, so $H$ cannot exist.

Verify: In the figure's diagonal table, row $D$ / column $D$ is the one cell D was engineered to flip. D disagrees with every program at its own diagonal cell, so D cannot equal any listed program — yet every program is listed. The list-vs-not-list clash matches Cantor's Diagonal Argument. ✓

Worked example Example 4 — Cells C5 & C6: what if

$H$ is a lazy constant answerer? Statement. Students often "solve" halting with a shortcut. Test two shortcuts: (a) H_yes(P,w) = always HALT. (b) H_no(P,w) = always LOOP. Find one input where each is wrong.

Forecast: guess a counterexample for each before reading.

H_yes on P2 = while True: pass: H_yes says HALT, but P2 loops. Wrong. Why this step? A constant YES decider dies the instant it meets any real looper (C2 from Ex 1).
H_no on P1 = print("hi"): H_no says LOOP, but P1 halts. Wrong. Why this step? A constant NO decider dies on any real halter (C1).
Neither constant is total-correct, so neither is a decider. Why this step? Rules out the "obvious" degenerate escape routes explicitly.

Verify: Both counterexamples come from Example 1, whose answers we already fixed (HALT, LOOP). A single wrong output disqualifies a claimed decider — a decider must be correct on every instance. ✓

Worked example Example 5 — Cell C7: reduction to empty-input halting

Statement. Prove $H A L T_{ε} = {P : P halts on empty input}$ is undecidable, using $H A L T$ .

Forecast: guess what small program you'd build from $⟨ P, w ⟩$ .

From any $⟨ P, w ⟩$ , build $P_{w}$ : "ignore your input; set the string to the fixed $w$ ; run $P$ on $w$ ." Why this step? We bake $w$ into the code so the input no longer matters — turning a general question into an empty-input question. This is a mapping reduction.
Observe: $P_{w}$ halts on empty input $⟺ P$ halts on $w$ . (They run the exact same computation.) Why this step? The equivalence is what makes the reduction correct.
If some decider $E$ solved $H A L T_{ε}$ , then $E (P_{w})$ would decide $⟨ P, w ⟩ \in H A L T$ — deciding $H A L T$ . Why this step? Chains the impossible: a solver for the new problem would solve the old, forbidden one.

Verify: We assumed nothing about $E$ except totality, and derived a decider for $H A L T$ — impossible by the parent theorem. So $E$ cannot exist. ✓

Worked example Example 6 — Cell C8: "does

$P$ ever print 7?" Statement. Show $P R I N T 7 = {P : P prints 7 at some point on empty input}$ is undecidable.

Forecast: guess the gadget program you'd wrap around $P$ .

From $⟨ P, w ⟩$ build $Q$ : run $P$ on $w$ ; if and when it halts, print(7). Why this step? We make "prints 7" a stand-in for "halts": the print only ever fires after $P$ finishes.
Then $Q$ prints 7 $⟺ P$ halts on $w$ . Why this step? Establishes the reduction equivalence, same shape as Ex 5.
A decider for $P R I N T 7$ would decide $H A L T$ via $Q$ — impossible. This is the flavour of Rice's Theorem (non-trivial semantic properties are undecidable). Why this step? Connects the one-off trick to the general theorem.

Verify: $Q$ never prints 7 while $P$ loops, and prints exactly once when $P$ halts, so the " $⟺$ " is exact. Reduction from undecidable $H A L T$ ⇒ $P R I N T 7$ undecidable. ✓

Worked example Example 7 — Cell C9: real-world "will my crawler ever finish?"

Statement. A company asks: "Write a tool that, given any web-crawler script and a start URL, guarantees whether the crawl terminates." Should you promise it?

Forecast: guess YES (deliverable) or NO (impossible).

Translate: crawler = program $P$ , start URL = input $w$ , "terminates" = halts. The ask is a decider for ${⟨ P, w ⟩ : P halts on w}$ = $H A L T$ . Why this step? English → formal language; only then can theory bite.
That is exactly $H A L T$ , proven undecidable. Why this step? Recognise the disguise.
Do not promise a general tool. You can promise: a checker that (a) confirms termination when it happens (semi-decider, Ex 2), or (b) works for a restricted crawler subclass with bounded loops. Why this step? Turn an impossible spec into an honest, shippable one.

Verify: A universal guarantee = deciding $H A L T$ = impossible. The fallback tools sidestep the theorem by dropping "for all programs" or "always halts." ✓

Worked example Example 8 — Cell C10: the recognizability exam twist

Statement. True/False, with justification: " $H A L T$ is undecidable, therefore it is also not recognizable."

Forecast: guess T or F.

From Ex 2, the simulator S recognizes $H A L T$ : it says HALT on every genuinely-halting instance. Why this step? Recognizability only needs the YES-side to eventually accept; NO-side may loop.
So $H A L T$ is recognizable, despite being undecidable. Why this step? Decidable ⇒ recognizable, but not the reverse. The statement conflates the two.
Answer: False. (For contrast, the complement $\overline{H A L T}$ is not recognizable — you can't confirm "loops forever.") Why this step? Pins the asymmetry: YES is confirmable, NO is not, which is precisely why decidability fails.

Verify: Decidable $=$ recognizable and co-recognizable. $H A L T$ is recognizable but not co-recognizable, so it's undecidable — fully self-consistent, statement is False. ✓

Recall Quick self-test across the matrix

Which cell: "H that outputs HALT for everything"? ::: C5 — a degenerate always-YES decider, wrong on any looper. Why is "simulate and report" not a decider? ::: C3 — on a looping input the simulation never halts, so it never outputs LOOP. What does building $P_{w}$ (hardcode $w$ , ignore input) achieve? ::: C7 — reduces $H A L T$ to empty-input halting, transferring undecidability. Is $H A L T$ recognizable? ::: C10 — yes; the simulator accepts all halting instances, so recognizable but not decidable. In $D (D)$ , which cell of the program×input table does $D$ flip? ::: C4 — the diagonal cell (D, D), forcing $x ⟺ \neg x$ .