1
Undecidable is proved, not unknown
It is not that nobody has found an algorithm. It is that none can exist, and the proof is a page long.
Lesson · Algorithms and Complexity · Limits
Decidability and the Halting Problem
The halting problem is undecidable: no program can determine, for every program and input, whether it terminates. The proof is a diagonal argument and it fits on a page.
DECIDABLE some algorithm always terminates with the right answer
UNDECIDABLE no such algorithm exists — proved, not merely unknown
the HALTING PROBLEM is undecidable (Turing, 1936)
Rice: every nontrivial semantic property is undecidable
The hard limit
Core ideas
What this lesson establishes
Undecidability is a theorem, not a state of ignorance, and its proof uses the same self-reference Logic and Proof excluded from propositions.
2
The proof is Cantor's diagonal argument
Assume the decider exists, build a program that does the opposite of what it predicts, and ask about that program.
3
Rice's theorem generalises it
Every nontrivial question about what a program computes is undecidable, which is why static analysis is necessarily approximate.
The material
The limits of computation
Decidability, the halting problem, the proof, and what follows.
Definition · Decidable
A decision problem is decidable if some algorithm terminates on every input with the correct yes/no answer. Otherwise it is undecidable.
Note what undecidable does not mean. Not "hard", not "exponential", not "nobody has managed it". It means no algorithm exists and none ever will, and the statement is a theorem.
Theorem · The halting problem is undecidable (Turing, 1936)
There is no algorithm H(P, x) that, for every program P and input x, terminates and correctly reports whether P halts on x.
Suppose such an H exists. Build a program D that takes one input P — the source of a program — and does the following: run H(P, P); if H says P halts on input P, then loop forever; if H says P does not halt, then halt immediately.
D is a perfectly ordinary program: it calls H, which by assumption always terminates, and then branches.
Now ask what D does on input D.
If D halts on D, then H(D, D) reported "halts", so by construction D loops forever. Contradiction.
If D does not halt on D, then H(D, D) reported "does not halt", so by construction D halts immediately. Contradiction.
Both cases are impossible, so H cannot exist.
□
The structure is exactly the diagonal argument of “Cardinality and Countability”, in Sets, Relations, and Functions: assume a complete listing or a complete decider, construct the object that differs from every entry, and derive a contradiction. Cantor used it against enumerations of the reals; Turing used it against deciders.
It is also the self-reference “Propositions and Truth Values” in Logic and Proof excluded from propositions, reappearing where it cannot be excluded: programs can take programs as input, and D is applied to itself. That is not a trick, it is what makes computation universal.
Rice's theorem
Theorem · Rice's theorem
Every nontrivial property of the function a program computes is undecidable. "Nontrivial" means some programs have it and some do not.
So all of the following are undecidable: does this program ever output 0? do these two programs compute the same function? does this program ever access an unallocated address? is this code reachable? does this loop terminate?
This is why static analysis tools are necessarily conservative. A compiler warning about unreachable code, a type system, a linter and a verifier all approximate: they may report a problem that does not exist or miss one that does, and Rice's theorem says no tool can do otherwise for every program.
Other undecidable problems
- The Post correspondence problem. Given two lists of strings, can a sequence of indices be found making the concatenations equal? A purely combinatorial question with no algorithm.
- Hilbert's tenth problem. Does a given polynomial equation have integer solutions? Shown undecidable by Matiyasevich in 1970 — arithmetic itself is not fully mechanisable.
- Program equivalence. Do two programs compute the same function? Undecidable by Rice, which is why compiler optimisations are verified by construction rather than by comparison.
The hierarchy
P solvable efficiently
NP verifiable efficiently
NP-complete the hardest in NP
EXPTIME solvable, but exponentially
DECIDABLE solvable eventually
UNDECIDABLE no algorithm exists
The path ends here, and the position is worth stating plainly. Logic and Proof made statements precise; Induction and Recursion gave the technique for proving them; counting, probability, number theory and graph theory built the structures; and this course measured the cost of computing with them. The last two lessons say what cost cannot be paid at all — some problems are intractable, and some are outside the reach of any algorithm whatever.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Recognising an undecidable problem
Ask what is being asked about.
1
Is the question about program behaviour?
"Does it halt", "does it output", "are these equivalent". Rice's theorem makes all such nontrivial questions undecidable.
2
Try reducing the halting problem to it
If a decider for your problem would give one for halting, yours is undecidable too. That is the standard proof technique.
3
Distinguish undecidable from intractable
NP-complete means slow; undecidable means impossible. Different responses are appropriate.
4
Restrict the question until it is decidable
Bounded loops, finite state spaces, restricted languages. Practical verification works by narrowing the question, not by defeating the theorem.
Decidability
Score 0 / 0Choose the answer you can justify.
The proof, in seven lines
Short enough to reconstruct from memory, and worth being able to.
Assume H(P, x) exists and always answers correctly.
Define D(P):
if H(P, P) says "halts": loop forever
else: halt
Ask: does D halt on input D?
D halts on D ⟹ H said "halts" ⟹ D loops. ✗
D loops on D ⟹ H said "does not halt" ⟹ D halts. ✗
Both branches contradict. H cannot exist. ∎
The whole proof rests on D being a legitimate program, which it is: it calls H, which was assumed to be an algorithm, and then branches. Nothing exotic is required, and that is what makes the conclusion so strong.
Common mistakes
1
Reading undecidable as "very hard"NP-complete is very hard. Undecidable means no algorithm exists, and the two call for entirely different responses.
2
Thinking a specific program's halting cannot be determinedMany individual programs are easy to analyse. The theorem is about a general procedure covering all of them.
3
Believing better tools will eventually decide these questionsRice's theorem is a proof. Practical verification works by restricting the question, not by defeating the theorem.
Check your understanding
✓
Finish when you can reproduce the halting proof from memory.
Seven lines: assume the decider, build the contrary program, apply it to itself, and read off both contradictions. It is the sharpest argument on this path and the shortest of the major ones.
Note: Turing's 1936 paper introduced the machine model, proved this result, and established that a single universal machine can simulate any other — the theoretical basis of the stored-program computer. The limits and the possibility arrived in the same paper.