Editing Busy beaver (section)

===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''}}.)