In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps.[1] Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game. Rather than traditional programming languages, the programs used in the game are n-state Turing machines, one of the first mathematical models of computation.[2]
Turing machines consist of an infinite tape, and a finite set of states which serve as the program's "source code". Producing the most output is defined as writing the largest number of 1s on the tape, also referred to as achieving the highest score, and running for the longest time is defined as taking the longest number of steps to halt. The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts. Such machines are assumed to start on a blank tape, and the tape is assumed to contain only zeros and ones (a binary Turing machine). A player should conceive of a set of transitions between states aiming for the highest score or longest running time while making sure the machine will halt eventually.
An nth busy beaver, BB-n or simply "busy beaver" is a Turing machine that wins the n-state busy beaver game.[3] Depending on definition, it either attains the highest score, or runs for the longest time, among all other possible n-state competing Turing machines. The functions determining the highest score or longest running time of the n-state busy beavers by each definition are Σ(n) and S(n) respectively.[4]
Deciding the running time or score of the nth Busy Beaver is incomputable. In fact, both the functions Σ(n) and S(n) eventually become larger than any computable function. This has implications in computability theory, the halting problem, and complexity theory.[5] The concept was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions". One of the most interesting aspects of the busy beaver game is that, if it were possible to compute the functions Σ(n) and S(n) for all n, then this would resolve all mathematical conjectures which can be encoded as "does this Turing machine halt or not". For example, a 27-state Turing machine could check Goldbach's conjecture for each number and halt on a counterexample: if this machine had not halted after running for S(27) steps, then it must run forever, resolving the conjecture. Many other problems, including the Riemann hypothesis (744 states) and the consistency of ZF set theory (748 states), can be expressed in a similar form, where at most a countably infinite number of cases need to be checked.
The n-state busy beaver game (or BB-n game), introduced in Tibor Radó's 1962 paper, involves a class of Turing machines, each member of which is required to meet the following design specifications:
and produces three outputs:
"Running" the machine consists of starting in the starting state, with the current tape cell being any cell of a blank (all-0) tape, and then iterating the transition function until the Halt state is entered (if ever). If, and only if, the machine eventually halts, then the number of 1s finally remaining on the tape is called the machine's score. The n-state busy beaver (BB-n) game is therefore a contest, depending on definition to find such an n-state Turing machine having the largest possible score or running time.
The score function quantifies the maximum score attainable by a busy beaver on a given measure. This is a noncomputable function, because it grows asymptotically faster than any computable function.[6]
The score function,
\Sigma:N\toN
It is clear that Σ is a well-defined function: for every n, there are at most finitely many n-state Turing machines as above, up to isomorphism, hence at most finitely many possible running times.
According to the score-based definition, any n-state 2-symbol Turing machine M for which (i.e., which attains the maximum score) is called a busy beaver. For each n, there exist at least 4(n - 1)! n-state busy beavers. (Given any n-state busy beaver, another is obtained by merely changing the shift direction in a halting transition, a third by reversing all shift directions uniformly, and a fourth by reversing the halt direction of the all-swapped busy beaver. Furthermore, a permutation of all states except Start and Halt produces a machine that attains the same score. Theoretically, there could be more than one kind of transition leading to the halting state, but in practice it would be wasteful, because there is only one sequence of state transitions producing the sought-after result.)
Radó's 1962 paper proved that if
f:N\toN
Moreover, this implies that it is undecidable by a general algorithm whether an arbitrary Turing machine is a busy beaver. (Such an algorithm cannot exist, because its existence would allow Σ to be computed, which is a proven impossibility. In particular, such an algorithm could be used to construct another algorithm that would compute Σ as follows: for any given n, each of the finitely many n-state 2-symbol Turing machines would be tested until an n-state busy beaver is found; this busy beaver machine would then be simulated to determine its score, which is by definition Σ(n).)
Even though Σ(n) is an uncomputable function, there are some small n for which it is possible to obtain its values and prove that they are correct. It is not hard to show that Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, and with progressively more difficulty it can be shown that Σ(3) = 6, Σ(4) = 13 and Σ(5) = 4098 . Σ(n) has not yet been determined for any instance of n > 5, although lower bounds have been established (see the Known values section below).
A variant of Kolmogorov complexity is defined as follows:[7] The complexity of a number n is the smallest number of states needed for a BB-class Turing machine that halts with a single block of n consecutive 1s on an initially blank tape. The corresponding variant of Chaitin's incompleteness theorem states that, in the context of a given axiomatic system for the natural numbers, there exists a number k such that no specific number can be proven to have complexity greater than k, and hence that no specific upper bound can be proven for Σ(k) (the latter is because "the complexity of n is greater than k" would be proven if were proven). As mentioned in the cited reference, for any axiomatic system of "ordinary mathematics" the least value k for which this is true is far less than 10⇈10; consequently, in the context of ordinary mathematics, neither the value nor any upper-bound of Σ(10⇈10) can be proven. (Gödel's first incompleteness theorem is illustrated by this result: in an axiomatic system of ordinary mathematics, there is a true-but-unprovable sentence of the form, and there are infinitely many true-but-unprovable sentences of the form .)
In addition to the function Σ, Radó [1962] introduced another extreme function for Turing machines, the maximum shifts function, S, defined as follows:
Because normal Turing machines are required to have a shift in each and every transition or "step" (including any transition to a Halt state), the max-shifts function is at the same time a max-steps function.
Radó showed that S is noncomputable for the same reason that Σ is noncomputable — it grows faster than any computable function. He proved this simply by noting that for each n, S(n) ≥ Σ(n). Each shift may write a 0 or a 1 on the tape, while Σ counts a subset of the shifts that wrote a 1, namely the ones that hadn't been overwritten by the time the Turing machine halted; consequently, S grows at least as fast as Σ, which had already been proved to grow faster than any computable function.
The following connection between Σ and S was used by Lin & Radó [''Computer Studies of Turing Machine Problems'', 1965] to prove that Σ(3) = 6: For a given n, if S(n) is known then all n-state Turing machines can (in principle) be run for up to S(n) steps, at which point any machine that hasn't yet halted will never halt. At that point, by observing which machines have halted with the most 1s on the tape (i.e., the busy beavers), one obtains from their tapes the value of Σ(n). The approach used by Lin & Radó for the case of n = 3 was to conjecture that S(3) = 21, then to simulate all the essentially different 3-state machines for up to 21 steps. By analyzing the behavior of the machines that had not halted within 21 steps, they succeeded in showing that none of those machines would ever halt, thus proving the conjecture that S(3) = 21, and determining that Σ(3) = 6 by the procedure just described.
In 2016, Adam Yedidia and Scott Aaronson obtained the first (explicit) upper bound on the minimum n for which S(n) is unprovable in ZFC. To do so they constructed a 7910-state[8] Turing machine whose behavior cannot be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (stationary Ramsey property).[9] [10] Stefan O'Rear then reduced it to 1919 states, with the dependency on the stationary Ramsey property eliminated,[11] [12] and later to 748 states. In July 2023, Riebel reduced it to 745 states.[13] [14]
Suppose that S(n) is a computable function and let EvalS denote a TM, evaluating S(n). Given a tape with n 1s it will produce S(n) 1s on the tape and then halt. Let Clean denote a Turing machine cleaning the sequence of 1s initially written on the tape. Let Double denote a Turing machine evaluating function n + n. Given a tape with n 1s it will produce 2n 1s on the tape and then halt. Let us create the composition Double | EvalS | Clean and let n0 be the number of states of this machine. Let Create_n0 denote a Turing machine creating n0 1s on an initially blank tape. This machine may be constructed in a trivial manner to have n0 states (the state i writes 1, moves the head right and switches to state i + 1, except the state n0, which halts). Let N denote the sum n0 + n0.
Let BadS denote the composition Create_n0 | Double | EvalS | Clean. Notice that this machine has N states. Starting with an initially blank tape it first creates a sequence of n0 1s and then doubles it, producing a sequence of N 1s. Then BadS will produce S(N) 1s on tape, and at last it will clear all 1s and then halt. But the phase of cleaning will continue at least S(N) steps, so the time of working of BadS is strictly greater than S(N), which contradicts to the definition of the function S(n).
The uncomputability of Σ(n) may be proved in a similar way. In the above proof, one must exchange the machine EvalS with EvalΣ and Clean with Increment — a simple TM, searching for a first 0 on the tape and replacing it with 1.
The uncomputability of S(n) can also be established by reference to the blank tape halting problem. The blank tape halting problem is the problem of deciding for any Turing machine whether or not it will halt when started on an empty tape. The blank tape halting problem is equivalent to the standard halting problem and so it is also uncomputable. If S(n) was computable, then we could solve the blank tape halting problem simply by running any given Turing machine with n states for S(n) steps; if it has still not halted, it never will. So, since the blank tape halting problem is not computable, it follows that S(n) must likewise be uncomputable.
A number of other uncomputable functions can be defined based on measuring the performance of Turing machines in other ways than time or maximal number of ones. For example:
num(n)
space(n)
Both of these functions are also uncomputable. This can be shown for
space(n)
\Sigma(n)\leqspace(n)
num(n)
space(n)<num(3n+3)
space(n)
num(n)\leq\Sigma(n)\leqspace(n)\leqS(n)
Analogs of the shift function can be simply defined in any programming language, given that the programs can be described by bit-strings, and a program's number of steps can be counted.[15] For example, the busy beaver game can also be generalized to two dimensions using Turing machines on two-dimensional tapes, or to Turing machines that are allowed to stay in the same place as well as move to the left and right. Alternatively a "busy beaver function" for diverse models of computation can be defined with Kolgomorov complexity. This is done by taking
{BB}(n)
m
KL(m)\len
KL(m)
L
m
{BB}(n)
n
L
The longest running 6-state, 2-symbol machine which has the additional property of reversing the tape value at each step produces 1s after steps. So for the Reversal Turing Machine (RTM) class,[16] SRTM(6) ≥ and ΣRTM(6) ≥ . Likewise we could define an analog to the Σ function for register machines as the largest number which can be present in any register on halting, for a given number of instructions.
A simple generalization is the extension to Turing machines with m symbols instead of just 2 (0 and 1). For example a trinary Turing machine with m = 3 symbols would have the symbols 0, 1, and 2. The generalization to Turing machines with n states and m symbols defines the following generalized busy beaver functions:
For example, the longest-running 3-state 3-symbol machine found so far runs steps before halting.
| 1 | 2 | 2 | |
|---|---|---|---|
| 2 | 4 | 4 | |
| 3 | 6 | 7 | |
| 4 | 7 | 11 | |
| 5 | 8 | 15 | |
| 6 | 7 | 18 | |
| 7 | 6 | 18 |
The problem can be extended to nondeterministic Turing machines by looking for the system with the most states across all branches or the branch with the longest number of steps. The question of whether a given NDTM will halt is still computationally irreducible, and the computation required to find an NDTM busy beaver is significantly greater than the deterministic case, since there are multiple branches that need to be considered. For a 2-state, 2-color system with p cases or rules, the table to the right gives the maximum number of steps before halting and maximum number of unique states created by the NDTM.
In addition to posing a rather challenging mathematical game, the busy beaver functions Σ(n) and S(n) offer an entirely new approach to solving pure mathematics problems. Many open problems in mathematics could in theory, but not in practice, be solved in a systematic way given the value of S(n) for a sufficiently large n.[18] Theoretically speaking, the value of S(n) encodes the answer to all mathematical conjectures that can be checked in infinite time by a Turing machine with less than or equal to n states.
Consider any
| 0 | |
| \Pi | |
| 1 |
Now, this program is simulated by an n-state Turing machine, so if we know S(n) we can decide (in a finite amount of time) whether or not it will ever halt by simply running the machine that many steps. And if, after S(n) steps, the machine does not halt, we know that it never will and thus that there are no counterexamples to the given conjecture (i.e., no even numbers that are not the sum of two primes). This would prove the conjecture to be true. Thus specific values (or upper bounds) for S(n) could be, in theory, used to systematically solve many open problems in mathematics.
However, current results on the busy beaver problem suggest that this will not be practical for two reasons:
| |||||||||||||
| 10 |
Another property of S(n) is that no arithmetically sound, computably axiomatized theory can prove all of the function's values. Specifically, given a computable and arithmetically sound theory
T
nT
n\geqnT
S(n)=k
T
T
nT
T
0=1
S(nT)
T
nT
nT
Exploring the relationship between computational universality and the dynamic behavior of Busy Beaver Turing machines, a conjecture was proposed in 2012[21] suggesting that Busy Beaver machines were natural candidates for Turing universality as they display complex characteristics, known for (1) their maximal computational complexity within size constraints, (2) their ability to perform non-trivial calculations before halting, and (3) the difficulty in finding and proving these machines; these features suggest that Busy Beaver machines possess the necessary complexity for universality.
In 1964 Milton Green developed a lower bound for the 1s-counting variant of the Busy Beaver function that was published in the proceedings of the 1964 IEEE symposium on switching circuit theory and logical design. Heiner Marxen and Jürgen Buntrock described it as "a non-trivial (not primitive recursive) lower bound".[22] This lower bound can be calculated but is too complex to state as a single expression in terms of n.[23] This was done with a set of Turing machines, each of which demonstrated the lower bound for a certain n. When n=8 the method gives
\Sigma(8)\geq3 x (7 x 392-1)/2 ≈ 8.248 x 1044
In contrast, the best current (as of 2024) lower bound on
\Sigma(6)
10\uparrow\uparrow15
\uparrow
| |||||||||||||
| 10 |
1010
\Sigma(8)
Specifically, the lower bound was shown with a series of recursive Turing machines, each of which was made of a smaller one with two additional states that repeatedly applied the smaller machine to the input tape. Defining the value of the N-state busy-beaver competitor on a tape containing
m
BN(m)
m=0
BN(0)=1
B1(m)=m+1
BN(m)=1+BN-2(1+BN(m-1))
BN(m)=1+BN-2(1+BN(m-1))
G(N)
G(N)=BN-2(BN-2(1))
G(N)=1+BN-3(1+BN-3(1))
A(n,n)>G(4N+3)>A(4,2N+1)
Trivially, S(n) ≥ Σ(n) because a machine that writes Σ(n) ones must take at least Σ(n) steps to do so. It is possible to give a number of upper bounds on the time S(n) with the number of ones Σ(n):
S(n)\leq(n+1) x \Sigma(5n) x 2\Sigma(5n)
S(n)\leq\Sigma(9n)
S(n)\leq(2n-1) x \Sigma(3n+3)
num(n)<\Sigma(n)
S(n)<num(n+o(n))
S(n)<num(3n+6)
Ben-Amram and Petersen, 2002, also give an asymptotically improved bound on S(n). There exists a constant c, such that for all :
S(n)\le\Sigma\left(n+\left\lceil
| 8n | |
| log2n |
\right\rceil+c\right).
tends to be close to the square of, and in fact many machines give less than .
The following table lists the exact values and some known lower bounds for S(n), Σ(n), and several other busy beaver functions. In this table, 2-symbol Turing machines are used. Entries listed as "?" are at least as large as other entries to the left (because all n-state machines are also (n+1) state machines), and no larger than entries above them (because S(n) ≥ space(n) ≥ Σ(n) ≥ num(n)).
| S(n) | 6 | 21 | 107 | > 10⇈15 | ||
| space(n) | 4 | 7 | 16 | ≥ | ? | |
| Σ(n) | 4 | 6 | 13 | 4098 | > 10⇈15 | |
| num(n) | 4 | 6 | 12 | ? | ? |
These are tables of rules for the Turing machines that generate Σ(1) and S(1), Σ(2) and S(2), Σ(3) (but not S(3)), Σ(4) and S(4), Σ(5) and S(5), and the best known lower bound for Σ(6) and S(6).
In the tables, columns represent the current state and rows represent the current symbol read from the tape. Each table entry is a string of three characters, indicating the symbol to write onto the tape, the direction to move, and the new state (in that order). The halt state is shown as
H.Each machine begins in state A with an infinite tape that contains all 0s. Thus, the initial symbol read from the tape is a 0.
Result key: (starts at the position, halts at the position)
| 0 | 1RH | |
|---|---|---|
| 1 | (not used) |
Result: 0 0 0 (1 step, one "1" total)
| 0 | 1RB | 1LA | |
|---|---|---|---|
| 1 | 1LB | 1RH |
Result: 0 0 1 1 1 0 0 (6 steps, four "1"s total)
| 0 | 1RB | 0RC | 1LC | |
|---|---|---|---|---|
| 1 | 1RH | 1RB | 1LA |
Result: 0 0 1 1 1 1 0 0 (14 steps, six "1"s total).
Unlike the previous machines, this one is a busy beaver only for Σ, but not for S. (S(3) = 21.)
| 0 | 1RB | 1LA | 1RH | 1RD | |
|---|---|---|---|---|---|
| 1 | 1LB | 0LC | 1LD | 0RA |
Result: 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 steps, thirteen "1"s total)
| 0 | 1RB | 1RC | 1RD | 1LA | 1RH | |
|---|---|---|---|---|---|---|
| 1 | 1LC | 1RB | 0LE | 1LD | 0LA |
Result: 4098 "1"s with 8191 "0"s interspersed in 47,176,870 steps.
Note in the image to the right how this solution is similar qualitatively to the evolution of some cellular automata.
| 0 | 1RB | 1RC | 1LC | 0LE | 1LF | 0RC | |
|---|---|---|---|---|---|---|---|
| 1 | 0LD | 0RF | 1LA | 1RH | 0RB | 0RE |
Result: 1 1 1 1 ... 1 1 1 ("10" followed by more than 10↑↑15 contiguous "1"s in more than 10↑↑15 steps, where 10↑↑15=1010..10, an exponential tower of 15 tens).
In the following table, the rules for each busy beaver (maximizing Σ) are represented visually, with orange squares corresponding to a "1" on the tape, and white corresponding to "0". The position of the head is indicated by the black ovoid, with the orientation of the head representing the state. Individual tapes are laid out horizontally, with time progressing from top to bottom. The halt state is represented by a rule which maps one state to itself (head doesn't move).
This is where Radó first defined the busy beaver problem and proved that it was uncomputable and grew faster than any computable function.
The results of this paper had already appeared in part in Lin's 1963 doctoral dissertation, under Radó's guidance. Lin & Radó prove that Σ(3) = 6 and S(3) = 21 by proving that all 3-state 2-symbol Turing Machines which don't halt within 21 steps will never halt. (Most are proven automatically by a computer program, however 40 are proven by human inspection.)
Brady proves that Σ(4) = 13 and S(4) = 107. Brady defines two new categories for non-halting 3-state 2-symbol Turing Machines: Christmas Trees and Counters. He uses a computer program to prove that all but 27 machines which run over 107 steps are variants of Christmas Trees and Counters which can be proven to run infinitely. The last 27 machines (referred to as holdouts) are proven by personal inspection by Brady himself not to halt.
Machlin and Stout describe the busy beaver problem and many techniques used for finding busy beavers (which they apply to Turing Machines with 4-states and 2-symbols, thus verifying Brady's proof). They suggest how to estimate a variant of Chaitin's halting probability (Ω).
Marxen and Buntrock demonstrate that Σ(5) ≥ 4098 and S(5) ≥ and describe in detail the method they used to find these machines and prove many others will never halt.
Green recursively constructs machines for any number of states and provides the recursive function that computes their score (computes σ), thus providing a lower bound for Σ. This function's growth is comparable to that of Ackermann's function.
Busy beaver programs are described by Alexander Dewdney in Scientific American, August 1984, pages 19–23, also March 1985 p. 23 and April 1985 p. 30.
Wherein Brady (of 4-state fame) describes some history of the beast and calls its pursuit "The Busy Beaver Game". He describes other games (e.g. cellular automata and Conway's Game of Life). Of particular interest is "The Busy Beaver Game in Two Dimensions" (p. 247). With 19 references.
Cf Chapter 9, Turing Machines. A difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. A reference in Booth attributes busy beaver to Rado. Booth also defines Rado's busy beaver problem in "home problems" 3, 4, 5, 6 of Chapter 9, p. 396. Problem 3 is to "show that the busy beaver problem is unsolvable... for all values of n."
Bounds between functions Σ and S.
Improved bounds.
This article contains a complete classification of the 2-state, 3-symbol Turing machines, and thus a proof for the (2, 3) busy beaver: Σ(2, 3) = 9 and S(2, 3) = 38.
This is the description of ideas, of the algorithms and their implementation, with the description of the experiments examining 5-state and 6-state Turing machines by parallel run on 31 4-core computer and finally the best results for 6-state TM.