No algorithm can read what a program does

The program that prints itself ended with a two-line proof that no algorithm decides whether an arbitrary program halts: a program that can read its own text asks the supposed decider about itself and does the opposite. That result is usually presented as a single impossibility, about one question. It is much more than that. In 1953 Henry Rice showed that it is the typical case, and that almost every question anyone would want to ask about what a program does is exactly as undecidable. The halting problem is the diagonal argument’s verdict on one question; Rice’s theorem is the verdict on all of them at once, and it belongs with the list that cannot contain itself and the sentence that says it has no proof as a statement about what a sufficiently expressive system cannot know about itself.

Rice’s theorem: let $P$ be any property of the function a program computes — not of its text, but of its behaviour — that some programs have and some do not. Then no algorithm can decide, given a program, whether it has $P$.

The theorem is abstract, and the best way to feel its force is to look at a world small enough that everything in it can be decided, and see what is being lost when the world grows. The smallest interesting world is the set of Turing machines with two states.

A world small enough to decide #

A Turing machine here has a tape of cells holding 0 or 1, a head that reads one cell, and a state, A or B. Its program is a table: for each state and each symbol read, what to write, which way to move, and which state to go into next — A, B, or halt. There are twelve choices for each of the four entries, so $12^4 = 20{,}736$ programs.

Every one of them can be run on a blank tape. Most stop quickly: 6,912 halt at the first step, having been told to. The rest thin out rapidly — 2,304 halt at step two, 384 at step three — and no machine halts later than step six. The 10,952 that have not halted after fifty steps never will; for machines this small that can be proved one pattern at a time, since each is either stuck in a loop of configurations or marching off into blank tape in a way that repeats.

So for two-state machines, “does it halt on a blank tape?” is decidable, and the algorithm is absurdly simple: run it for six steps. Every other question about their behaviour on a blank tape is decidable the same way — run the machine to its end, or to step six, and look.

The number six is the busy beaver number for two states, and it has to be found by exactly this search — no argument predicts it. The census also finds how the halting machines are distributed, and the distribution is steep: a third of all two-state machines halt at the first step, because their table tells them to halt as soon as they read the blank that every tape starts with. Beyond step one the counts fall by a factor of about three each step — 2,304, then 384, then 128 — until the sixteen machines that halt at step five and the forty that halt at step six, which are the machines that use their small tables most cleverly. Nothing in the rules of the game says the tail ends at six; the census is the only proof that it does.

Why the small world does not scale #

The decision method for two states has a number in it — six — and the number was found by searching every machine. For three states the corresponding search covers some sixteen million machines and the longest halting run is 21 steps; for four states it is 107 steps, established in the 1980s. For five states, the answer, 47,176,870 steps, was settled only in 2024 by a large collaboration that had to classify every non-halting five-state machine individually, several of them by proofs as intricate as research papers. For six states the number is not known and is known to be at least a tower of exponentials.

Each step up needs a new search, and the searches do not get easier; they get harder faster than any computable function grows. That is not a failure of effort. If there were an algorithm computing the busy beaver number for every number of states, it would decide the halting problem — run a machine for that many steps and see — and there is no such algorithm. The decidability of each finite world is real, and it does not add up to a method for all of them.

The point is easy to misread, so it is worth stating the other way round. For any fixed number of states there is an algorithm deciding halting on a blank tape — a lookup table listing which machines halt, or equivalently the single number of steps after which anything still running never stops. What does not exist is an algorithm that, given the number of states, produces that table. The census for two states is such a table, and so is the 2024 classification for five. Each finite world is decidable by a different algorithm, and the algorithms cannot themselves be computed from the worlds they decide. Rice’s theorem is a statement about the uniform question, and every finite census, however large, is on the decidable side of it.

Many programs, few behaviours #

Rice’s theorem is about properties of behaviour, and the census shows how different behaviour is from text.

Thousands of different tables do exactly the same thing. Most of their entries are never consulted: a machine that halts at step one reads a single entry of its table, and the other three can be anything. So a question about what a machine does is a question about its behaviour class, and two programs in the same class must get the same answer even though their texts differ in almost every position.

