Editing Busy beaver (section)

== 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(3)=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 |archive-date=2016-10-20 |archive-url=https://web.archive.org/web/20161020113637/https://www.newscientist.com/article/2087845-this-turing-machine-should-run-forever-unless-maths-is-wrong/ |url-status=live }}</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 |archive-date=2016-09-27 |archive-url=https://web.archive.org/web/20160927020541/http://www.scottaaronson.com/blog/?p=2725 |url-status=live }}</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]] |access-date=2018-05-19 |archive-date=2021-04-17 |archive-url=https://web.archive.org/web/20210417052518/https://github.com/sorear/metamath-turing-machines/blob/master/sample_out/zf.tm |url-status=live }}</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 |archive-date=2023-08-28 |archive-url=https://web.archive.org/web/20230828002248/https://scottaaronson.blog/?p=7388 |url-status=live }}</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" />