Topic · Computation

The Halting Problem

No program can predict every other program.

Alan Turing, 1936. Given a program P and an input x, can we always decide whether P halts on x? Turing said no — and proved it with a self-referential diagonal trick that no machine can dodge. The Explorer runs a handful of toy programs on a small tape so you can watch some terminate, others run forever, and one program — the diagonal D — twist itself into the contradiction Turing wrote down.

Discover the story → Open the Explorer

Step one · The question

Does P halt on x?

Given the source code of a program P and an input x, decide whether P eventually finishes or whether it runs forever. It sounds like something a clever enough analyser should always be able to determine — programs are finite strings of symbols, after all, and a computer can simulate them. David Hilbert, in his Entscheidungsproblem of 1928, asked for exactly such a universal decision procedure. By the mid-1930s Alonzo Church (via the λ-calculus) and Alan Turing (via what we now call Turing machines) were closing in on the same answer from opposite directions.

Step two · Turing's contradiction

Assume halts(P, x), then build D

Suppose, for contradiction, there exists a total computable function halts(P, x) that returns ⊤ when P halts on input x and ⊥ otherwise. Then we can write a new program D(P): compute halts(P, P); if it returns ⊤, loop forever; if it returns ⊥, halt immediately. D is allowed — every step of it is computable by assumption. Now ask: what does halts(D, D) return? If halts(D, D) = ⊤, then by the definition of D the program D loops on input D — so D does not halt on D, contradicting ⊤. If halts(D, D) = ⊥, then D halts on D — contradicting ⊥. Either answer breaks the definition, so no such halts can exist. (Turing 1936, ‘On Computable Numbers, with an Application to the Entscheidungsproblem’.)

Step three · Diagonalisation in disguise

Cantor, Gödel, Turing — the same move

The same trick powers Cantor's diagonal (build a real that disagrees with the n-th listed real in the n-th digit), Gödel's first incompleteness theorem (build a sentence that says ‘I am not provable’), and Turing's halting argument (build a program that does the opposite of what the decider says). Each construction lays the candidates out in a list and reads down the diagonal to forge an object the list cannot contain. The halting problem was the first concrete decision problem to be proved undecidable — the moment the limits of computation became a theorem.

Step four · Why it matters today

Rice's theorem and the practical fallout

Rice's theorem (Henry Gordon Rice, 1953) generalises Turing: any non-trivial semantic property of programs — ‘does it ever return zero?’, ‘does it leak memory?’, ‘is it malicious?’ — is undecidable. Static analysers must therefore approximate: they over-report (false positives) or under-report (missed bugs), never both clean and complete. Compilers time out when optimising, refusing to inline beyond a heuristic. Antivirus engines can never catch all malware in general. Cloud autoscalers cannot promise that a submitted job will halt; they cap CPU time instead. The halting problem is not a curiosity — it is the wall that every program-about-programs eventually hits.

Diagram · the diagonal program D

Whatever H says about D on D, D does the opposite.

Branch ⊤

⇒ D loops forever on D

But H said D halts. Contradiction.

Branch ⊥

⇒ D halts immediately on D

But H said D loops. Contradiction.

Conclusion

Both branches of the assumed halts oracle H break the definition of D. No total computable H can exist. The halting problem is undecidable.

← Back to the atlas

Where you meet it

How and where this technique lives in the world today.

Compilers & static analysis

Modern static analysers (Coverity, Infer, Rust's borrow checker) have to give up perfect precision because non-trivial program properties are undecidable — direct halting-problem consequence (Rice's theorem).

Antivirus

Why no antivirus catches every malware: perfectly detecting hostile programs would solve a variant of the halting problem.

Compute clouds

Cloud autoscalers can never guarantee 'this user job will halt' — they enforce timeouts because deciding halting is impossible.

Education

The canonical introduction to undecidability in every theory-of-computation course on Earth.