Busy Beaver Hall of Fame

Take every Turing machine with $n$ states and two symbols. Start each one on a blank tape. Some halt, some run for ever. Among the ones that halt, which runs longest? That is the whole of the busy beaver game, and it is one of the few questions in mathematics where a child can follow the rules and the answer is still out of reach of every computer that will ever be built.

The game

Tibor Radó posed it in 1962, in a paper called “On non-computable functions”.¹ A machine plays by being started on a blank tape; it scores only if it halts. Radó kept two scores, and they are not the same:

• $S(n)$, the most steps any halting $n$-state machine takes;
• $\Sigma(n)$, the most 1s any halting $n$-state machine leaves behind.

For small $n$ one machine can win both. At three states it cannot, which is why this collection lists two three-state champions. The longest runner takes 21 steps but leaves only 5 ones; the most productive leaves 6 ones but stops after 14 steps. The game rewards two different kinds of cleverness.

Why nobody can compute it

Radó’s point was not the game but what it proves. Suppose some program could compute $S(n)$. Then it could decide whether any $n$-state machine halts: run the machine for $S(n)$ steps, and if it has not stopped by then it never will. But no program can decide that — it is Turing’s halting problem. So $S$ is not computable, and neither is $\Sigma$. Radó showed more: each of them eventually grows faster than every computable function, however fast.

This is why every value of the function has had to be won by hand, one size at a time, and why each has taken longer than the last.

The frontier

Every number in rows two to five of that table is counted by this library: it runs each champion from a blank tape to its halt whenever it builds, and the figures above are the ones it got. The step from four states to five is a factor of about 440,000. The step from five to six is not a factor of anything you could write down: the current six-state champion is known to halt only because its behaviour was analysed by hand and with accelerated simulators. No computer will ever run it to its halt step by step.

BB(2) champion ITM · 2×2 · halts in 6 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(3) champion — most steps ITM · 3×2 · halts in 21 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(3) champion — most ones ITM · 3×2 · halts in 14 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(4) champion ITM · 4×2 · halts in 107 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(5) champion ITM · 5×2 · halts in 47.2M Deterministic Added 28 Sept 2026Updated 28 Sept 2026

Five states, and the proof

The five-state champion was found in 1989 by Heiner Marxen and Jürgen Buntrock, and for the next thirty-five years it was only the best known. The trouble with proving it best was never the champion, which halts: it was the millions of other five-state machines, each of which had to be shown either to halt sooner or to run for ever. In 2024 the bbchallenge collaboration finished that proof and had it checked by computer in the Coq proof assistant.²

The champion itself turns out to be doing arithmetic — iterating a small Collatz-like function until it lands on a number that stops it. Its own page follows that orbit stage by stage.

More symbols

Radó’s game is played with two symbols, but nothing stops you giving a machine more. With two states and three symbols the champion runs for 38 steps; with two states and four, 3,932,964. Set those beside the table above, machine for machine with the same number of rules: two states and three symbols beat three states and two (21 steps), and two states and four symbols beat four states and two (107) by a factor of more than thirty thousand. At these sizes an extra symbol is worth more than an extra state.

Reading further

Scott Aaronson’s survey “The Busy Beaver Frontier” (2020) is the best single place to start, and the bbchallenge website keeps the current state of the problem, including every machine of six states whose fate is still unknown.

1. T. Radó, “On non-computable functions”, Bell System Technical Journal 41 (1962). ↩

2. The bbchallenge collaboration, bbchallenge.org. ↩