The machines that need a reason never to stop

No algorithm can read what a program does ran every Turing machine with two states and found that the question “does it halt on a blank tape?” is easy for them: no halting two-state machine runs longer than six steps, so running each one for six steps settles everything. The essay ended with the numbers for larger machines — 21 steps for three states, 107 for four, 47,176,870 for five, settled only in 2024 — and with the observation that each of those numbers was found by a search harder than the last.

This essay runs the three-state search, and the surprise is where its difficulty lies. Finding the machines that halt is easy: run each one, and the halters stop. The difficulty is entirely in the machines that do not halt, because “has not halted yet” proves nothing, and the record of 21 steps is only established when every one of the others has been given a reason it will never halt. The reasons come in kinds, and the census below counts how many machines each kind settles — and how many it leaves over.

Which machines are worth running #

A three-state machine on a tape of 0s and 1s has a table with six entries, one for each of the states A, B and C and each symbol it might read. Each entry says what to write, which way to move and which state to enter next, or says halt. Written out in full there are millions of such tables, but most are the same machine in disguise: renaming B and C changes nothing, and an entry the machine never reaches from a blank tape can be anything at all without changing what happens.

The census therefore builds the machines the way they run. It starts with an empty table and a blank tape, with the first entry fixed — write 1, move right, go to B, which every interesting machine can be arranged to begin with. It runs the machine until it reaches an entry that has not been filled, and at that moment branches: the entry becomes halt, or any of the possible write–move–state combinations, with new states named in the order they are first used. Each branch is run on, and branches again when it next reaches an empty entry. A machine that halts, or that runs three thousand steps without reaching an empty entry, is a leaf. This is the tree normal form, and it produces 16,549 three-state machines, each a genuinely different behaviour from a blank tape.

The same construction for two states gives 121 machines, 15 of which halt — the census of the earlier essay, reached this time without listing all 20,736 tables. The arithmetic of the reduction is part of the point: almost all of the raw tables are irrelevant to the question, and only by running them can the relevant ones be found.

The halters, and two records held by different machines #

The halting machines are the easy part. 1,379 of the three-state machines halt, at steps from 2 to 21, and the distribution has a peak at seven steps and a long thin tail. A single machine runs for 21 steps: in the order of its six entries — A reading 0, A reading 1, B reading 0, and so on — it is 1RB 1RZ 1LB 0RC 1LC 1LA, where 1RZ means “write 1 and halt”. It leaves five 1s on the tape.

The busy beaver problem asks two questions, and three states already separate them. The most steps any halting machine takes is 21; the most 1s any halting machine leaves is six, and the machines that leave six halt sooner than 21 steps. The two records, steps and marks, are held by different machines, which is a small sign that “the most a machine of this size can do” is not one quantity. Both numbers have the same status, though. Each is the largest value among the halting machines, and it is a record only once every non-halting machine has been shown never to halt — a machine still running after 21 steps might halt at step 22 with seven 1s, unless something says it will not.

Four reasons a machine never stops #

The 15,170 machines that do not halt in three thousand steps are sorted by four checks, applied in turn. Each is a proof, not a test: a machine it settles provably never halts.

No halting entry. Most of the non-halters are settled before they are run, because their tables have no halting entry left: the tree filled every entry with a move. A machine that has no instruction to halt cannot halt, and 12,492 machines are settled this way. They are the bulk of the census and the dullest part of it.

An exact repeat. If the whole configuration — state, head position and every cell of tape — returns to one it has been in before, the machine is in a loop and will go round it for ever. Recording every configuration for the first few hundred steps finds 361 such cyclers, the second panel of the figure being one: the head shuffles over two cells and the tape never changes again.

A repeat, shifted. A machine can repeat without returning to the same place. The third panel walks steadily to the right, writing as it goes, and its pattern repeats one stretch further along each time. That too is provable, and the next section draws the proof. This check settles 2,254 machines, the translated cyclers.

Every way back dies. The fourth check works backwards. A machine halts only by reaching its halting entry, which means being in a particular state and reading a particular symbol. Ask what configuration could have led there one step earlier, and what could have led to that, keeping track of what the tape must have held at each cell visited. If every such backward history dies out after a few dozen steps — reaching a configuration that no instruction can produce — then the halting entry is unreachable, and the machine never halts. This settles 36 machines that the first three checks miss. Because a backward search could in principle make a mistake that a forward one cannot, it is checked against every halting machine: run on each of the 1,379, it must report the halting entry reachable, and it does every time.

A repeat that walks #

The shifted-repeat proof is worth seeing on one machine, because its logic is the same as an ordinary repeat with one extra observation. At step 12 the head of the machine in the figure is further right than it has ever been, in some state, with certain cells immediately behind it. At step 18 the same is true again: further right still, the same state, the same cells behind it. To the right of the head at both moments there is nothing but blank tape, because the head has never been there. And between steps 12 and 18 the head never went back past the cells outlined.

Those facts are enough. Everything the machine did from step 12 to step 18 depended only on its state, the outlined cells and the blank tape ahead, because it never looked at anything else. At step 18 it has the same state, the same cells and the same blank tape ahead, so it will do the same thing again, shifted, arriving at step 24 in the same situation once more — and so on for ever. A machine in that situation cannot halt, and the proof needs only two rows of its run and the record of how far back the head went between them. The check looks for exactly this pattern at every moment the head reaches a new extreme, on either side.

The twenty-seven left over #

After the four checks, 27 three-state machines remain. None has halted, and none is a cycler, a translated cycler or refutable backwards within the limits used. The fourth panel of the traces is one of them, and its behaviour is easy to describe and hard to capture in a check: it sweeps right across its tape, turns, sweeps left across the whole tape again, and each sweep is a little longer than the last. Nothing ever repeats, exactly or shifted, because the stretch it covers keeps growing.

