The Busy Beaver sequence begins modestly: 1, 4, 6, 13. Numbers you could write on a napkin. Numbers a child could count, given patience. Then comes BB(5) = 4,098—modest enough—but the champion machine that produces it runs for 47,176,870 steps. And then the lights go out. Not gradually, not in the way that large numbers shade into incomprehensibility—at a specific, finite point, the sequence becomes unknowable. The boundary between the computable and the uncomputable is not a vague philosophical horizon. It is not an asymptotic limit approached but never reached. It has an address. We have just barely managed to read it.
What follows is about that boundary. About the simplest question in mathematics that opens onto the hardest. About a function that starts by counting and ends by encoding the limits of all formal thought. And about the number 4,098—probably the last exact value of this function that anyone, human or machine, will ever determine.
The game is simple enough to state on a single line. Take a Turing machine with n states, a two-symbol alphabet (0 and 1), and a blank tape stretching to infinity in both directions. Every cell is 0. The machine reads the cell under its head, consults its state table, writes a symbol, moves left or right, and transitions to a new state—or halts. That is all. The rules are grade-school simple: read, write, move, repeat.
Now ask: among all possible n-state machines that eventually halt, which one writes the most 1s on the tape before stopping? Call that maximum BB(n). The Busy Beaver function. A function defined not by a formula but by a competition—a tournament among every possible machine of a given size, where the winner is the one that does the most work before falling silent.
The conceptual simplicity is seductive. A finite number of states. A finite number of possible transition tables. A finite tape at any moment. Everything about the setup screams computability, decidability, the well-behaved world of finite combinatorics. You could, in principle, enumerate every n-state machine. You could run each one. You could watch which ones halt and count their output.
Except you cannot. Because to determine which machines halt, you need to solve the Halting Problem, and the Halting Problem is undecidable. The finitude of the setup is a trap. The question looks bounded but opens onto the infinite, because a machine that has not yet halted after a billion steps might halt at step one billion and one, or never. Patience alone cannot resolve the question. No amount of waiting is enough, because no amount of waiting tells you that waiting longer would be futile.
The known values trace a trajectory from the mundane to the vertiginous.
BB(1) = 1. A single-state machine writes a single 1 and halts. There is almost nothing to say.
BB(2) = 4. Already you must be slightly clever. The champion two-state machine writes four 1s in six steps—maximum output for the simplest non-trivial case. A small puzzle, solvable by hand.
BB(3) = 6. The champion three-state machine writes six 1s in fourteen steps. Lin and Radó proved this in 1965, when the Busy Beaver problem was only three years old. The proof required checking every three-state machine and showing that each one either halted (and produced at most 6 ones) or ran forever. Tractable, if tedious.
BB(4) = 13. Here the difficulty sharpens. The champion four-state machine runs for 107 steps. The proof, completed by Brady in 1983, required classifying every four-state machine—and some of them resist classification badly. Machines that run for thousands of steps before halting. Machines whose behavior appears chaotic, purposeless, interminable—and then they stop. The gap between “has not halted yet” and “will never halt” is already, at four states, a chasm that demands real mathematical argument to cross.
Then BB(5) = 4,098. But the number that staggers is the step count: the champion five-state machine takes 47,176,870 steps to produce those 4,098 ones.
The jump is not merely large. It is a qualitative transformation. Nearly fifty million steps to write four thousand ones. It was discovered by Heiner Marxen and Jürgen Buntrock in 1989, and for thirty-five years it sat as a conjecture: the best known, but unproven champion. To prove it, you would need to classify every possible five-state Turing machine. There are tens of millions of them. And the hard ones—the “holdouts”—are machines that resist every standard technique for proving non-halting.
The proof came in 2024, through the Busy Beaver Challenge—an extraordinary collaborative effort organized by Tristan Stérin and hosted at bbchallenge.org. The approach was proof by exhaustion, but exhaustion of a particular kind: not brute-force computation, but formal verification in Coq. Every five-state machine was classified as either halting or non-halting, and each classification was backed by a machine-checked proof.
The easy cases fell quickly. Most five-state machines either halt within a few thousand steps or fall into obvious loops. But a stubborn residue remained—machines that run for millions of steps without halting, whose behavior has no apparent pattern, whose non-halting is mathematically true but not obviously provable. For these holdouts, the community built “deciders”: automated proof strategies, each targeting a specific class of difficult machine behavior. Machines with exponentially growing counters. Machines with nested loops. Machines with behavior so complex that recognizing the underlying structure required new mathematical ideas.
One by one, the holdouts fell. Each decider resolved a batch; each batch revealed the next layer of difficulty. It took years. The final proof is not a single argument but an ecosystem of arguments, a cathedral of case analysis, every stone verified by machine. BB(5) = 47,176,870. Proven. Settled. The last light before the dark.
Why does the Busy Beaver function grow so fast? Not just faster than exponential—faster than any computable function. Faster than tower functions, faster than the Ackermann function, faster than any function you can name, because any function you can name is computable, and BB outgrows them all.
The proof is one of those arguments that feels, when you first encounter it, like watching someone pull a rabbit from an empty hat. Suppose BB were computable. Then there exists a program that, given n, outputs BB(n). Now consider any Turing machine M with n states. Run M for BB(n) steps. If it has not halted, it never will—because BB(n) is the maximum number of steps any halting n-state machine takes, so any machine still running after that many steps must run forever. We have just solved the Halting Problem for n-state machines. Do this for all n, and we have solved the Halting Problem entirely.
But the Halting Problem is undecidable. Turing proved this in 1936. So our assumption—that BB is computable—must be false.
The beauty of the argument is that it does not merely show BB is hard to compute. It shows BB is impossible to compute. Not hard in the way that factoring large numbers is hard. Not hard in the way that protein folding or weather prediction is hard. Hard in the way that contradictions are hard—the assumption leads to logical impossibility. BB grows faster than every computable function because if it did not, computation itself would be more powerful than it is.
Here is where the Busy Beaver function stops being a curiosity and becomes something philosophically unsettling.
A Turing machine can be programmed to search for counterexamples to any mathematical conjecture. Take Goldbach’s conjecture: every even integer greater than 2 is the sum of two primes. Build a machine that checks each even number in sequence. If it finds one that is not the sum of two primes, it halts. If Goldbach’s conjecture is true, the machine runs forever. If the conjecture is false, the machine halts at the first counterexample.
This machine can be built with a small number of states. Not large—small. The arithmetic of checking primality and addition is mechanical, repetitive, expressible in a compact transition table. So somewhere in the zoo of n-state machines, for some modest n, there is a machine whose halting behavior encodes the truth of Goldbach’s conjecture.
To determine BB(n), you must classify every n-state machine as halting or non-halting. Including this one. Including the one that encodes Goldbach. To know BB(n), you must know whether Goldbach’s conjecture is true.
And Goldbach is mild. The Riemann Hypothesis can be encoded. The consistency of arithmetic can be encoded. Any statement expressible in the language of first-order arithmetic—and that is nearly everything—can be encoded as the halting behavior of a Turing machine with a bounded number of states. The Busy Beaver function does not merely count. It knows. Its values implicitly contain the truth values of mathematical statements that the best human minds have failed to resolve for centuries.
This is already visible at BB(6). Some six-state machines exhibit Collatz-like behavior—iterative processes where a value is halved when even and mapped to 3x + 1 when odd, or variations thereof. The Collatz conjecture (does every starting value eventually reach 1?) has resisted proof since 1937. These six-state holdout machines do something analogous, and resolving their halting behavior may require resolving Collatz-type questions that current mathematics simply cannot answer. BB(6) is not merely unknown. It may be unknowable by current methods—not because we lack computing power, but because we lack theorems.
In 2016, Adam Yedidia and Scott Aaronson made the boundary explicit. They constructed a Turing machine—with approximately 27 states after compression—that halts if and only if ZFC, the Zermelo-Fraenkel axioms with the Axiom of Choice, is inconsistent. ZFC is the standard foundation of modern mathematics. Virtually every theorem proved in the last century can be formalized within it. It is, for practical purposes, the axiom system.
If ZFC is consistent—which is to say, if modern mathematics is not self-contradictory—then this machine runs forever. It searches for a proof of 0 = 1 within ZFC and never finds one. But ZFC, if consistent, cannot prove its own consistency. This is Gödel’s Second Incompleteness Theorem, one of the deepest results in mathematical logic. ZFC cannot prove that the machine runs forever. Therefore ZFC cannot determine BB(27). The value exists—it is a definite natural number—but no proof within ZFC can establish what it is.
Let that settle. The Busy Beaver function begins in the computable. BB(1) through BB(4) are provable by hand, by exhaustion, by patience. BB(5) is provable by heroic collaborative effort and machine-checked formal verification. And then, at some specific finite n—perhaps as low as 6, certainly by 27—the function exits the reach of our entire mathematical framework. Not the reach of our computers. The reach of our axioms.
The function passes through distinct regimes. First, the computable: small enough to enumerate and check. Then the merely difficult: too many machines, too complex behavior, but still provable with sufficient effort. Then the independence zone: values that are well-defined but unprovable within the axiom system you are working in. Different axiom systems would give different answers. ZFC says one thing. ZFC with large cardinal axioms might say another. The Busy Beaver function becomes a mirror held up to the limits of formal thought, reflecting back not a number but a question: what can your axioms reach?
This is not a deficiency of ZFC. It is a structural feature of any sufficiently powerful formal system. Gödel guarantees it. For any consistent axiom system strong enough to encode arithmetic, there exists a value of n beyond which BB(n) is independent of the system. The boundary moves when you strengthen the axioms—add large cardinals, add consistency statements, add whatever you like—but it never disappears. There is always a last number you can reach.
BB(5) = 4,098 is, almost certainly, the last exact Busy Beaver value anyone will ever know.
This is not a claim about computing power. It is not a claim about human intelligence or mathematical ingenuity. It is a claim about the structure of the knowable. For small n, “What is BB(n)?” is a question about machines. You enumerate them, run them, classify them. The answer is difficult but reachable—a matter of engineering and persistence. For large n, the same question transforms into something else entirely. It becomes a question about truth itself. About which mathematical statements are true, which are provable, and what the gap between those two categories contains.
The boundary between these two regimes is not gradual. It does not shade from one to the other through some twilight zone of increasing difficulty. It is sharp. On one side, proof by exhaustion works. On the other side, the machines you must classify encode statements your axioms cannot resolve. The transition happens at a specific n, and we are standing on it.
Think about what was required to prove BB(5). Thirty-five years from candidate to proof. A global collaboration of mathematicians and programmers. Thousands of specialized deciders. A proof assistant verifying every step. All of this to reach 47,176,870. One number. The next number in the sequence—BB(6)—already entangles with open problems in number theory. The one after that may entangle with the consistency of arithmetic. And by BB(27), we hit the wall of ZFC itself, the formal system in which virtually all of modern mathematics is conducted.
There is something poignant about this. The Busy Beaver function is the simplest possible encoding of computational ambition—a machine trying to do as much as possible before stopping. The question “What is the most work a simple machine can do?” sounds like it should have a simple answer. And it does, for a while. 1. 4. 6. 13. 4,098. Then the simplicity of the question collides with the complexity of what the machines encode, and the answer becomes everything that mathematics cannot prove, everything that computation cannot reach, everything that formal systems cannot contain.
The unknowable does not begin at infinity. It does not require exotic axioms or baroque set-theoretic constructions to encounter. It begins at a modest number of Turing machine states—somewhere between 5 and 27—and it has an exact address. We have just barely managed to read the number written there: 47,176,870. The last number. Beyond it, the Busy Beaver function continues to exist, continues to be well-defined, continues to take specific integer values. We simply cannot know what they are. The boundary of the knowable is not a horizon. It is a wall. And the last thing written on it, in the smallest legible script, is four thousand and ninety-eight—and the forty-seven million, one hundred seventy-six thousand, eight hundred seventy steps it took to write them.