This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) This articlemay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(October 2016) (Learn how and when to remove this message) This articlehas an unclearcitation style. The references used may be made clearer with a different or consistent style ofcitation andfootnoting.(July 2024) (Learn how and when to remove this message) (Learn how and when to remove this message)

Intheoretical computer science, thebusy beaver game aims to find a terminatingprogram of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps.^[1] Since anendlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game.^[1] Rather than traditional programming languages, the programs used in the game are n-stateTuring machines,^[1] 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.^[3] Then-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which hasn states and eventually halts.^[1] 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).^[1] The objective of the game is to program a set of transitions between states aiming for the highest score or longest running time while making sure the machine will halt eventually.

Ann-th busy beaver,BB-n or simply "busy beaver" is a Turing machine that wins then-state busy beaver game.^[4] Depending on definition, it either attains the highest score (denoted byΣ(n)^[3]), or runs for the longest time (S(n)), among all other possiblen-state competing Turing machines.

Deciding the running time or score of thenth Busy Beaver isincomputable.^[3] In fact, both the functions Σ(n) and S(n) eventually become larger than any computable function.^[3] This has implications incomputability theory, thehalting problem, andcomplexity theory.^[5] The concept of a busy beaver was first introduced byTibor Radó in his 1962 paper, "On Non-Computable Functions".^[3] 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 alln, then this would resolve all mathematical conjectures which can be encoded in the form "does <this Turing machine> halt".^[4] For example, a 27-state Turing machine could checkGoldbach'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.^[4] Many other problems, including theRiemann hypothesis (744 states) and the consistency ofZF set theory (745 states^[6][7]), can be expressed in a similar form, where at most acountably infinite number of cases need to be checked.^[4]

The Busy Beaver function is related to the Sleepy Sloth function. For instance, whereas the value of Busy Beaver at 5 is 47,176,870, the value of Sleepy Sloth at 47,176,870 is 5.^[8]

Then-state busy beaver game (orBB-n game), introduced inTibor Radó's 1962 paper, involves a class ofTuring machines, each member of which is required to meet the following design specifications:

• The machine hasn "operational" states plus a Halt state, wheren is a positive integer, and one of then states is distinguished as the starting state. (Typically, the states are labelled by 1, 2, ...,n, with state 1 as the starting state, or byA,B,C, ..., with stateA as the starting state.)
• The machine uses a single two-way infinite (or unbounded) tape.
• The tape alphabet is {0, 1}, with 0 serving as the blank symbol.
• The machine'stransition function takes two inputs:

1. the current non-Halt state,
2. the symbol in the current tape cell,

and produces three outputs:

1. a symbol to write over the symbol in the current tape cell (it may be the same symbol as the symbol overwritten),
2. a direction to move (left or right; that is, shift to the tape cell one place to the left or right of the current cell), and
3. a state to transition into (which may be the Halt state).

"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'sscore. Then-state busy beaver (BB-n) game is therefore a contest, depending on definition to find such ann-state Turing machine having the largest possible score or running time.

The rules for one 1-state Turing machine might be:

• In state 1, if the current symbol is 0, write a 1, move one space to the right, and transition to state 1
• In state 1, if the current symbol is 1, write a 0, move one space to the right, and transition to HALT

This Turing machine would move to the right, swapping the value of all the bits it passes. Since the starting tape is all 0s, it would make an unending string of ones. This machine would not be a busy beaver contender because it runs forever on a blank tape.

In his original 1962 paper, Radó defined two functions related to the busy beaver game: the score function Σ(n) and the shifts function S(n).^[3] Both take a number of Turing machine states${\displaystyle n}$ and output the maximum score attainable by a Turing machine of that number of states by some measure. The score function Σ(n) gives the maximum number of 1s an${\displaystyle n}$-state Turing machine can output before halting, while the shifts function S(n) gives the maximum number of shifts (or equivalently steps, because each step includes a shift) that an${\displaystyle n}$-state Turing machine can undergo before halting.^[3] He proved that both of these functions werenoncomputable, because they each grew faster than any computable function.^[3] The function BB(n) has been defined to be either of these functions,^{[citation needed]} so that notation is not used in this article.

A number of other uncomputable functions can also be defined based on measuring the performance of Turing machines in other ways than time or maximal number of ones.^[9] For example:^[9]