Run for 200,000 steps, none of them halts, and their growth sorts them into two families. Twenty-five visit a stretch of tape that grows like the square root of the time: they are bouncers, crossing their whole tape on each sweep and adding a cell at the end, so a tape of width $w$ costs about $w^2$ steps to build. The other two grow like the logarithm of the time — squaring the number of steps roughly doubles the width — which is the signature of a binary counter, a machine that increments a number written on its tape in binary and lengthens it by one digit each time it overflows.

Each family needs its own kind of proof, and each proof is an argument about the whole growing pattern: that a sweeper at width $w$ produces a sweeper at width $w + 1$ in a predictable number of steps, or that a counter’s tape at each moment is a binary numeral followed by a fixed tail. Such arguments are routine for a person who has looked at the run, and they are what Shen Lin and Tibor Radó supplied by hand in 1965 for the few dozen three-state machines their computer search left unsettled — which is how $S(3) = 21$ was proved, three years after Radó had defined the problem.

Why five states needed a collaboration #

The pattern of the three-state census is the pattern of the whole busy beaver problem, magnified. At every size, finding the halters is easy and settling the rest is the work. At every size, a few simple kinds of check settle most machines, and a residue is left that needs a new idea. For four states Allen Brady settled the residue in 1983, and $S(4) = 107$. For five states the residue left by every known check numbered in the thousands, and the collaboration that established $S(5) = 47{,}176{,}870$ in 2024 settled it with a dozen deciders of increasing cleverness — finite automata that recognise the tape patterns a machine can produce, backward searches, bouncer and counter recognisers — and a few individual machines whose non-halting needed proofs as long as research papers. The whole proof was then checked by a computer proof assistant, so that the census itself, and not just its conclusions, is verified.

Each new size has needed new kinds of argument, and there is a theorem behind that. If a fixed collection of checks settled every machine of every size, it would be an algorithm for the halting problem on blank tapes, and the theorem that no algorithm reads what a program does says there is none. So the residues cannot be eliminated by any one method. They are where undecidability shows itself in a finite world: not as a machine that cannot be settled — every machine of a fixed size can be settled by somebody — but as the impossibility of settling them all in the same way.

How small a machine can compute anything #

The residue has a counterpart at the other end of the question. Instead of asking how long a small machine can run before stopping, ask how small a machine can be and still run any program at all — be universal, able to simulate any other machine given a suitable description on its tape. Universal machines are where undecidability comes from, since a universal machine’s halting problem contains every other machine’s, and the smallest known ones are tiny. Machines with two states and three symbols, or with about fifteen states and two symbols, have been proved universal, under conventions about how the input is written; the most famous one-dimensional example is the elementary cellular automaton of the rule that computes, whose universality was the key to proving several of the smallest universal Turing machines universal.

So the region where the census is easy and the region where universality begins are not far apart, and the three-state residue sits between them. Its sweepers and counters are not universal — they are too regular for that — but they are already machines whose behaviour is described by an argument about growing patterns rather than by a finite check. The same transition happens in every exhaustive search that grows with its parameter: counting the Latin squares of each order is easy at order five and a research effort at order eleven, and ruling out a projective plane of order ten took years of computer time and a proof that the search itself was correct. The busy beaver search has the same shape, with the difference that there is a theorem saying the difficulty can never level off.

Machines that encode questions #

The residue grows harder than any computable function grows, and for six states it already contains machines whose behaviour is equivalent to open problems. Some six-state machines halt exactly when a certain sequence defined by a Collatz-like rule reaches a particular value, and whether it does is not known. Those machines are not undecidable in any absolute sense — each either halts or does not — but deciding them would solve a problem of the same character as the Collatz problem, which fourteen fractions that list the primes showed is exactly the kind of problem that becomes undecidable when generalised.

Further up, the search runs into mathematics itself. Explicit machines with a few hundred states are known that halt if and only if the standard axioms of set theory are inconsistent; their behaviour cannot be proved within those axioms, so neither can the busy beaver value for that many states. Between six states, where open problems appear, and a few hundred, where independence is guaranteed, the boundary is not known. The growth rates involved are measured, as an ordinal measures a growth rate, against fast-growing hierarchies, and the busy beaver function eventually outgrows all of them.

What the census does not show #

The census settles every three-state machine except the 27, and for those it shows only that they run for 200,000 steps without halting and that their tapes grow in two recognisable ways. That is evidence and not proof. The proofs exist — the value $S(3) = 21$ is established — but they are not carried out here, and a reader should treat the 27 as the place where this census hands over to arguments of a different kind.

The checks themselves have limits that the figures do not display. The exact-repeat check looks only at the first few hundred steps, the shifted-repeat check compares only a fixed window of cells behind the head, and the backward search gives up after a fixed depth. A machine missed by a check with these limits might be settled by the same check with larger ones, and some of the 27 may be; the counts in each class depend on the limits, while the soundness of each class does not.

Still open: the sixth number #

The value of the busy beaver function for six states is not known. Machines have been found that run for more than a tower of exponentials of steps before halting, so the value is at least that large, and among the six-state machines that have not been settled are several whose behaviour reduces to Collatz-like problems. Whether $S(6)$ will ever be determined is open, and some of those working on it expect that it will not be in any foreseeable time.

Smaller questions remain open at every size where a census has been done, and they concern the checks rather than the machines. Is there a natural, small collection of kinds of argument that settles every five-state machine — rather than the dozen deciders and individual proofs actually used? How large must the residue be at six states, for any collection of checks of a given complexity? The busy beaver problem measures, size by size, how much new reasoning a finite question can demand, and the measurement has only been carried out four times.