BB(10) Surpasses Graham's Number: A Milestone in the Busy Beaver Problem

There is a famous function in computer science—the Busy Beaver function BB(n)—which describes the maximum number of 1s an n-state Turing machine can write on its tape before halting. This function grows extremely fast, far outpacing any computable function. A recent hot topic on Hacker News, "BB(10) > Graham's Number," points out that the 10-state Busy Beaver number already exceeds Graham's Number.

What Is the Busy Beaver Function

The Busy Beaver function BB(n) is defined as the maximum number of 1s an n-state, two-symbol Turing machine can write on its tape when it finally halts. It is uncomputable—there is no general algorithm to find BB(n) for arbitrary n.

Because it is uncomputable, BB(n) grows far faster than all computable functions, including the Ackermann function and even the rapidly growing Conway chained arrow notation. The first few known values are small (BB(1)=1, BB(2)=4, BB(3)=6, BB(4)=13), but from the fifth term onward it skyrockets. BB(5) was only recently determined to be 47176870, and BB(6) is already too large to write out completely with conventional notation.

A two-symbol Turing machine is a heavily restricted Turing machine model: the tape alphabet has only two symbols {0, 1} (plus an implicit blank symbol, usually also treated as 0), the read/write head can only move one cell left or right per step, and the number of states is fixed at n. The phrase "number of 1s written" usually refers to the number of non-blank cells on the tape at halting; both counting conventions are used in the literature, differing only by a constant factor, which does not affect discussions of growth magnitude.

The behavior of such a machine is entirely determined by a finite state transition table: for each combination of "state × current symbol," it specifies what to write next, which way to move, and which state to switch to. The number of transition tables is finite, so there are only finitely many n-state Turing machines, which in theory can be enumerated and simulated one by one. The problem lies precisely here—some of these machines never halt, and determining whether a given machine halts is exactly the halting problem, which is undecidable. So although BB(n) has a precise definition and each n corresponds to a determinate natural number, there is no algorithm that can compute it for arbitrary n.

A computable function is one for which there exists a Turing machine that, for any input, produces an output and halts within a finite number of steps. Although the Ackermann function and Conway chained arrow notation grow extremely fast, they are still computable—they can all be written as finite algorithms. What makes the Busy Beaver function different is this: if BB(n) could be computed, it could be used to determine whether all n-state machines halt, thereby solving the halting problem. Since the halting problem is undecidable, BB(n) must be uncomputable.

This yields a direct corollary: BB(n) is a function that is uncomputable but well-defined as a natural number, and for any computable function f, there exists some n such that BB(n) > f(n). In other words, no matter how insanely large a computable function you construct, the Busy Beaver will eventually leave it behind at some state count. This is precisely the fundamental reason BB(10) can exceed Graham's Number.

What Is Graham's Number

Graham's Number long held a Guinness record as "the largest number to appear in a mathematical proof." It comes from an upper bound problem in Ramsey theory concerning the coloring of hypercube vertices, recursively defined using Knuth's up-arrow notation. Its scale is so vast that even its number of digits cannot be written out with an ordinary power tower.

For a long time, Graham's Number was regarded as synonymous with "inconceivably large." But the existence of the Busy Beaver function makes this "inconceivability" look rather restrained.

Knuth's up-arrow notation uses a single up-arrow to denote iteration of exponentiation, two up-arrows to denote iteration of power towers (i.e., tetration), three arrows to iterate the two-arrow process, and so on—the more arrows, the faster the growth. Graham's Number depends precisely on this kind of recursive arrow stacking: first define g₁ = 3↑↑↑↑3 (four arrows), then let g₂ be a layer of 3 with g₁ arrows, and so on to define g₆₄; Graham's Number is g₆₄.

The defining feature of this construction is that each step takes the number of arrows used in the previous step as the new number of arrows, forming layer upon layer of nested explosive growth. Even so, the entire definition remains finite, mechanical, and step-by-step expandable—if you are willing to write out symbols on an astronomical scale. This "huge but fully computable" nature stands in sharp contrast to the uncomputability of the Busy Beaver function.

Why BB(10) Can Surpass Graham's Number

The key lies in the difference in orders of magnitude of growth rates. Although Graham's Number is enormous, it is still computable—there exists a finite algorithm that can write it out (it just requires absurd time and space). The Busy Beaver function lies at the other end of the computability hierarchy: it is uncomputable, and its growth exceeds that of any recursively computable function.

An intuitive way to understand this is: given any computable function f, one can always find some n such that BB(n) > f(n). Graham's Number corresponds to a specific computable construction, so there must exist a not-too-large n for which BB(n) exceeds it. The conclusion given in community discussions is that this n falls around 10—that is, BB(10) is already determined to be greater than Graham's Number.

This means that to describe the maximum number of 1s a 10-state Turing machine can write, Graham's Number is not even enough.

What This Means

This fact is not surprising in itself; it is a direct corollary of the definition of the Busy Beaver function. But its educational value lies in:

• "Large" is relative. So-called "largest numbers" constructed by human intuition are insignificant in the face of uncomputable functions.
• 10 states are already enough. The minimalist Turing machine model can encode extremely complex computational processes with very few states, and the specific value of BB(10) can never be computed by humans—because computing it would amount to solving an instance of the halting problem.
• An intuitive demonstration of uncomputability. Compared with abstract undecidability proofs, BB(n) surpassing Graham's Number is an example that can be explained to non-experts, showing just how vast the gulf is implied by "there exist functions that cannot be computed."

Most comments in the HN discussion thread (news.ycombinator.com/item?id=50070741) focus on the derivation details of this conclusion and whether it has been rigorously proven. The core consensus is that this is a corollary of standard properties of the Busy Beaver function, not a new unsolved problem.

Summary

BB(10) > Graham's Number is a beautiful thought-experiment-style conclusion. It reminds us that the seemingly simple model of the Turing machine contains complexity far beyond human intuition. Graham's Number was once the pinnacle symbol of "large numbers"; now it has become a coordinate point in front of the Busy Beaver function.

One-line Summary

The 10-state Busy Beaver number BB(10) has surpassed Graham's Number, highlighting the terrifying growth of uncomputable functions.

Paragraph Summary

The article explores a striking property of the Busy Beaver function BB(n): BB(10) is already greater than Graham's Number. BB(n) is defined as the maximum number of 1s an n-state two-symbol Turing machine can write before halting; it is uncomputable, so it grows faster than every computable function, including the Ackermann function. Although Graham's Number was long regarded as "the largest number," it can still be constructed by a finite algorithm and belongs to the computable realm. Since for any computable function f there exists n such that BB(n) > f(n), Graham's Number must be surpassed by some not-too-large BB(n), and the community believes this n is about 10. This conclusion is not a new problem but a direct corollary of standard properties of BB(n), and its value lies in intuitively demonstrating the vast gulf between uncomputability and human intuition.