The Halting Problem

Can a computer program decide, for any program and any input, whether that program eventually stops or runs for ever? This question is called the halting problem, and Alan Turing proved in 1936 that the answer is no. No algorithm can do it, and no future computer will change that.

That makes this page the odd one out. Every other challenge on this list is open: someone, someday, might crack it. The halting problem is closed, and closed in the strangest way a problem can be. It was not solved. It was proved unsolvable, with the same finality that mathematics proves anything, and that impossibility turned out to be one of the foundations of computer science. The quiz above hands you the decider’s job for five small programs, and the fifth one shows exactly where the trap is.

The question Hilbert asked

The story starts before computers existed. In 1928 the German mathematician David Hilbert, together with Wilhelm Ackermann, posed what they called the Entscheidungsproblem, the “decision problem”. They wanted a definite procedure, a recipe that could be followed without insight or imagination, that would take any statement of formal logic and correctly announce whether it was provable. Hilbert believed such a procedure existed. Finding it would, in a sense, mechanise mathematics.

Two people demolished the hope within months of each other in 1936. Alonzo Church at Princeton did it using a system he invented called the lambda calculus. Alan Turing, a 23-year-old at Cambridge working independently, did it with a paper titled On Computable Numbers, with an Application to the Entscheidungsproblem, received by the London Mathematical Society on 28 May 1936. Turing’s version won the argument for posterity, because on the way to his answer he did something bigger than the question. He defined the computer.

A machine made of paper

To prove that no procedure could exist, Turing first had to pin down what “procedure” means, precisely enough to reason about every possible one. His answer was the Turing machine: an imaginary device with a paper tape divided into squares, a head that reads and writes one symbol at a time, and a small table of rules saying what to do next. That is the whole machine. It sounds like a toy, yet nothing we have built since can compute anything a Turing machine cannot, and that includes every supercomputer on the planet. Every programming language you have heard of is, in this sense, the same machine wearing different clothes. So a proof about what Turing machines cannot do is a proof about what software cannot do, full stop.

One more of Turing’s observations matters here: a machine’s rule table can be written out as symbols on a tape. Programs are data. A program can therefore be fed to another program as input, which is exactly the move the proof needs. As it happens, Turing never used the phrase “halting problem” himself; his paper works with a closely related question about machines that print, and the now-standard name and framing came from later textbooks. The logic below is the modern telling of his argument.

The contrarian program

Here is the proof, and it fits in four steps. No algebra required.

Suppose somebody claims to have written the impossible program. Call it H. You give H any program plus that program’s input, and H always answers, correctly and in finite time, either “halts” or “runs for ever”. H never hedges and never gets stuck.

Now I write a short, spiteful program called D. When D is given the code of any program P, it asks H a single question: “Would P halt if it were run with its own code as input?” Then D does the opposite of whatever H predicts. If H says P would halt, D deliberately enters an endless loop. If H says P would run for ever, D immediately stops.

The killer move: run D with its own code as input. Now H must answer the question “does D halt when fed D?”, and both answers destroy it. If H says “halts”, then D, by its own construction, loops for ever, so H was wrong. If H says “runs for ever”, D promptly stops, so H was wrong again. A program that is always right about halting is wrong about D. The only way out of the contradiction is that H never existed in the first place.

The trick is called diagonalisation, and it is the same self-reference weapon Georg Cantor used in 1891 to show that some infinities outsize others. Notice what the proof does not say. It does not say halting is hard to predict, or that we lack the computing power. It says the predictor’s existence is logically contradictory, like a square circle. That is why the status line on this page will never need updating.

Not a party trick

It would be easy to file this under mathematical curiosities. The trouble is that the impossibility spreads. In 1951 the American logician Henry Gordon Rice proved a brutal generalisation, published in 1953 and now called Rice’s theorem: every non-trivial question about what a program does, as opposed to what its text looks like, is undecidable. Does this program ever crash? Does it ever print a password? Does it compute the same results as that other program? Is this code malware? Each of these is the halting problem in a costume.

The practical fallout is everywhere. Antivirus software cannot decide, in general, whether a file behaves maliciously, which is why detection leans on signatures and heuristics and why the arms race with malware authors never ends. An optimising compiler cannot reliably identify all dead code, so it settles for the cases it can prove. Program verification cannot be fully automated for arbitrary software. And your IDE, however smart its analysis engine gets, will never be able to warn you about every infinite loop, because a perfect infinite-loop detector would be H, and H cannot exist.

How software lives with it

Undecidability sounds paralysing. In practice engineers route around it, and the escape hatches are worth knowing.

The bluntest one is the timeout: give up predicting and just pull the plug. Web servers kill requests that run too long, and your operating system lets you force-quit a frozen app. The question of whether the program would have finished goes unanswered, but nothing hangs for ever either.

A subtler hatch is to shrink the language. Turing’s proof needs programs powerful enough to loop indefinitely, so languages that forbid unbounded loops escape it. Regular expressions in their classic form always finish. The Linux kernel accepts user-supplied eBPF programs only after a verifier checks they must terminate, which is possible precisely because eBPF is deliberately not a full programming language. Proof assistants such as Coq and Lean insist that every function provably terminates before they accept it.

The third hatch is to give up on “all programs” and verify one program at a time, with humans and machines constructing the proof together. The seL4 microkernel and the CompCert C compiler were verified this way. The halting problem forbids a universal button; it says nothing against patient, program-by-program effort.

The same wall, seen from two other pages

Two of the open problems on this list are really the halting problem viewed from other angles. The Collatz conjecture asks whether one specific five-line loop halts for every starting number, and after nearly a century nobody can decide even that single family. Undecidability does not prove Collatz is hopeless, since one program’s halting can be settled without a universal decider, but it explains why no general-purpose machinery exists to settle it for us. The busy beaver problem is the quantitative face of the same wall: it asks for the longest any halting n-state Turing machine can run, and Tibor Radó proved in 1962 that this function grows faster than anything computable. If you could compute busy beaver values, you could solve the halting problem, so you cannot.

The quiz’s fifth program earns its place here. It searches for an odd perfect number and stops if it finds one. Whether it halts is a genuine open question in mathematics, unresolved since antiquity, so a working halting decider would settle it instantly, along with Goldbach’s conjecture and every other question of the form “does this search ever succeed”. One box cannot contain that many answers.

Gödel, briefly

Five years before Turing’s paper, Kurt Gödel proved that any consistent formal system rich enough for arithmetic contains true statements it cannot prove. The two results are siblings, and the halting problem gives the cleaner path to Gödel’s. If some proof system could prove or refute every statement of the form “program P halts on input x”, you could build H by searching through all possible proofs until one settles the question. H cannot exist, so no such system can exist either. There will always be true facts about programs that sit beyond proof.

Hilbert wanted a mathematics with no unanswerable questions. What he got instead was a precise definition of the computer, delivered inside the proof that some questions stay open for ever. Not a bad consolation prize.