The chart puts a number on the gap between text and behaviour. A machine that reads one entry has three quarters of its program as dead text — entries that could be changed arbitrarily without any effect on a blank tape — and a property of its behaviour must ignore them. For the two-state machines that is easy, because the census shows which entries are read. For machines in general, deciding which parts of a program ever matter is itself a semantic question, and undecidable for the same reason as everything else here: a part matters exactly when the program reaches it, and whether a program reaches a given instruction is the halting problem in disguise.

This is the distinction the theorem draws. A syntactic property is a property of the text — “the table mentions state B”, “the program is shorter than a hundred characters”. Those are trivially decidable: read the text. A semantic property is a property of the behaviour — “halts on a blank tape”, “leaves at least three 1s”, “computes the successor function”. Rice’s theorem says that every non-trivial semantic property is undecidable, for machines in general, even though for the two-state machines every one of them can be settled by running each machine six steps.

The reduction, run on real machines #

The proof of Rice’s theorem is a single construction, and it can be carried out on the census.

Pick any semantic property $P$ that some program has — say, “computes $x + 1$”. Given any machine $M$, build a new program $M'$ that ignores its input $x$, first runs $M$ on a blank tape, and then, if that ever finishes, outputs $x + 1$. If $M$ halts, $M'$ computes $x + 1$ and has the property. If $M$ never halts, $M'$ never outputs anything, and computes the empty function, which does not have it.

So a decider for $P$ would give a decider for halting: to ask whether $M$ halts, build $M'$ and ask whether it has $P$. There is no decider for halting, so there is none for $P$. The same construction works for any property of behaviour that the empty function lacks, with $x + 1$ replaced by any program that has the property; for properties the empty function has, apply the argument to the property’s negation. The two properties excluded — “true of every program” and “true of none” — are exactly the ones the construction cannot use, because it needs one program with the property and one without.

The recursion theorem gives an even shorter proof: a program that can read its own text asks the supposed decider whether it has $P$, and then behaves like a fixed program without $P$ if the answer is yes, and like one with $P$ if the answer is no. Either way the decider is wrong about it. The two proofs are the same idea at different resolutions: the reduction routes the question through halting, and the fixed-point version cuts out the middle step and lets the program contradict the decider directly.

What is lost, concretely #

Rice’s theorem sweeps up almost everything one would like to know about software, and it is worth listing what falls under it, because the list is the reason the theorem matters.

No algorithm decides, for every program, whether it ever divides by zero; whether it computes the same function as another given program; whether it ever writes to a particular file; whether it is a virus, in the sense of copying itself into other programs; whether it terminates on every input; whether its output is always sorted. Each is a property of behaviour, each is true of some programs and false of others, and each is undecidable.

That does not mean these questions cannot be answered for particular programs, or that tools cannot answer them usefully. It means every tool that answers them must, for some programs, give no answer, or give a wrong one. Type checkers, static analysers and verification tools all live inside that constraint: they decide a syntactic approximation of the semantic property — a property of the text that implies the behaviour — and they reject some correct programs, or accept some faulty ones, as the price of always finishing. A type checker that rejects a program because one branch could, in principle, add a number to a string is doing exactly this: it reads the text, finds a pattern that might misbehave, and refuses — even if that branch can never run. The alternative, running the program to see, is what testing does, and it has the opposite weakness: it confirms behaviour on the inputs tried and says nothing about the rest. Between the two lies every practical method for making software trustworthy, and Rice’s theorem is the reason there is no third way that is both complete and certain. The fourteen fractions that list the primes showed how little it takes for a system to compute, and Rice’s theorem is what that power costs.

The half that can be done #

Undecidable does not mean hopeless, and the census shows which half of the halting question survives. If a machine halts, running it long enough will show that it halts; the search only fails to finish when the answer is no. A property like that — one that can be confirmed by finite evidence when it holds, though its failure may never be confirmed — is called semi-decidable, and halting is the standard example.