• The function${\displaystyle \text{num}(n)}$ is defined to be the maximum number ofcontiguous ones a halting Turing machine can write on a blank tape. In other words, this is the largestunary number a Turing machine ofn states can write on a tape.
• The function${\displaystyle \text{space}(n)}$ is defined to be the maximal number of tape squares a halting Turing machine canread (i.e., visit) before halting. This includes the starting square, but not a square that the machine only reaches after the halt transition (if the halt transition is annotated with a move direction), because that square does not influence the machine's behaviour. This is the maximalspace complexity of ann-state Turing machine.

These four functions together stand in the relation${\displaystyle \text{num}(n)\le \mathrm{\Sigma }(n)\le \text{space}(n)\le S(n)}$.^[9] More functions can also be defined by operating the game on different computing machines, such as 3-symbol Turing machines,^[10] non-deterministic Turing machines,^[11] thelambda calculus (sequenceA333479 in theOEIS) or even arbitrary programming languages.^[10]

The score function quantifies the maximum score attainable by a busy beaver on a given measure. This is anoncomputable function, because it growsasymptotically faster than any computable function.^[12]

The score function,${\displaystyle \mathrm{\Sigma }:\mathbb{N}\to \mathbb{N}}$, is defined so that Σ(n) is the maximum attainable score (the maximum number of 1s finally on the tape) among all halting 2-symboln-state Turing machines of the above-described type, when started on a blank tape.

It is clear that Σ is a well-defined function: for everyn, there are at most finitely manyn-state Turing machines as above,up to isomorphism, hence at most finitely many possible running times.

