Here is a machine you could write on an index card: five states, two symbols, a strip of blank tape. Set it running and it works for forty-seven million steps — and then, against every instinct, it stops. No five-state machine that ever stops runs longer. We only proved that in 2024. Add one more state and the truth falls off a cliff we may never see the bottom of.
A Turing machine is the simplest thing that deserves to be called a computer. A tape of cells, each holding a 0 or a 1. A head sitting over one cell. A short table of rules. At each step the machine reads the cell under the head, and its rules — keyed to the symbol it read and the state it's in — tell it three things: which symbol to write, whether to move one cell left or right, and which state to enter next. That's the entire machine. Alan Turing showed in 1936 that this toy, given enough tape, can compute anything any computer can.
Now play a game with it, invented by Tibor Radó in 1962. Fix the number of states — call it n — and allow two symbols. Start on a blank tape (all zeros). Among all the machines with n states that eventually halt, which one runs the longest before stopping? That maximum number of steps is the Busy Beaver number, written S(n). (A sibling, Σ(n), asks instead for the most 1s left on the tape.) The game sounds innocent. It is one of the most dangerous functions in mathematics.
Why dangerous? Because most machines you could write down never halt — they loop, or wander off down the tape forever. The ones that do halt can take a staggeringly long time to get around to it, and there is no general way to tell the two apart by looking. The busy beaver is the record-holder among the finite ones: the longest race that still has a finish line. Nothing here is mine to assert. The machines below run in your browser, from their own rule tables, and stop exactly where I say they stop.
This is the reigning five-state champion, found by Heiner Marxen and Jürgen Buntrock in 1989 and proven optimal only in 2024. Its entire rule table fits in the grid below. Read it like this: 1RB in the row for symbol 0 under state A means "if you're in state A reading a 0: write 1, move Right, go to state B." Z is the halt instruction. Pick a machine, then step it by hand, run it at a speed you can watch — or, for the five-state monster, hit race to halt and watch the step counter spin up to 47,176,870 and stop.
Five states. Two symbols. A blank tape. Forty-seven million steps. Then it stops — and nothing with five states stops later.
Forty-seven million steps is too many to watch one at a time, but a computation has a shape. Below, time runs downward: each row is the tape at one moment in the run (sampled evenly, because there are far more steps than pixels), with brightness showing the density of 1s. For the five-state champion you get a stack of nested arcs — the machine sweeping out across the tape, laying down and partly erasing a field of marks, then resetting and sweeping again, each pass reaching a little further left than the last. That is how a five-line rule manufactures forty-seven million steps out of almost nothing. Draw the portrait of each champion and watch the structure climb with the state count.
Here is everything we know, and where the floor gives out. For one through four states the answer is small and old. For five, it is forty-seven million, and the proof is two years old. For six states, nobody knows the value, and the best anyone can say is a lower bound — and that lower bound is not a number you can write in digits. It is a tower of exponentials. The bars below are on a logarithmic scale (each unit is a factor of ten), so the jump you can see from four to five — a bar more than three times taller — is already a jump by a factor of half a million. The six-state bar cannot be drawn at all.
| n | S(n) — max steps | Σ(n) — max 1s | log₁₀ S(n) |
|---|
You might think the cliff is a temporary embarrassment — that with enough cleverness and compute we'll grind out S(6), then S(7), forever. We won't. Radó proved in 1962 that the busy beaver function is uncomputable: no program can take n and return S(n) for all n. The argument is short and lethal.
Suppose some program BB did compute it. Then I could solve the halting problem — the problem of deciding, for an arbitrary machine, whether it ever stops — which Turing proved in 1936 is impossible. Here's how: to decide whether some n-state machine M halts on a blank tape, I compute S(n), then simulate M for that many steps. If M hasn't stopped by step S(n), it never will — because S(n) is, by definition, the longest any halting n-state machine runs. So BB would hand me a halting-decider, and no such thing exists. Therefore BB cannot exist either.
The same logic shows the busy beaver grows faster than every computable function. Pick any function you can actually program — 2ⁿ, n!, n!!!…!, the Ackermann function, anything — and S(n) eventually overtakes it and never looks back. That is exactly why the bound at six states is a tower of exponentials and the values beyond it are worse: we are climbing a function built to outrun us.
It gets stranger than "hard." For a large but specific number of states, the busy beaver value isn't merely unknown — it is unknowable within standard mathematics. In 2016 Adam Yedidia and Scott Aaronson built an explicit Turing machine that halts if and only if the axioms of set theory (ZFC) are inconsistent. By Gödel's second incompleteness theorem, ZFC — if it is consistent — cannot prove its own consistency, and so cannot prove that this machine runs forever. Their machine has since been shrunk; the current record, due to Johannes Riebel in 2023, is 745 states. So the value of S(745) is independent of the mathematics nearly all working mathematicians stand on: no proof from those axioms can pin it down. Somewhere between 6 and 745, the busy beaver crosses out of the knowable and never returns.
Which makes the 2024 result feel less like a footnote and more like a flag planted at the edge of a continent. An international band of amateurs and academics — the Busy Beaver Challenge — enumerated and classified every five-state machine, and, crucially, checked the whole proof inside the Coq proof assistant, so that the claim "S(5) = 47,176,870" rests not on anyone's word but on a machine that verifies machines. That is the deepest rhyme this page has with the rest of this place: the only honest answer to can this enormous computation really stop exactly here? is to make a second, trusted computation watch the first. Never trust. Verify. The whole site is built on that sentence, and so is the frontier.