View source for Busy beaver

{{Short description|Longest-running Turing machine of a given size}}
{{for multi|the 1931 Silly Symphonies animated film|The Busy Beavers|the online children's educational program|Busy Beavers|other uses}}
{{multiple issues|
{{technical|date=October 2016}}
{{Citation style|date=July 2024}}
}}[[File:Busy Beaver 5 State 2 Color.png|thumb|300px|This "space-time diagram"<ref>{{Cite web |title=The Busy Beaver Challenge: Story # space-time-diagrams |url=https://bbchallenge.org/story#space-time-diagrams |access-date=2024-07-09 |website=bbchallenge.org |language=en}}</ref> shows the first 100,000 timesteps of the best 5-state busy beaver from top to bottom. Orange is "1", white is "0" (image compressed vertically).]]In [[theoretical computer science]], the '''busy beaver game''' aims at finding a terminating [[Computer program|program]] of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps.<ref name=":2">{{Cite web |last=Weisstein |first=Eric W |title=Busy Beaver |url=https://mathworld.wolfram.com/BusyBeaver.html |access-date=21 November 2023 |website=Wolfram MathWorld}}</ref> Since an [[endless loop|endlessly looping]] program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game.<ref name=":2" /> Rather than traditional programming languages, the programs used in the game are n-state [[Turing machine|Turing machines]],<ref name=":2" /> one of the first mathematical models of computation.<ref name=":4">{{Cite web |last=Brubaker |first=Ben |date=2024-07-02 |title=Amateur Mathematicians Find Fifth 'Busy Beaver' Turing Machine |url=https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ |access-date=2024-07-03 |website=Quanta Magazine |language=en}}</ref>

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.<ref name="rado" /> The ''n-''state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has ''n'' states and eventually halts.<ref name=":2" /> 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).<ref name=":2" /> 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.

An '''''n''th busy beaver''', '''BB-''n''''' or simply "busy beaver" is a Turing machine that wins the ''n''-state busy beaver game.<ref name=":1">{{Cite web |last=Pavlus |first=John |date=10 December 2020 |title=How the Slowest Computer Programs Illuminate Math's Fundamental Limits |url=https://quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/ |access-date=2020-12-11 |website=Quanta Magazine |language=en}}</ref> 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.<ref name="rado">{{cite journal |last=Radó |first=Tibor |author-link=Tibor Radó |date=May 1962 |title=On non-computable functions |url=https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf |journal=[[Bell System Technical Journal]] |volume=41 |issue=3 |pages=877–884 |doi=10.1002/j.1538-7305.1962.tb00480.x}}</ref>

Deciding the running time or score of the ''n''th Busy Beaver is [[incomputable]].<ref name="rado" /> In fact, both the functions Σ(n) and S(n) eventually become larger than any computable function.<ref name="rado" /> This has implications in [[computability theory]], the [[halting problem]], and [[Computational complexity theory|complexity theory]].<ref name=":62">{{Cite journal |last=Aaronson |first=Scott |date=2020-09-29 |title=The Busy Beaver Frontier |url=https://doi.org/10.1145/3427361.3427369 |journal=SIGACT News |volume=51 |issue=3 |pages=32–54 |doi=10.1145/3427361.3427369 |issn=0163-5700}} [https://scottaaronson.com/papers/bb.pdf PDF available] from author.</ref> The concept was first introduced by [[Tibor Radó]] in his 1962 paper, "On Non-Computable Functions".<ref name="rado" /> 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".<ref name=":1" /> 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.<ref name=":1" /> Many other problems, including the [[Riemann hypothesis]] (744 states) and the consistency of [[Zermelo–Fraenkel set theory|ZF set theory]] (745 states<ref name="AaronsonJuly2023" /><ref name=":3">{{Cite thesis |last=Riebel |first=Johannes |title=The Undecidability of BB(748): Understanding Gödel's Incompleteness Theorems |date=March 2023 |access-date=24 September 2024 |degree=Bachelor's |publisher=[[University of Augsburg]] |url=https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf}}</ref>), can be expressed in a similar form, where at most a [[Countable set|countably infinite]] number of cases need to be checked.<ref name=":1" />

==Technical definition==
[[File:Moves_of_a_3-state_Busy_Beaver.jpg|thumb|440x440px|Moves of a 3-state Busy Beaver. This is one of several Busy Beavers that give the maximum number of 1's at the halting point (namely 6). The arrows show the moves depending on the state and on whether the machine reads a 0 or a 1. "P" means to print a 1 before moving right or left ("R" or "L").]]
The '''''n''-state busy beaver game''' (or '''BB-''n'' game'''), introduced in [[Tibor Radó]]'s 1962 paper, involves a class of [[Turing machine]]s, each member of which is required to meet the following design specifications:

*The machine has ''n'' "operational" states plus a Halt state, where ''n'' is a positive integer, and one of the ''n'' states is distinguished as the starting state. (Typically, the states are labelled by 1, 2, ..., ''n'', with state 1 as the starting state, or by ''A'', ''B'', ''C'', ..., with state ''A'' 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's ''transition function'' takes two inputs:
:#the current non-Halt state,
:#the symbol in the current tape cell,
:and produces three outputs:
:#a symbol to write over the symbol in the current tape cell (it may be the same symbol as the symbol overwritten),
:#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
:#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'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.

=== Example ===

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.

== Functions ==
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).<ref name="rado" /> Both take a number of Turing machine states <math>n</math> 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 <math>n</math>-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 <math>n</math>-state Turing machine can undergo before halting.<ref name="rado" /> He proved that both of these functions were [[Noncomputable function|noncomputable]], because they each grew faster than any computable function.<ref name="rado" /> The function BB(n) has been defined to be either of these functions,{{Citation needed|date=September 2024}} 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.<ref name=":6" /> For example:<ref name=":6" />
* The function <math>\text{num}(n)</math> is defined to be the maximum number of ''contiguous'' ones a halting Turing machine can write on a blank tape. In other words, this is the largest [[Unary Number System|unary number]] a Turing machine of ''n'' states can write on a tape.
* The function <math>\text{space}(n)</math> is defined to be the maximal number of tape squares a halting Turing machine can ''read'' (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 maximal [[space complexity]] of an ''n''-state Turing machine.
These four functions together stand in the relation <math>\text{num}(n) \leq \Sigma(n) \leq \text{space}(n) \leq S(n)</math>.<ref name=":6" /> More functions can also be defined by operating the game on different computing machines, such as 3-symbol Turing machines,<ref name=":5" /> non-deterministic Turing machines,<ref name="NDTM" /> the [[lambda calculus]] {{OEIS|A333479}} or even arbitrary programming languages.<ref name=":5" />

===Score function Σ===

The score function quantifies the maximum score attainable by a busy beaver on a given measure. This is a [[noncomputable function]], because it grows [[asymptotic analysis|asymptotically]] faster than any computable function.<ref>Chaitin (1987)</ref>

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

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 {{math|1=''σ''(''M'') = Σ(''n'')}} (i.e., which attains the maximum score) is called a busy beaver.  For each ''n'', there exist at least 4(''n'' &minus; 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.)

==== Non-computability ====
Radó's 1962 paper proved that if <math>f: \mathbb{N} \to \mathbb{N}</math> is any [[computable function]], then Σ(''n'') > ''f''(''n'') for all sufficiently large ''n'', and hence that Σ is not a computable function.<ref name="rado" />

Moreover, this implies that it is [[Undecidable problem|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 {{OEIS|A028444}}. Σ(''n'') has not yet been determined for any instance of ''n'' > 5, although lower bounds have been established (see the [[#Known results|Known values]] section below).

====Complexity and unprovability of Σ====

A variant of [[Kolmogorov complexity]] is defined as follows:<ref>Boolos, Burgess & Jeffrey, 2007. "Computability and Logic"</ref>  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 number]]s, 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 {{math|''n'' > Σ(''k'')}} 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 [[Knuth's up-arrow notation|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 {{math|1=Σ(10⇈10) = ''n''}}, and there are infinitely many true-but-unprovable sentences of the form {{math|Σ(10⇈10) < ''n''}}.)

===Maximum shifts function ''S''===
In addition to the function Σ, Radó [1962] introduced another extreme function for Turing machines, the '''maximum shifts function''', ''S'', defined as follows:<ref name="rado" />

* {{math|''s''(''M'')}} = the number of shifts ''M'' makes before halting, for any {{math|''M'' ∈ ''E''<sub>''n''</sub>}},
* {{math|1=''S''(''n'') = max{{mset|''s''(''M'') | ''M'' ∈ ''E''<sub>''n''</sub>}}}} = the largest number of shifts made by any halting ''n''-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 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.<ref name="rado" />

The following connection between Σ and ''S'' was used by Lin & Radó [''Computer Studies of Turing Machine Problems'', 1965] to prove that Σ(3) = 6 and that S(6)=21:  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 (after unsuccessfully conjecturing 18), then to simulate all the essentially different 3-state machines (82,944 machines, equal to 2{{sup|10}}3{{sup|4}}) 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 that ''S''(3) = 21, and also determined that Σ(3) = 6, which was attained by several machines, all halting after 11 to 14 steps.<ref name=":10" />

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<ref>{{cite report |title=A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory |author=Adam Yedidia and Scott Aaronson |date=May 2016 |arxiv=1605.04343 |bibcode=2016arXiv160504343Y |institution=MIT |type=Technical Report}}</ref> 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 ([[Ramsey cardinal|stationary Ramsey property]]).<ref>{{Cite web |last=Aron |first=Jacob |title=This Turing machine should run forever unless maths is wrong |url=https://newscientist.com/article/2087845-this-turing-machine-should-run-forever-unless-maths-is-wrong/ |access-date=2016-09-25 |website=NewScientist |language=en-US}}</ref><ref name=":0">Version from May 3rd contained 7918 states: {{cite news |date=2016-05-03 |title=The 8000th Busy Beaver number eludes ZF set theory |url=https://scottaaronson.com/blog/?p=2725 |access-date=2016-09-25 |work=Shtetl-Optimized blog}}</ref> Stefan O'Rear then reduced it to 1919 states, with the dependency on the stationary Ramsey property eliminated,<ref name="Aaronson3">{{cite news |date=2016-05-03 |title=Three announcements |url=https://scottaaronson.com/blog/?p=2741 |access-date=2018-04-27 |work=Shtetl-Optimized blog}}</ref><ref>{{Cite web |date=2019-02-13 |title=GitHub - sorear/metamath-turing-machines: Metamath proof enumerators and other things. |url=https://github.com/sorear/metamath-turing-machines/blob/master/sample_out/zf.tm |website=[[GitHub]]}}</ref> and later to 748 states.<ref name=":62" /> In July 2023, Riebel reduced it to 745 states.<ref name="AaronsonJuly2023">{{Cite web |date=2023-07-05 |title=Life, blogging, and the Busy Beaver function go on |url=https://scottaaronson.blog/?p=7388 |access-date=2023-08-27}}</ref><ref name=":3" />

===Proof for uncomputability of ''S''(''n'') and Σ(''n'')===
{{Unreferenced|section|date=July 2024}}
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 2''n'' 1s on the tape and then halt. 
Let us create the composition ''Double'' | ''EvalS'' | ''Clean'' and let ''n''<sub>0</sub> be the number of states of this machine. Let ''Create_n<sub>0</sub>'' denote a Turing machine creating ''n''<sub>0</sub> 1s on an initially blank tape. This machine may be constructed in a trivial manner to have ''n''<sub>0</sub> states (the state ''i'' writes 1, moves the head right and switches to state ''i'' + 1, except the state ''n''<sub>0</sub>, which halts). Let ''N'' denote the sum ''n''<sub>0</sub> + ''n''<sub>0</sub>.

Let ''BadS'' denote the composition ''Create_n<sub>0</sub>'' | ''Double'' | ''EvalS'' | ''Clean''. Notice that this machine has ''N'' states. Starting with an initially blank tape it first creates a sequence of ''n''<sub>0</sub> 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.

=== Uncomputability of space(n) and num(n) ===
Both <math>\text{space}(n)</math> and <math>\text{num}(n)</math> functions are uncomputable .<ref name=":6" /> This can be shown for <math>\text{space}(n)</math> by noting that every tape square a Turing machine writes a one to, it must also visit: in other words, <math>\Sigma(n) \leq \text{space}(n)</math>.<ref name=":6" />  The <math>\text{num}(n)</math> function can be shown to be incomputable by proving, for example, that <math>\text{space}(n) < \text{num}(3n + 3)</math>: this can be done by designing an ''(3n+3)''-state Turing machine which simulates the ''n''-state space champion, and then uses it to write at least <math>\text{space}(n)</math> contiguous ones to the tape.<ref name=":6" />

== Generalizations ==
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.<ref name=":5">{{Cite web |last=Aaronson |first=Scott |date=2024-07-02 |title=BusyBeaver(5) is now known to be 47,176,870 |url=https://scottaaronson.blog/?p=8088 |access-date=2024-07-04 |website=Shtetl-Optimized |language=en-US}}</ref> 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.<ref name=":5" /> Alternatively a "busy beaver function" for diverse models of computation can be defined with [[Kolmogorov complexity]].<ref name=":5" /> This is done by taking <math>{BB}(n)</math> to be the largest integer <math>m</math> such that <math>K_L(m) \le n</math>, where <math>K_L(m)</math> is the length of the shortest program in <math>L</math> that outputs <math>m</math>: <math>{BB}(n)</math> is thereby the largest integer a program with length <math>n</math> or less can output in <math>L</math>.<ref name=":5" />

The longest running 6-state, 2-symbol machine which has the additional property of reversing the tape value at each step produces {{val|6147}} 1s after {{val|47339970}} steps.{{Citation needed|date=February 2022}} So for the Reversal Turing Machine (RTM) class,<ref>{{Cite web |title=Reversal Turing machine |url=https://skelet.ludost.net/bb/RTM.htm |access-date=2022-02-10 |website=skelet.ludost.net}}</ref> ''S''<sub>RTM</sub>(6) ≥ {{val|47339970}} and Σ<sub>RTM</sub>(6) ≥ {{val|6147}}. Likewise we could define an analog to the Σ function for [[register machine]]s as the largest number which can be present in any register on halting, for a given number of instructions.{{Citation needed|date=June 2024}}

=== Different numbers of symbols ===
A simple generalization is the extension to Turing machines with ''m'' symbols instead of just 2 (0 and 1).<ref name=":5" /> 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''':
# Σ(''n'', ''m''): the largest number of non-zeros printable by an ''n''-state, ''m''-symbol machine started on an initially blank tape before halting,{{Citation needed|date=June 2024}} and
# ''S''(''n'', ''m''): the largest number of steps taken by an ''n''-state, ''m''-symbol machine started on an initially blank tape before halting.<ref name=":5" />

For example, the longest-running 3-state 3-symbol machine found so far runs {{val|119112334170342540}} steps before halting<!--[https://cse.unr.edu/~al/BusyBeaver.html]-->.<ref name="michel_comp" />{{Better source needed|reason=The current source is insufficiently reliable ([[WP:NOTRS]]).|date=July 2024}}

=== Nondeterministic Turing machines ===
{| class="wikitable" align="right"
|+ Maximal Halting Times and States from ''p''-case, 2-state, 2-color NDTM<ref name="NDTM">{{cite web |last1=Wolfram |first1=Stephen |author-link=Stephen Wolfram |date=4 February 2021 |title=Multiway Turing Machines |url=https://wolframphysics.org/bulletins/2021/02/multiway-turing-machines/ |website=www.wolframphysics.org |language=en}}</ref>
! p
! steps
! states
|-
! 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 machine]]s by looking for the system with the most states across all branches or the branch with the longest number of steps.<ref name="NDTM" /> 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.

==Applications==

=== Open mathematical problems ===
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 problem in mathematics|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''.<ref name=":1" /><ref name=":9">{{cite book |last=Chaitin |first=Gregory J. |author-link=Gregory Chaitin |title=Open Problems in Communication and Computation |publisher=Springer |year=1987 |isbn=978-0-387-96621-2 |editor1-last=Cover |editor1-first=T. M. |pages=108–112 |chapter=Computing the Busy Beaver Function |access-date=2022-07-07 |editor2-last=Gopinath |editor2-first=B. |chapter-url=https://cs.auckland.ac.nz/~chaitin/bellcom.pdf |archive-url=https://web.archive.org/web/20171230195953/https://www.cs.auckland.ac.nz/~chaitin/bellcom.pdf |archive-date=2017-12-30 |url-status=dead}}</ref> 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.<ref name=":62" />

Consider any <math>\Pi_1^0</math> [[conjecture]]: any conjecture that could be [[mathematical proof|disproven]] via a [[counterexample]] among a [[countable]] 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 an ''n''-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 halts ''only'' if it finds a counterexample.)<ref name=":62" />

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.<ref name=":62" /> Thus specific values (or upper bounds) for ''S''(''n'') could be, in theory, used to systematically solve many open problems in mathematics.<ref name=":62" />

However, current results on the busy beaver problem suggest that this will not be practical for two reasons:{{citation needed|date=July 2024}}
* It is extremely hard to prove values for the busy beaver function (and the max shift function). Every known exact value of ''S''(''n'') was proven by enumerating every ''n''-state Turing machine and proving whether or not each halts. One would have to calculate ''S''(''n'') by some less direct method for it to actually be useful.{{citation needed|date=July 2024}}
* 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 <math>10^{(10^{(10^{(10^{(\ldots)})})})}</math> with a stack of 15 tens.<ref name=":5" />{{Better citation needed|reason=The current source is insufficiently reliable ([[WP:NOTRS]]).|date=July 2024}} 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 the [[Goldbach's conjecture|Goldbach 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.<ref name=":1" />

==== Consistency of theories ====
Another property of S(n) is that no arithmetically sound, computably axiomatized [[Axiomatic system|theory]] can prove all of the function's values. Specifically, given a computable and arithmetically sound theory <math>T</math>, there is a number <math>n_T</math> such that for all <math>n \geq n_T</math>, no statement of the form <math>S(n) = k</math> can be proved in <math>T</math>.<ref name=":62" /> 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 <math>T</math>, a Turing machine with <math>n_T</math> states can be designed to enumerate every possible proof in <math>T</math>.<ref name=":62" /> 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, <math>0 = 1</math>.<ref name=":62" /> Any theory that proves the value of <math>S(n_T)</math> proves its own consistency, violating [[Gödel's incompleteness theorems|Gödel's second incompleteness theorem]].<ref name=":62" /> This can be used to place various theories on a scale, for example the various [[Large cardinal axiom|large cardinal axioms]] in [[ZFC]]: if each theory <math>T</math> is assigned as its number <math>n_T</math>, theories with larger values of <math>n_T</math> prove the consistency of those below them, placing all such theories on a countably infinite scale.<ref name=":62" />

==== Notable examples ====
* A 745-state binary Turing machine has been constructed that halts [[if and only if]] [[ZFC]] is inconsistent.<ref name="AaronsonJuly2023" /><ref name=":3" />

* A 744-state Turing machine has been constructed that halts if, and only if, the [[Riemann hypothesis]] is false.<ref name="Aaronson3" /><ref name=":1" />

* In 2016, a 43-state Turing machine was constructed that halts if, and only if, [[Goldbach's conjecture]] is false. This was further reduced to 27-state machine, <ref name="Aaronson3" /><ref name=":1" /> and in 2024 this construction was formally proved and verified in the [[Lean 4]] theorem proving language.<ref>{{cite web|last=Leng|first=Yijun|title=GitHub Repository "goldbach_tm27"|website=[[GitHub]] |url=https://github.com/lengyijun/goldbach_tm}}</ref>

* A 15-state Turing machine has been constructed that halts if and only if the following conjecture formulated by [[Paul Erdős]] in 1979 is false: for all ''n'' > 8 there is at least one digit 2 in the base 3 representation of 2<sup>''n''</sup>.<ref>{{cite report |title=On the hardness of knowing busy beaver values BB(15) and BB(5,4) |author=Tristan Stérin and Damien Woods |date=July 2021 |arxiv=2107.12475 |institution=Maynooth University |type=Technical Report}}</ref><ref>{{cite journal |last=Erdõs |first=Paul |author-link=Paul Erdõs |date=1979 |title=Some unconventional problems in number theory. |url=https://jstor.org/stable/2689842 |journal=[[Math. Mag.]] |volume=52 |issue=2 |pages=67–70 |doi=10.1080/0025570X.1979.11976756 |jstor=2689842}}</ref>

=== Universal Turing machines ===
Exploring the relationship between computational universality and the dynamic behavior of Busy Beaver [[Turing machines]], a conjecture was proposed in 2012<ref name="“conjecture">{{Cite journal |last=Zenil |first=Hector |date=2012 |title=On the Dynamic Qualitative Behaviour of Universal Computation |url=https://www.complex-systems.com/abstracts/v20_i03_a08/ |journal=Complex Systems |volume=20 |issue=3 |pages=265–277 |doi=10.25088/ComplexSystems.20.3.265 |issn=0891-2513}} [https://content.wolfram.com/sites/13/2019/01/20-3-8.pdf PDF available] from publisher.</ref> 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.

== Known results ==
=== Lower bounds ===

==== Green machines ====
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".<ref>{{Cite journal |last=Brady |first=Allen H. |date=March 1998 |title=Heiner Marxen and Jürgen Buntrock. Attacking the busy beaver 5. Bulletin of the European Association for Theoretical Computer Science, no. 40 (Feb.1990), pp. 247–251. - Pascal Michel. Busy beaver competition and Collatz-like problems. Archive for mathematical logic, vol. 32 (1993), pp. 351–367. |url=https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/heiner-marxen-and-jurgen-buntrock-attacking-the-busy-beaver-5-bulletin-of-the-european-association-for-theoretical-computer-science-no-40-feb1990-pp-247251-pascal-michel-busy-beaver-competition-and-collatzlike-problems-archive-for-mathematical-logic-vol-32-1993-pp-351367/D18FE9FA2B022BD2960AEF1E8AE28178# |journal=The Journal of Symbolic Logic |language=en |volume=63 |issue=1 |pages=331–332 |doi=10.2307/2586607 |jstor=2586607 |issn=0022-4812}} [https://turbotm.de/~heiner/BB/mabu90.html Free HTML version by author]</ref> This lower bound can be calculated but is too complex to state as a single expression in terms of ''n''.<ref name=":7">{{Cite journal |last=Green |first=Milton W. |date=1964-11-11 |title=A lower bound RADO's sigma function for binary turing machines |url=https://doi.org/10.1109/SWCT.1964.3 |journal=Proceedings of the 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design |series=SWCT '64 |location=USA |publisher=IEEE Computer Society |pages=91–94 |doi=10.1109/SWCT.1964.3}}</ref> This was done with a set of Turing machines, each of which demonstrated the lower bound for a certain ''n''.<ref name=":7" /> When ''n''=8 the method gives
: <math>\Sigma(8) \geq 3 \times (7 \times 3^{92} - 1) / 2 \approx 8.248 \times 10^{44}</math>.

In contrast, the best current (as of 2024) lower bound on <math>\Sigma(6)</math> is <math>10 \uparrow\uparrow 15</math>, where each <math>\uparrow</math> is [[Knuth's up-arrow notation]].<ref name=":5" /> This represents <math>10^{(10^{(10^{(10^{(\ldots)})})})}</math>, an exponentiated chain of 15 tens equal to <math>10^{10 \uparrow\uparrow 14}</math>. The value of <math>\Sigma(8)</math> 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.<ref name=":7" /> Defining the value of the N-state busy-beaver competitor on a tape containing <math>m</math> ones to be <math>B_N(m)</math> (the ultimate output of each machine being its value on <math>m = 0</math>, because a blank tape has 0 ones), the recursion relations are as follows:<ref name=":7" /> a
: <math>B_N(0) = 1</math>
: <math>B_1(m) = m + 1</math>
: <math>B_N(m) = 1 + B_{N-2}(1 + B_N(m - 1))</math>
This leads to two formulas, for odd and even numbers, for calculating the lower bound given by the Nth machine, <math>G(N)</math>:
: <math>G(N) = B_{N-2}(B_{N-2}(1))</math> for odd N
: <math>G(N) = 1 + B_{N-3}(1 + B_{N-3}(1))</math> for even N
The lower bound BB(N) can also be related to the [[Ackermann function]]. It can be shown that:<ref name=":8">{{cite journal
 | last1 = Ben-Amram | first1 = A. M.
 | last2 = Petersen | first2 = H.
 | doi = 10.1007/s00224-001-1052-0
 | issue = 1
 | journal = Theory of Computing Systems
 | mr = 1879169
 | pages = 1–11
 | title = Improved bounds for functions related to busy beavers
 | volume = 35
 | year = 2002}}</ref>
: <math>A(n,n) > G(4N+3) > A(4, 2N+1)</math>

==== Relationships between Busy beaver functions ====
Trivially, S(n) ≥ Σ(n) because a machine that writes Σ(n) ones must take at least Σ(n) steps to do so.<ref name=":8" /> It is possible to give a number of upper bounds on the time S(n) with the number of ones Σ(n):
* <math>S(n) \leq (n + 1) \times \Sigma(5n) \times 2^{\Sigma(5n)}</math> &nbsp; (Rado<ref name=":8" />)
* <math>S(n) \leq \Sigma(9n)</math> &nbsp; (Buro<ref name=":8" />)
* <math>S(n) \leq (2n - 1) \times \Sigma(3n + 3)</math> &nbsp; (Julstrom and Zwick<ref name=":8" />)
By defining num(n) to be the maximum number of ones an ''n''-state Turing machine is allowed to output contiguously, rather than in any position (the largest [[Unary numeral system|unary number]] it can output), it is possible to show:<ref name=":8" />
: <math>\text{num}(n) < \Sigma(n)</math>
: <math>S(n) < \text{num}(n + o(n))</math>
: <math>S(n) < \text{num}(3n+6)</math> &nbsp; (Ben-Amram, et al., 1996<ref name=":6">{{Cite journal |last1=Ben-Amram |first1=A. M. |last2=Julstrom |first2=B. A. |last3=Zwick |first3=U. |date=1996-08-01 |title=A note on busy beavers and other creatures |url=https://doi.org/10.1007/BF01192693 |journal=Mathematical Systems Theory |language=en |volume=29 |issue=4 |pages=375–386 |doi=10.1007/BF01192693 |issn=1433-0490}}</ref>)

Ben-Amram and Petersen, 2002, also give an asymptotically improved bound on S(n). There exists a constant ''c'', such that for all {{math|''n'' ≥ 2}}:<ref name=":8"/>

:<math>S(n) \le \Sigma\left(n + \left\lceil \frac{8n}{\log_2 n} \right\rceil + c\right). </math>

===Exact values and lower and upper bounds===
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)). So, space(6) is known to be greater than 10⇈15, as space(n) ≥ Σ(n) and Σ(6) > 10⇈15. {{val|47176870}} is an upper bound for space(5), because S(5) = {{val|47176870}} (<ref name=":4" />) and S(n) ≥ space(n). 4098 is an upper bound for num(5), because Σ(5) = 4098 (<ref name=":8" />) and Σ(n) ≥ num(n). The last entry listed as "?" is num(6), because Σ(6) > 10⇈15, but Σ(n) ≥ num(n).
{| class="wikitable"
|+Values of busy beaver functions
!Function
!2-state
!3-state
!4-state
!5-state
!6-state
|-
|'''S(n)'''
|6 (<ref name=":62" />)
|21 (<ref name=":62" />)
|107 (<ref name=":62" />)
|{{val|47176870}} (<ref name=":4" />)
|> 10⇈15 (<ref name=":5" />)
|-
|'''space(n)'''
|4 (<ref name=":8" />)
|7 (<ref name=":8" />)
|16 (<ref name=":8" />)
|≥ {{val|12289}} (<ref name=":8" />)
≤ {{val|47176870}} (S(n) ≥ space(n))
|> 10⇈15 (space(n) ≥ Σ(n))
|-
|'''Σ(n)'''
|4 (<ref name=":8" />)
|6 (<ref name=":8" />)
|13 (<ref name=":8" />)
|4098 (<ref name=":8" />)
|> 10⇈15 (<ref name="ligocki_bb6" />)
|-
|'''num(n)'''
|4 (<ref name=":8" />)
|6 (<ref name=":8" />)
|12 (<ref name=":8" />)
|≤ 4098 (Σ(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 in [[Coq (software)|Coq]].<ref>{{Cite web |date=2024-07-02 |title=[July 2nd 2024] We have proved "BB(5) = 47,176,870" |url=https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 |access-date=2024-07-02 |website=The Busy Beaver Challenge |language=en}}</ref><ref>{{Cite web |title=The Busy Beaver Challenge |url=https://bbchallenge.org/ |access-date=2024-07-02 |website=bbchallenge.org |language=en}}</ref>

=== List of busy beavers ===
{{for|an example of a 3-state busy beaver's state table and its "run"|Turing machine examples#3-state Busy Beaver|Turing machine examples}}[[File:Busy Beaver 5 spacetime.png|thumb|480px|A zoomed-out space-time diagram of the 5-state busy beaver machine (for S(n), then Σ(n)). The machine runs for 47,176,870 steps, peaking with 12288 zeroes, and leaving behind 4098 zeroes upon halt. <br />The diagram is compressed so only steps which change the tape are shown. Green and yellow triangles indicate regions where the Turing machine shuttles back and forth; the time taken is proportional to the areas of these colored triangles. The bottom row is an excerpt of the tape and the read/write head upon halting.]]These are tables of rules for 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 <span style="color:red">'''H'''</span>.

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 {{overline|overlined}}, halts at the position {{underline|underlined}})

:{| class="wikitable"
|+ 1-state, 2-symbol busy beaver
! width="20px" |
! A
|-
! 0
| 1R<span style="color:red">'''H'''</span>
|-
! 1
| (not used)
|}

'''Result:''' 0 0 {{overline|1}} {{underline|0}} 0 (1 step, one "1" total)

:{| class="wikitable"
|+ 2-state, 2-symbol busy beaver{{cn|date=January 2023}}
! width="20px" |
! A
! B
|-
! 0
| 1R'''B'''
| 1L'''A'''
|-
! 1
| 1L'''B'''
| 1R<span style="color:red">'''H'''</span>
|}

'''Result:''' 0 0 1 1 {{underline|{{overline|1}}}} 1 0 0 (6 steps, four "1"s total)

[[File:3-state, 2-symbol Busy Beaver animation.gif|thumb|Animation of a 3-state, 2-symbol busy beaver]]

:{| class="wikitable"
|+ 3-state, 2-symbol busy beaver<ref>{{cite thesis | type=Ph.D. thesis | url=http://rave.ohiolink.edu/etdc/view?acc_num=osu1486554418657614 | author=Shen Lin | title=Computer studies of Turing machine problems | institution=[[Ohio State University]] | year=1963 }}</ref><ref name=":10">{{cite journal |last1=Lin |first1=Shen |last2=Rado |first2=Tibor |title=Computer studies of Turing machine problems. |journal=Journal of the ACM |date=April 1965 |volume=12 |issue=2 |pages=196–212|doi=10.1145/321264.321270 |s2cid=17789208 |doi-access=free }}</ref>
! width="20px" |
! A
! B
! C
|-
! 0
| 1R'''B'''
| 0R'''C'''
| 1L'''C'''
|-
! 1
| 1R<span style="color:red">'''H'''</span>
| 1R'''B'''
| 1L'''A'''
|}

'''Result:''' 0 0 1 {{overline|1}} 1 {{underline|1}} 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 for ''S''. (''S''(3) = 21, and the machine obtains only five 1s.<ref name=":10"/>)

[[File:4-state, 2-symbol Busy Beaver animation.gif|thumb|Animation of a 4-state, 2-symbol busy beaver]]

:{| class="wikitable"
|+ 4-state, 2-symbol busy beaver
! width="20px" |
! A
! B
! C
! D
|-
! 0
| 1R'''B'''
| 1L'''A'''
| 1R<span style="color:red">'''H'''</span>
| 1R'''D'''
|-
! 1
| 1L'''B'''
| 0L'''C'''
| 1L'''D'''
| 0R'''A'''
|}

'''Result:''' 0 0 1 {{underline|0}} 1 1 1 1 1 1 1 1 {{overline|1}} 1 1 1 0 0 (107 steps, thirteen "1"s total)

:{| class="wikitable"
|+ 5-state, 2-symbol busy beaver
! width="20px" |
! A
! B
! C
! D
! E
|-
! 0
| 1R'''B'''
| 1R'''C'''
| 1R'''D'''
| 1L'''A'''
| 1R<span style="color:red">'''H'''</span>
|-
! 1
| 1L'''C'''
| 1R'''B'''
| 0L'''E'''
| 1L'''D'''
| 0L'''A'''
|}

'''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]]. 

:{| class="wikitable"
|+ current 6-state, 2-symbol best contender<ref name=michel_comp>Pascal Michel's [https://bbchallenge.org/~pascal.michel/bbc.html Busy Beaver Competitions] page listing best contenders known.</ref><ref name="ligocki_bb6">{{Cite web |last=Ligocki |first=Shawn |date=2022-06-21 |title=BB(6, 2) > 10↑↑15 |url=https://www.sligocki.com//2022/06/21/bb-6-2-t15.html |access-date=2024-07-04 |website=sligocki |language=en}}</ref>
! width="20px" |
! A
! B
! C
! D
! E
! F
|-
! 0
| 1R'''B'''
| 1R'''C'''
| 1L'''C'''
| 0L'''E'''
| 1L'''F'''
| 0R'''C'''
|-
! 1
| 0L'''D'''
| 0R'''F'''
| 1L'''A'''
| 1R<span style="color:red">'''H'''</span>
| 0R'''B'''
| 0R'''E'''
|}

'''Result:''' 1 {{underline|0}} 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<sup>10<sup>.<sup>.<sup>10</sup></sup></sup></sup>, an exponential tower of 15 tens).

==Visualizations==

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).

{{Multiple image
| perrow            = 4
<!-- Layout parameters -->
| align             = left
| direction         = horizontal
| background color  = 
| caption_align     = center
| image_style       = 
| image_gap         = 0

<!-- Header -->
<!-- | header_background = header background as a 'hex triplet' web color (include the initial #) -->
| header_align      = center
| header            = Evolution of busy beavers with 1-4 states

<!--image 1-->
| image1            = Busybeaver1rules.png
| width1            = 75
| caption1          = Rules for 1-state busy beaver

<!--image 2-->
| image2            = Busybeaver2rules.png
| width2            = 200
| caption2          = Rules for 2-state busy beaver

<!--image 3-->
| image3            = Busybeaver3rules.png
| width3            = 225
| caption3          = Rules for 3-state busy beaver

<!--image 4-->
| image4            = Busybeaver4rules.png
| width4            = 300
| caption4          = Rules for 4-state busy beaver

<!--image 5-->
| image5            = Busybeaver1.svg
| width5            = 75
| caption5          = Evolution of 1-state busy beaver until halt. The initial state triggers a halt, with a single "1" being written before termination.

<!--image 6-->
| image6            = Busybeaver2.svg
| width6            = 200
| caption6          = Evolution of 2-state busy beaver until halt

<!--image 7-->
| image7            = Busybeaver3.svg
| width7            = 225
| caption7          = Evolution of 3-state busy beaver until halt

<!--image 8-->
| image8            = Busybeaver4.png
| width8            = 300
| caption8          = 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).

<!-- Footer -->
| footer_background = <!-- footer background as a 'hex triplet' web color (include the initial #) -->
| footer_align      = <!-- left (default), center, right -->
| footer            = <!-- footer text -->
}}{{-}}

==See also==
*[[Rayo's number]]
*[[Turmite]]

==Notes==
<references />

==References==
{{refbegin}}
* {{cite journal | last = Radó | first = Tibor | author-link = Tibor Radó | url = https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf | title = On non-computable functions | journal = [[Bell System Technical Journal]] | volume = 41 | issue = 3 | date = May 1962 | pages = 877–884 | doi = 10.1002/j.1538-7305.1962.tb00480.x }}
*: This is where Radó first defined the busy beaver problem and proved that it was uncomputable and grew faster than any computable function.
* {{cite journal | last1 = Lin | first1 = Shen | last2 = Radó | first2 = Tibor | author-link2 = Tibor Radó | title = Computer Studies of Turing Machine Problems | journal = [[Journal of the ACM]] | volume = 12 | issue = 2 | date = April 1965 | pages = 196–212 | doi = 10.1145/321264.321270 | s2cid = 17789208 | url = https://rave.ohiolink.edu/etdc/view?acc_num=osu1486554418657614 | doi-access = free }}
*: 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.) 
* {{cite journal | last1 = Brady | first1 = Allen H. | title = The determination of the value of Rado's noncomputable function Σ(''k'') for four-state Turing machines | journal = [[Mathematics of Computation]] | volume = 40 | issue = 162 |date=April 1983 | pages = 647–665 | jstor = 2007539 | doi = 10.1090/S0025-5718-1983-0689479-6 | doi-access = free }}
*: 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.
* {{cite journal | last1 = Machlin | first1 = Rona | last2 = Stout | first2 = Quentin F. | url = https://eecs.umich.edu/~qstout/abs/busyb.html | title = The complex behavior of simple machines | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]] | volume = 42 | issue = 1–3 | date = June 1990 | pages = 85–98 | doi = 10.1016/0167-2789(90)90068-Z | hdl = 2027.42/28528 | bibcode = 1990PhyD...42...85M | hdl-access = free }}
*: 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 (Ω).
* {{cite journal | last1 = Marxen | first1 = Heiner | last2 = Buntrock | first2 = Jürgen | title = Attacking the Busy Beaver 5 | journal = [[European Association for Theoretical Computer Science|Bulletin of the EATCS]] | volume = 40 | date = February 1990 | pages = 247–251 | url = https://turbotm.de/~heiner/BB/mabu90.html | access-date = 2020-01-19 | archive-url = https://web.archive.org/web/20061009135243/https://drb.insel.de/~heiner/BB/mabu90.html | archive-date = 2006-10-09 | url-status = live }}
*: Marxen and Buntrock demonstrate that Σ(5)&nbsp;≥&nbsp;4098 and ''S''(5)&nbsp;≥&nbsp;{{val|47176870}} and describe in detail the method they used to find these machines and prove many others will never halt.
* {{cite conference | last1 = Green | first1 = Milton W. | year = 1964 | title = A Lower Bound on Rado's Sigma Function for Binary Turing Machines | conference-url = https://computer.org/csdl/proceedings/focs/1964/5428/00/index.html | conference = 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design | pages = 91–94 | doi = 10.1109/SWCT.1964.3 }}
*: 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]].
* {{cite journal | last = Dewdney | first = Alexander K. |author-link = Alexander Dewdney | title = A computer trap for the busy beaver, the hardest working Turing machine | journal = [[Scientific American]] | volume = 251 | issue = 2 | pages = 10–17 | year = 1984 }}
*: Busy beaver programs are described by [[Alexander Dewdney]] in ''Scientific American'', August 1984, pages 19–23, also March 1985 p.&nbsp;23 and [https://web.archive.org/web/20100709121641/https://grail.cba.csuohio.edu/~somos/busy.html#dewd April 1985 p. 30].
* {{cite book | last = Chaitin | first = Gregory J. | author-link = Gregory Chaitin | chapter = Computing the Busy Beaver Function | editor1-first = T. M. | editor1-last = Cover | editor2-first = B. | editor2-last = Gopinath | title = Open Problems in Communication and Computation | publisher = Springer | year = 1987 | pages = 108–112 | chapter-url = https://cs.auckland.ac.nz/~chaitin/bellcom.pdf | isbn = 978-0-387-96621-2 | access-date = 2022-07-07 | archive-date = 2017-12-30 | archive-url = https://web.archive.org/web/20171230195953/https://www.cs.auckland.ac.nz/~chaitin/bellcom.pdf | url-status = dead }}
* {{cite book | last = Brady | first = Allen H. | chapter = The Busy Beaver Game and the Meaning of Life | pages = 237–254 | editor1-last = Herken | editor1-first = Rolf | title = The Universal Turing Machine: A Half-Century Survey | edition = 2nd | year = 1995 | publisher = Springer-Verlag | location = Wien, New York |isbn = 978-3-211-82637-9 }}
*: 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.&nbsp;247). With 19 references.
* {{cite book | author-link = Taylor L. Booth | first = Taylor L. | last = Booth | title = Sequential Machines and Automata Theory | publisher = Wiley | location =  New York | year = 1967 | isbn = 978-0-471-08848-6 }}
*: 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.&nbsp;396. Problem 3 is to "show that the busy beaver problem is unsolvable... for all values of n."
* {{cite journal | first1 = A. M. | last1 = Ben-Amram | first2 = B. A. | last2 = Julstrom | first3 = U. | last3 = Zwick | author3-link = Uri Zwick | title = A note on Busy Beavers and other creatures | journal = [[Mathematical Systems Theory]] | volume = 29 | issue = 4 | pages = 375–386 | year = 1996 | doi = 10.1007/BF01192693 | url = https://www2.mta.ac.il/~amirben/downloadable/bjz.ps | citeseerx = 10.1.1.75.1297 | s2cid = 30937913 | access-date = 2022-07-07 | archive-date = 2018-07-21 | archive-url = https://web.archive.org/web/20180721082951/http://www2.mta.ac.il/~amirben/downloadable/bjz.ps | url-status = dead }}
*: Bounds between functions Σ and ''S''.
*{{cite journal | first1 = A. M. | last1 = Ben-Amram | first2 = H. | last2 = Petersen | title = Improved Bounds for Functions Related to Busy Beavers | journal = [[Theory of Computing Systems]] | volume = 35 | pages = 1–11 | year =  2002 | doi = 10.1007/s00224-001-1052-0 | citeseerx = 10.1.1.136.5997 | s2cid = 10429773 }}
*: Improved bounds.
* {{cite conference | first1 = G. | last1 = Lafitte | first2 = C. | last2 = Papazian | citeseerx = 10.1.1.104.3021 | title = The fabric of small Turing machines | book-title = Computation and Logic in the Real World, Proceedings of the Third Conference on Computability in Europe |date=June 2007 | pages = 219–227 }}
*: 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.
* {{cite book | first1 = George S. | last1 = Boolos | first2 = John P. | last2 = Burgess | first3 = Richard C. | last3 = Jeffrey | title = Computability and Logic | url = https://archive.org/details/computabilitylog0000bool | url-access = registration | edition = Fifth | year = 2007 | publisher = Cambridge University Press | isbn = 978-0-521-87752-7 }}
* {{cite thesis | first1 = Pavel | last1 = Kropitz | title = Problém Busy Beaver | degree = Bachelor | year = 2010 | publisher = Charles University in Prague | language = sk }}
*: 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.
{{refend}}

==External links==
<!--box-->
{{sister project|project=Wikiversity
|text=[[v:How things work college course/Turing machine quiz|Wikiversity hosts a quiz on the busy beaver]]}}
* The page of <!-- https://web.archive.org/web/20020811035511/https://drb.insel.de/~heiner/BB/ -->[https://turbotm.de/~heiner/BB/ Heiner Marxen], who, with Jürgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine.
* Pascal Michel's [https://bbchallenge.org/~pascal.michel/ha.html Historical survey] of busy beaver results which also contains best results and some analysis.
* Definition of the class [https://skelet.ludost.net/bb/RTM.htm RTM] - Reversal Turing Machines, simple and strong subclass of the TMs.
* "[https://homepages.hass.rpi.edu/heuveb/Research/BB/index.html The Busy Beaver Problem: A New Millennium Attack]" ([https://web.archive.org/web/20140717153332/https://cogsci.rpi.edu/~heuveb/research/BB/ archived]) at the Rensselaer RAIR Lab. This effort found several new records and established several values for the quadruple formalization.
* Daniel Briggs' [https://web.mit.edu/~dbriggs/www/ website] [https://web.archive.org/web/20121026023118/https://web.mit.edu/~dbriggs/www/ archive] and [https://web.archive.org/web/20101227082649/https://dbriggs.scripts.mit.edu/forum/index.php forum] for solving the 5-state, 2-symbol busy beaver problem, based on [https://skelet.ludost.net/bb/nreg.html Skelet] (Georgi Georgiev) nonregular machines list.
* {{Cite web |last=Ligocki |first=Shawn |date=2021-07-17 |title=Collatz-like behavior of Busy Beavers |url=https://www.sligocki.com//2021/07/17/bb-collatz.html |access-date=2022-07-12 |website=sligocki |language=en}}
* Aaronson, Scott (1999), ''[https://scottaaronson.com/writings/bignumbers.html Who can name the bigger number?]''
* {{MathWorld |title=Busy Beaver |urlname=BusyBeaver}}
* [https://youtube.com/watch?v=CE8UhcyJS0I Busy Beaver Turing Machines - Computerphile], Youtube
* Pascal Michel. [https://hal.archives-ouvertes.fr/hal-00396880v5 The Busy Beaver Competition: a historical survey]. 70 pages. 2017. <hal-00396880v5>

{{Authority control}}

[[Category:Computability theory]]
[[Category:Theory of computation]]
[[Category:Large integers]]
[[Category:Metaphors referring to animals]]