According to the score-based definition, anyn-state 2-symbol Turing machineM for whichσ(M) = Σ(n) (i.e., which attains the maximum score) is called a busy beaver. For eachn, there exist at least 4(n − 1)!n-state busy beavers. (Given anyn-state busy beaver, another is obtained by merely changing the shift direction in a halting transition, a third by reversingall 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${\displaystyle f:\mathbb{N}\to \mathbb{N}}$ is anycomputable function, then Σ(n) >f(n) for all sufficiently largen, and hence that Σ is not a computable function.^[3]

Moreover, this implies that it isundecidable by a generalalgorithm 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 givenn, each of the finitely manyn-state 2-symbol Turing machines would be tested until ann-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 smalln 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 (sequenceA028444 in theOEIS). Σ(n) has not yet been determined for any instance ofn > 5, although lower bounds have been established (see theKnown values section below).

A variant ofKolmogorov complexity is defined as follows:^[13] Thecomplexity of a numbern is the smallest number of states needed for a BB-class Turing machine that halts with a single block ofn consecutive 1s on an initially blank tape. The corresponding variant ofChaitin's incompleteness theorem states that, in the context of a givenaxiomatic system for thenatural numbers, there exists a numberk such that no specific number can be proven to have complexity greater thank, and hence that no specific upper bound can be proven for Σ(k) (the latter is because "the complexity ofn is greater thank" would be proven ifn > Σ(k) were proven). As mentioned in the cited reference, for any axiomatic system of "ordinary mathematics" the least valuek for which this is true is far less than10⇈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Σ(10⇈10) =n, and there are infinitely many true-but-unprovable sentences of the formΣ(10⇈10) <n.)

In addition to the function Σ, Radó [1962] introduced another extreme function for Turing machines, themaximum shifts function,S, defined as follows:^[3]

• s(M) = the number of shiftsM makes before halting, for anyM ∈E_n,
• S(n) = max{s(M) |M ∈E_n} = the largest number of shifts made by any haltingn-state 2-symbol Turing machine.

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 thatS is noncomputable for the same reason that Σ is noncomputable — it grows faster than any computable function. He proved this simply by noting that for eachn,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.^[3]

The following connection between Σ andS was used by Lin & Radó [Computer Studies of Turing Machine Problems, 1965] to prove that Σ(3) = 6 and that S(3)=21: For a givenn, ifS(n) is known then alln-state Turing machines can (in principle) be run for up toS(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 ofn = 3 was to conjecture thatS(3) = 21 (after unsuccessfully conjecturing 18), then to simulate all the essentially different 3-state machines (82,944 machines, equal to 2¹⁰3⁴) for up to 21 steps. They found 26,073 machines that halted, including one that halted only after 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, most of them following a certain pattern. This proved the conjecture thatS(3) = 21, and also determined that Σ(3) = 6, which was attained by several machines, all halting after 11 to 14 steps.^[14]

In 2016, Adam Yedidia andScott Aaronson obtained the first (explicit) upper bound on the minimumn for which S(n) is unprovable inZFC. To do so they constructed a 7910-state^[15] Turing machine whose behavior cannot be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with theaxiom of choice), under reasonable consistency hypotheses (stationary Ramsey property).^[16][17] Stefan O'Rear then reduced it to 1919 states, with the dependency on the stationary Ramsey property eliminated,^[18][19] and later to 748 states.^[5] In July 2023, Riebel reduced it to 745 states.^[6][7]

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved. Find sources: "Busy beaver" – news ·newspapers ·books ·scholar ·JSTOR(July 2024) (Learn how and when to remove this message)

Suppose thatS(n) is a computable function and letEvalS denote a TM, evaluatingS(n). Given a tape withn 1s it will produceS(n) 1s on the tape and then halt. LetClean denote a Turing machine cleaning the sequence of 1s initially written on the tape. LetDouble denote a Turing machine evaluating functionn +n. Given a tape withn 1s it will produce 2n 1s on the tape and then halt. Let us create the compositionDouble |EvalS |Clean and letn₀ be the number of states of this machine. LetCreate_n₀ denote a Turing machine creatingn₀ 1s on an initially blank tape. This machine may be constructed in a trivial manner to haven₀ states (the statei writes 1, moves the head right and switches to statei + 1, except the staten₀, which halts). LetN denote the sumn₀ +n₀.

LetBadS denote the compositionCreate_n₀ |Double |EvalS |Clean. Notice that this machine hasN states. Starting with an initially blank tape it first creates a sequence ofn₀ 1s and then doubles it, producing a sequence ofN 1s. ThenBadS will produceS(N) 1s on tape, and at last it will clear all 1s and then halt. But the phase of cleaning will continue at leastS(N) steps, so the time of working ofBadS is strictly greater thanS(N), which contradicts to the definition of the functionS(n).

The uncomputability of Σ(n) may be proved in a similar way. In the above proof, one must exchange the machineEvalS withEvalΣ andClean withIncrement — a simple TM, searching for a first 0 on the tape and replacing it with 1.

The uncomputability ofS(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 standardhalting problem and so it is also uncomputable. IfS(n) was computable, then we could solve the blank tape halting problem simply by running any given Turing machine withn states forS(n) steps; if it has still not halted, it never will. So, since the blank tape halting problem is not computable, it follows thatS(n) must likewise be uncomputable.

Both${\displaystyle \text{space}(n)}$ and${\displaystyle \text{num}(n)}$ functions are uncomputable.^[9] This can be shown for${\displaystyle \text{space}(n)}$ by noting that every tape square a Turing machine writes a one to, it must also visit: in other words,${\displaystyle \mathrm{\Sigma }(n)\le \text{space}(n)}$.^[9] The${\displaystyle \text{num}(n)}$ function can be shown to be incomputable by proving, for example, that: this can be done by designing an(3n+3)-state Turing machine which simulates then-state space champion, and then uses it to write at least${\displaystyle \text{space}(n)}$ contiguous ones to the tape.^[9]

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.^[10] 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.^[10] Alternatively a "busy beaver function" for diverse models of computation can be defined withKolmogorov complexity.^[10] This is done by taking${\displaystyle BB(n)}$ to be the largest integer${\displaystyle m}$ such that${\displaystyle K_L(m)\le n}$, where${\displaystyle K_L(m)}$ is the length of the shortest program in${\displaystyle L}$ that outputs${\displaystyle m}$:${\displaystyle BB(n)}$ is thereby the largest integer a program with length${\displaystyle n}$ or less can output in${\displaystyle L}$.^[10]

The longest running 6-state, 2-symbol machine which has the additional property of reversing the tape value at each step produces6147 1s after47339970 steps.^{[citation needed]} So for the Reversal Turing Machine (RTM) class,^[20]S_RTM(6) ≥47339970 and Σ_RTM(6) ≥6147. Likewise we could define an analog to the Σ function forregister machines as the largest number which can be present in any register on halting, for a given number of instructions.^{[citation needed]}

A simple generalization is the extension to Turing machines withm symbols instead of just 2 (0 and 1).^[10] For example a trinary Turing machine withm = 3 symbols would have the symbols 0, 1, and 2. The generalization to Turing machines withn states andm symbols defines the followinggeneralized busy beaver functions:

1. Σ(n,m): the largest number of non-zeros printable by ann-state,m-symbol machine started on an initially blank tape before halting,^{[citation needed]} and
2. S(n,m): the largest number of steps taken by ann-state,m-symbol machine started on an initially blank tape before halting.^[10]

For example, the longest-running 3-state 3-symbol machine found so far runs119112334170342540 steps before halting.^[21][22]

The problem can be extended tonondeterministic Turing machines by looking for the system with the most states across all branches or the branch with the longest number of steps.^[11] 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 withp 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 challengingmathematical game, the busy beaver functions Σ(n) andS(n) offer an entirely new approach to solving pure mathematics problems. Manyopen problems in mathematics could in theory, but not in practice, be solved in a systematic way given the value ofS(n) for a sufficiently largen.^[4][23] 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 ton states.^[5]

Consider any${\displaystyle {\mathrm{\Pi }}_1^0}$conjecture: any conjecture that could bedisproven via acounterexample among acountable number of cases (e.g.Goldbach's conjecture). Write a computer program that sequentially tests this conjecture for increasing values. In the case of Goldbach's conjecture, we would consider every even number ≥ 4 sequentially and test whether or not it is the sum of two prime numbers. Suppose this program is simulated on ann-state Turing machine. If it finds a counterexample (an even number ≥ 4 that is not the sum of two primes in our example), it halts and indicates that. However, if the conjecture is true, then our program will never halt. (This program haltsonly if it finds a counterexample.)^[5]

Now, this program is simulated by ann-state Turing machine, so if we knowS(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, afterS(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.^[5] Thus specific values (or upper bounds) forS(n) could be, in theory, used to systematically solve many open problems in mathematics.^[5]

However, current results on the busy beaver problem suggest that this will not be practical for two reasons:^{[citation needed]}

• It is extremely hard to prove values for the busy beaver function (and the max shift function). Every known exact value ofS(n) was proven by enumerating everyn-state Turing machine and proving whether or not each halts. One would have to calculateS(n) by some less direct method for it to actually be useful.^{[citation needed]}
• The values of S(n) and the other busy beaver functions get very large, very quickly. While the value of S(5) is only around 47 million, the value of S(6) is more than 10⇈15, which is equal to${\displaystyle {10}^{({10}^{({10}^{({10}^{(\dots )})})})}}$ with a stack of 15 tens.^[10][24] This number has 10⇈14 digits and is unreasonable to use in a computation. The value of S(27), which is the number of steps the current program for theGoldbach conjecture would need to be run to give a conclusive answer, is incomprehensibly huge, and not remotely possible to write down, much less run a machine for, in the observable universe.^[4]

Another property of S(n) is that no arithmetically sound, computably axiomatizedtheory can prove all of the function's values. Specifically, given a computable and arithmetically sound theory${\displaystyle T}$, there is a number${\displaystyle n_T}$ such that for all${\displaystyle n\ge n_T}$, no statement of the form${\displaystyle S(n)=k}$ can be proved in${\displaystyle T}$.^[5] This implies that for each theory there is a specific largest value of S(n) that it can prove. This is true because for every such${\displaystyle T}$, a Turing machine with${\displaystyle n_T}$ states can be designed to enumerate every possible proof in${\displaystyle T}$.^[5] If the theory is inconsistent, then all false statements are provable, and the Turing machine can be given the condition to halt if and only if it finds a proof of, for example,${\displaystyle 0=1}$.^[5] Any theory that proves the value of${\displaystyle S(n_T)}$ proves its own consistency, violatingGödel's second incompleteness theorem.^[5] This can be used to place various theories on a scale, for example the variouslarge cardinal axioms inZFC: if each theory${\displaystyle T}$ is assigned as its number${\displaystyle n_T}$, theories with larger values of${\displaystyle n_T}$ prove the consistency of those below them, placing all such theories on a countably infinite scale.^[5]

• A 745-state binary Turing machine has been constructed that haltsif and only ifZFC is inconsistent.^[6][7]

• A 744-state Turing machine has been constructed that halts if, and only if, theRiemann hypothesis is false.^[18][4]

• A 43-state Turing machine was constructed that halts if, and only if,Goldbach's conjecture is false. This was further reduced to 25-state machine,^[18][4] and later formally proved and verified in theLean 4 theorem proving language.^[25]

• A 15-state Turing machine has been constructed that halts if and only if the following conjecture formulated byPaul Erdős in 1979 is false: for alln > 8 there is at least one digit 2 in the base 3 representation of 2ⁿ.^[26][27]

Exploring the relationship between computational universality and the dynamic behavior of Busy BeaverTuring machines, a conjecture was proposed in 2012^[28] suggesting that Busy Beaver machines were natural candidates for Turing universality as they display complex characteristics, known for (1) their maximalcomputational 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".^[29] This lower bound can be calculated but is too complex to state as a single expression in terms ofn.^[30] This was done with a set of Turing machines, each of which demonstrated the lower bound for a certainn.^[30] Whenn=8 the method gives

${\displaystyle \mathrm{\Sigma }(8)\ge 3\times (7\times 3^{92}-1)/2\approx 8.248\times {10}^{44}}$.

In contrast, the best current (as of 2024) lower bound on${\displaystyle \mathrm{\Sigma }(6)}$ is${\displaystyle 10\uparrow \uparrow 15}$, where each${\displaystyle \uparrow }$ isKnuth's up-arrow notation.^[10] This represents${\displaystyle {10}^{({10}^{({10}^{({10}^{(\dots )})})})}}$, an exponentiated chain of 15 tens equal to${\displaystyle {10}^{10\uparrow \uparrow 14}}$. The value of${\displaystyle \mathrm{\Sigma }(8)}$ is probably much larger still than that.

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.^[30] Defining the value of the N-state busy-beaver competitor on a tape containing${\displaystyle m}$ ones to be${\displaystyle B_N(m)}$ (the ultimate output of each machine being its value on${\displaystyle m=0}$, because a blank tape has 0 ones), the recursion relations are as follows:^[30] a

${\displaystyle B_N(0)=1}$

${\displaystyle B_1(m)=m+1}$

${\displaystyle B_N(m)=1+B_{N-2}(1+B_N(m-1))}$

This leads to two formulas, for odd and even numbers, for calculating the lower bound given by the Nth machine,${\displaystyle G(N)}$:

${\displaystyle G(N)=B_{N-2}(B_{N-2}(1))}$ for odd N

${\displaystyle G(N)=1+B_{N-3}(1+B_{N-3}(1))}$ for even N

The lower bound BB(N) can also be related to theAckermann function. It can be shown that:^[31]

${\displaystyle 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.^[31] It is possible to give a number of upper bounds on the time S(n) with the number of ones Σ(n):

• ${\displaystyle S(n)\le (n+1)\times \mathrm{\Sigma }(5n)\times 2^{\mathrm{\Sigma }(5n)}}$   (Rado^[31])
• ${\displaystyle S(n)\le \mathrm{\Sigma }(9n)}$   (Buro^[31])
• ${\displaystyle S(n)\le (2n-1)\times \mathrm{\Sigma }(3n+3)}$   (Julstrom and Zwick^[31])

By defining num(n) to be the maximum number of ones ann-state Turing machine is allowed to output contiguously, rather than in any position (the largestunary number it can output), it is possible to show:^[31]

  (Ben-Amram, et al., 1996^[9])

Ben-Amram and Petersen, 2002, also give an asymptotically improved bound on S(n). There exists a constantc, such that for alln ≥ 2:^[31]

${\displaystyle S(n)\le \mathrm{\Sigma }\left(n+\lceil \frac{8n}{{\log }_{2}n}\rceil +c\right).}$

The following table lists the exact values and some known lower bounds forS(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)). So, space(6) is known to be greater than 10⇈15, as space(n) ≥ Σ(n) and Σ(6) > 10⇈15.47176870 is an upper bound for space(5), because S(5) =47176870 (^[2]) and S(n) ≥ space(n). 4098 is an upper bound for num(5), because Σ(5) = 4098 (^[31]) and Σ(n) ≥ num(n). The last entry listed as "?" is num(6), because Σ(6) > 10⇈15, but Σ(n) ≥ num(n).

The 5-state busy beaver was discovered by Heiner Marxen and Jürgen Buntrock in 1989, but only proved to be the winning fifth busy beaver — stylized as BB(5) — in 2024 using a proof inCoq.^[33][34]

These are tables of rules for Turing machines that generate Σ(1) andS(1), Σ(2) andS(2), Σ(3) (but notS(3)), Σ(4) andS(4), Σ(5) andS(5), and the best known lower bound for Σ(6) andS(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 asH.

Each machine begins in stateA with an infinite tape that contains all 0s. Thus, the initial symbol read from the tape is a 0.

Result key: (starts at the positionoverlined, halts at the positionunderlined)

1-state, 2-symbol busy beaver

	A
0	1RH
1	(not used)

Result: 0 010 0 (1 step, one "1" total)

2-state, 2-symbol busy beaver^{[citation needed]}

	A	B
0	1RB	1LA
1	1LB	1RH

Result: 0 0 1 11 1 0 0 (6 steps, four "1"s total)

3-state, 2-symbol busy beaver^[35][14]

	A	B	C
0	1RB	0RC	1LC
1	1RH	1RB	1LA

Result: 0 0 11 11 1 1 0 0 (14 steps, six "1"s total).

This is one of several nonequivalent machines giving six 1s. Unlike the previous machines, this one is a busy beaver for Σ, but not forS. (S(3) = 21, and the machine obtains only five 1s.^[14])

4-state, 2-symbol busy beaver

	A	B	C	D
0	1RB	1LA	1RH	1RD
1	1LB	0LC	1LD	0RA

Result: 0 0 10 1 1 1 1 1 1 1 11 1 1 1 0 0 (107 steps, thirteen "1"s total)

5-state, 2-symbol busy beaver

	A	B	C	D	E
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 somecellular automata.

current 6-state, 2-symbol best contender^[21][32]

	A	B	C	D	E	F
0	1RB	1RC	1LC	0LE	1LF	0RC
1	0LD	0RF	1LA	1RH	0RB	0RE

Result: 10 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=10^10..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).

Evolution of busy beavers with 1-4 states

Rules for 1-state busy beaver

Rules for 2-state busy beaver

Rules for 3-state busy beaver

Rules for 4-state busy beaver

Evolution of 1-state busy beaver until halt. The initial state triggers a halt, with a single "1" being written before termination.

Evolution of 2-state busy beaver until halt

Evolution of 3-state busy beaver until halt

Evolution of 4-state busy beaver until halt. Bottom line in left image wraps to top line of right image. The final step writes "1" before halting (not shown).

• Rayo's number
• Turmite

Wikiversity hosts a quiz on the busy beaver

• The page ofHeiner Marxen, who, with Jürgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine.
• Pascal Michel'sHistorical survey of busy beaver results which also contains best results and some analysis.
• Definition of the classRTM - Reversal Turing Machines, simple and strong subclass of the TMs.
• "The Busy Beaver Problem: A New Millennium Attack" (archived) at the Rensselaer RAIR Lab. This effort found several new records and established several values for the quadruple formalization.
• Daniel Briggs'websitearchive andforum for solving the 5-state, 2-symbol busy beaver problem, based onSkelet (Georgi Georgiev) nonregular machines list.
• Ligocki, Shawn (2021-07-17)."Collatz-like behavior of Busy Beavers".sligocki. Retrieved2022-07-12.
• Aaronson, Scott (1999),Who can name the bigger number?
• Weisstein, Eric W."Busy Beaver".MathWorld.
• Busy Beaver Turing Machines - Computerphile, Youtube
• Pascal Michel.The Busy Beaver Competition: a historical survey. 70 pages. 2017. <hal-00396880v5>
• OEISsequence A060843 (Busy Beaver problem)

• Computability theory
• Theory of computation
• Large integers
• Metaphors referring to animals

• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles that are too technical from October 2016
• All articles that are too technical
• Wikipedia references cleanup from July 2024
• All articles needing references cleanup
• Articles covered by WikiProject Wikify from July 2024
• All articles covered by WikiProject Wikify
• Articles with multiple maintenance issues
• All articles with unsourced statements
• Articles with unsourced statements from September 2024
• Articles needing additional references from July 2024
• All articles needing additional references
• Articles with unsourced statements from February 2022
• Articles with unsourced statements from June 2024
• Articles with unsourced statements from July 2024
• Articles with unsourced statements from January 2023
• CS1 Slovak-language sources (sk)