The Busy Beaver Problem

Take every Turing machine with n states that eventually halts when started on a blank tape. One of them runs longer than all the rest before it stops. That machine is the busy beaver, and BB(n) is its step count. The function is easy to define and impossible to compute: no algorithm can produce BB(n) for every n.

The game Radó invented

Tibor Radó was a Hungarian mathematician at Ohio State University when he published “On Non-Computable Functions” in the Bell System Technical Journal in May 1962. The paper set up what he called the busy beaver game, played with the simplest computers imaginable.

Picture a paper tape stretching endlessly in both directions, every cell holding a 0. A machine has n internal states, and each state carries two instructions, one for when the head reads a 0 and one for when it reads a 1. An instruction does exactly three things: write a 0 or a 1, move one cell left or right, then either switch to a state or halt. That is the entire machine. The Turing machine, in other words, stripped to two symbols.

Now hold a contest. Start every possible n-state machine on the blank tape. Some run forever; disqualify them. Among the machines that do halt, the one that takes the most steps is the champion, and BB(n) is its score. Radó also tracked a second prize, Σ(n), for the most 1s left on the tape at the finish.

It sounds like bookkeeping. The sting is in the disqualification round. To crown a champion you must prove that every longer-running machine of that size never halts, and Turing had already shown in 1936 that no general method for deciding this can exist. That is the halting problem, and it is the reason the busy beaver game is hard in a way that brute force cannot fix.

The known values

Sixty-four years after Radó’s paper, humanity has five values.

States	BB(n), steps	1s left by the champion	Proved by
1	1	1	Radó, 1962
2	6	4	Radó, 1962
3	21	5	Shen Lin and Radó, 1965
4	107	13	Allen Brady, 1974 (published 1983)
5	47,176,870	4,098	bbchallenge collaboration, 2024

The demo above has all five champions loaded, with their published transition tables. The one-state machine writes a single 1 and stops, which is the best a single state can do. The three-state champion is the oddity of the table: it runs for 21 steps but leaves only five 1s, while a different three-state machine manages six 1s in a shorter run. It is the only size where the endurance record and the tidiness record belong to different machines.

Watch the four-state champion step by step and you can see why these little devices are hard to reason about. It shuttles back and forth, builds up a block of 1s, occasionally erases one, and dies suddenly at step 107 with no visible warning.

Sixty-two years for five numbers

The gap between BB(4) and BB(5) is the story of the problem. In 1989 two German researchers, Heiner Marxen and Jürgen Buntrock, ran an accelerated search over five-state machines and found one that halted after 47,176,870 steps, publishing the find in 1990. Most people who studied the problem believed this was the champion. Believing is cheap. To prove it, someone had to show that among the 181,385,789 essentially distinct five-state machines, every single one that runs longer never halts at all.

Progress crawled for decades. A Bulgarian researcher known as Skelet whittled the holdouts down to a few dozen ferociously difficult machines in 2003, but nobody could finish the list, and unpublished or unverifiable claims piled up around the problem.

In 2022 Tristan Stérin launched bbchallenge.org, an open online effort to settle BB(5) properly. The collaboration that formed around it, more than twenty people, most of them without academic posts, built visualisation tools, split the space of machines into families, and wrote “deciders”, programs that prove whole families non-halting. The house rule was severe: results counted only once they were formally verified in the Coq proof assistant, a system that checks every logical step by machine. On 2 July 2024 the group announced that the proof was complete, roughly 40,000 lines of Coq confirming that Marxen and Buntrock’s machine really is the fifth busy beaver. It was the first new value in over forty years, and the first ever proved to that standard.

Why no algorithm can compute BB

Suppose someone handed you a program that computed BB(n) for any n. You could then settle the halting problem for any machine M with n states: compute BB(n), run M for that many steps, and check. If M is still running past BB(n) steps, it can never halt, because BB(n) is by definition the longest any halting n-state machine survives. Turing proved no such halting test can exist, so no such program can exist either. The busy beaver function is uncomputable, full stop.

The same argument shows something stranger. BB must eventually grow faster than any function you can compute, since a computable function that kept pace with it (or overtook it) would give you the halting test above. Pick any monster a program can produce, the Ackermann function included, and beyond some point BB(n) is bigger. Alan Turing established the ceiling in 1936; Radó’s contribution was a function that makes the ceiling concrete, one integer at a time.

The wall at six states

Those integers get out of hand immediately. BB(6) is unknown, and the known lower bound stopped being a normal number in 2025. In June of that year a pseudonymous bbchallenge contributor called mxdys, the same person who completed the BB(5) Coq proof, showed that the reigning six-state machine runs for more than 2↑↑2↑↑2↑↑9 steps. The double arrow is tetration: 2↑↑9 means a tower of nine 2s, each the exponent of the one below, and here the height of the tower is itself a tower whose height is a tower. There is no way to write the number out in digits; the observable universe has nowhere to put them.

Worse, six states are already enough to encode open mathematics. In June 2024 the collaboration found Antihydra, a six-state machine whose halting depends on the long-run behaviour of a Collatz-like sequence, the family of problems around the Collatz conjecture that has resisted proof since the 1930s. Machines like it are nicknamed cryptids. Unless someone tames them, BB(6) stays open, and it may simply never be known.

Push the state count higher and the game leaves mathematics-as-usual altogether. Scott Aaronson’s 2020 survey reports a 27-state machine, built by a GitHub contributor writing as Code Golf Addict, that halts if and only if Goldbach’s conjecture is false, so the value of BB(27) would settle a question open since 1742. Further out sits a result of Stefan O’Rear, tightened to 745 states by Johannes Riebel in 2023: a machine that halts if and only if the standard ZF axioms of set theory are inconsistent. Assuming those axioms are consistent, they cannot prove the value of BB(745). Somewhere below 745 states, the function slips past the axioms mathematics is built on.

Why it belongs here

Computer science began with a negative result: Turing’s 1936 discovery that some questions about programs have no algorithmic answer. The busy beaver game is that discovery in its sharpest form, a sequence of ordinary whole numbers, each perfectly well defined, that no procedure can list. Five of them took 62 years and a Coq-checked proof by internet volunteers. The sixth may be beyond anyone. When you run the champions in the demo above, you are watching the exact place where computation runs out of road.