Which semantic properties are semi-decidable has an exact answer too, the Rice–Shapiro theorem. A property of behaviour can be confirmed by running programs exactly when it is determined by finite pieces of behaviour: when having the property can always be witnessed by finitely many input–output pairs, and anything extending a witness has the property too. “Outputs 7 on some input” qualifies — one run that prints 7 settles it. “Halts on every input” does not, since no finite number of runs can confirm all of them, and “computes exactly the successor function” does not either. The same finite-evidence condition runs through the proof systems that search for refutations: a proof, when there is one, is a finite object that can be found by searching, and the absence of one never is.

So the landscape has three levels. Properties that can be settled either way by finite evidence are decidable, and among semantic properties only the trivial ones are. Properties confirmed by finite evidence when true are semi-decidable. And properties like “halts on every input” are neither: they sit higher in the hierarchy of logical complexity, where the generalised Collatz problem was shown to sit too.

The same wall across mathematics #

Rice’s theorem is about programs, but the programs can be hidden inside questions that look nothing like programming, and then the wall appears in the middle of ordinary mathematics.

A Diophantine equation is a polynomial equation to be solved in whole numbers. Hilbert asked in 1900 for an algorithm deciding whether any given one has a solution; Yuri Matiyasevich completed the proof in 1970, building on work of Martin Davis, Hilary Putnam and Julia Robinson, that none exists — because every program can be encoded as a polynomial that has a whole-number solution exactly when the program halts. A set of square tiles with coloured edges either tiles the plane or does not, and Robert Berger showed in 1966 that no algorithm decides which, by building tile sets that simulate machines; the proof needed tile sets that tile only without ever repeating, the first of the kind the tiles that never repeat describes. And whether two words in a group’s generators name the same element — reading the group drawn as a map — is undecidable for some finitely presented groups, by Pyotr Novikov and William Boone in the 1950s.

In each case the undecidability is Rice’s theorem in disguise: a mathematical object has been built that behaves like a program, and a question about the object is a question about what the program does. That a cellular automaton with one rule can compute is the same discovery, made about a different object.

What the census cannot show #

The figures decide everything about two-state machines by running them, and the theorem is about the impossibility of doing that in general. No finite census can illustrate the impossibility directly: in any finite world, every question has an answer that a lookup table could give. What the census can show is the shape of the difficulty — the gap between the number of texts and the number of behaviours, and the fact that the decision method for this world rests on a constant that only search could find.

The reduction figure is also a demonstration and not the proof. It uses machines whose halting is already known, because it was found by the census, and shows that $M'$ has the property exactly when $M$ halts. The proof’s force is that the construction is uniform — it works for every machine, including ones whose halting nobody knows — and a table of six cases cannot display that. Nor can any figure show the property the reduction relies on most: that building $M'$ from $M$ is itself a simple, mechanical operation on texts. The whole argument turns on that — a hard question about $M'$ is transferred to a hard question about $M$ by a transformation anyone could carry out — and it is invisible in a table of outputs.

Still open: where the undecidable begins #

Rice’s theorem places the undecidability at the level of all programs. The open questions are about where, among small programs, it begins to bite. For two-state machines everything is decided; for five states the halting behaviour of every machine on a blank tape is now known; for six states some machines’ behaviour depends on questions like the Collatz problem that nobody can settle, so the sixth busy beaver number is not known and may never be.

It is also known that for some fixed, moderately small number of states — several hundred, by explicit construction — there are machines whose halting cannot be proved or disproved in the standard axioms of mathematics, because they search for a contradiction in those axioms. Where between six and several hundred that first happens is open, and the five-state result of 2024 is the furthest the frontier has yet been pushed from below. The numbers involved grow faster than anything computable, which is why they are measured, as an ordinal measures a growth rate, by comparison with fast-growing hierarchies rather than by formulas; the busy beaver function outgrows every one of them, and each value that is pinned down is pinned down by a proof about specific machines rather than by any general method.