4.6.18 · D5Theory of Computation
Question bank — Halting problem — undecidability proof by diagonalization
Before you start, four pieces of notation this whole bank leans on. Read them once; every question below reuses them.
The picture below is the whole proof in one grid — glance at it now, then revisit it whenever a question mentions "the diagonal".
True or false — justify
Every item: decide true/false, then give the reason — the reason is the real answer.
If a problem is undecidable, then no program can ever answer any single instance of it.
False — undecidable means no one program is correct for all instances; individual instances like "does
print("hi") halt?" are trivially answerable.The halting problem is unsolvable because programs can be arbitrarily long and slow.
False — length and speed are irrelevant; the proof gives
H unlimited resources and still breaks it. The barrier is logical self-reference, not size.is recognizable (semi-decidable).
True — simulate on ; if it halts, say "yes". You'll be correct on every real halting case; you just never say "no", which is exactly why it's recognizable but not decidable.
is not recognizable at all.
False — it is recognizable; the complement (the "loops forever" language) is the one that is not recognizable.
If both a language and its complement are recognizable, the language is decidable.
True — run both recognizers in parallel; exactly one halts with "yes", giving a total decider. This is why recognizable + undecidable forces to be unrecognizable.
The diagonal program D is an illegal or malformed program.
False — if
H existed, D is a plain if calling a subroutine; it's perfectly well-formed. The contradiction lands on H, the only doubtful ingredient.A faster computer or a quantum computer could decide halting.
False — by the Church–Turing Thesis every physical computing model is simulable by a Turing machine, so it inherits the same limit. Speed does not create decidability.
The proof shows most programs' halting is undecidable but the diagonal case is a rare exception.
False — one contradictory instance ( on ) is enough to kill entirely; a total decider must be right on every instance, so a single failure disproves existence.
Because we can build a Universal Turing Machine that runs any program, we can also decide whether it halts.
The empty-input halting problem is easier and might be decidable.
False — via a reduction (hardcode into a program that ignores its input, then asks it to halt on ) deciding would decide ; so it's equally undecidable.
Spot the error
Each line states flawed reasoning; the answer names the exact broken step.
"To decide halting, just run on and report the outcome."
The error: if loops, your simulation never returns, so it never prints "LOOP". A decider must always terminate — this only gives a recognizer.
"D(D) is contradictory, so self-referential programs are forbidden and the puzzle dissolves."
The error: nothing forbids feeding a program its own code — code is just a string. The contradiction points at
H's existence, not at D." returns LOOP, therefore D loops, so the answer is consistent."
The error: if says LOOP,
D takes its else branch and halts — contradicting the LOOP prediction. Every branch flips 's claim."We proved one clever H fails; a differently-designed H might survive."
The error: the construction of
D uses H only as a black-box subroutine — it works against any total H, so no design escapes."Undecidable and unrecognizable mean the same thing."
The error: is undecidable yet still recognizable. Unrecognizable is strictly stronger (e.g. ).
"By Rice's Theorem, every question about programs is undecidable, including whether the source has 10 lines."
The error: Rice's Theorem states that every non-trivial semantic property — one about the language/behavior a program computes, and true of some programs but not all — is undecidable. "Has 10 lines" is a syntactic property of the source text, not of behavior, so Rice's Theorem doesn't apply and it is decidable.
"Diagonalization needs the programs to be finite in number to list them."
The error: diagonalization works precisely on a countably infinite list ; the point (as in Cantor's Diagonal Argument) is that even an infinite list misses
D.Why questions
Why do we assume H exists instead of directly building a decider?
Because it's a proof by contradiction: assuming existence and deriving nonsense forces the assumption false. We never intend
H to be real.Why is D built to do the opposite of H's prediction?
So that
D's behavior on itself disagrees with whatever H claims — this manufactured disagreement is the diagonal flip (see the flipped diagonal in the figure) that no consistent table entry can satisfy.Why can a program legally take its own source code as input?
Because a program is just a finite string , and any string is valid input data — self-reference is data-feeding, not magic.
Why does undecidability of matter for real software questions?
Many practical questions (loop termination, dead code, program equivalence) reduce to halting, so they inherit its unsolvability — a hard ceiling on static analysis.
Why is the argument named after Cantor's diagonal?
Because listing "does halt on ?" as a table and forcing
D to differ from cell mirrors Cantor building a real number differing from every listed one at digit .Why doesn't the existence of a Universal Turing Machine solve halting?
A UTM faithfully simulates; if the simulated program loops, the UTM loops with it, so it can confirm halting but never confirm looping in finite time.
Why is "the impossibility is structural, not a lack of cleverness" the correct takeaway?
The proof never inspects how
H works — brute force, AI, oracle-guided, all fail identically — so no future cleverness can patch a structural contradiction.Edge cases
Is a program that provably always halts (e.g. print("hi")) a counterexample to undecidability?
No — deciding specific programs is fine; undecidability forbids only a single universal method correct for all program-input pairs.
What if H is allowed to sometimes output "I don't know"?
Then it's no longer a decider for the yes/no membership question; a decider must give a definite correct answer, so the relaxed
H doesn't refute the theorem — it just isn't the object under discussion.What if H only needs to be correct on inputs where P actually halts?
That is exactly a recognizer, which does exist (simulate and report halting). The theorem is only about the total, always-halting decider.
Does the proof still work if there are infinitely many programs?
Yes — infinitude is required, not a problem;
D is a single program that must appear somewhere in the infinite list yet contradicts its own diagonal entry.What happens at the "degenerate" instance where the input equals the program itself, ?
That is the pivotal instance: , a statement equal to its own negation — impossible.
Could restricting to programs without infinite loops make halting decidable?
Trivially yes — if every program in your set halts by construction, "does it halt?" is constantly "yes". The undecidability lives in the full set of all programs, including the pathological ones.
Recall One-line self-test before you close
The whole page collapses to one sentence — reconstruct it: ::: A total decider H would let you build D whose behavior on itself contradicts H's own prediction, so H cannot exist — hence is undecidable but still recognizable.