Content deleted Content added
Clarify which definition |
|||
Line 41:
This infinite sequence '''Σ''' is the '''busy beaver function''', and 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'''. Note that for each ''n'', there exist at least 4(''n'' − 1)! ''n''-state busy beavers. (Given any ''n''-state busy beaver, another is obtained by merely changing the shift direction in a halting transition, a third by reversing ''all'' shift directions uniformly, and a fourth by reversing the halt direction of the all-swapped busy beaver. Furthermore, a permutation of all states except Start and Halt produces a machine that attains the same score. Theoretically, there could be more than one kind of transition leading to the halting state, but in practice it would be wasteful, because there's only one sequence of state transitions producing the sought-after result.)
There are (4''n'' + 4)<sup>2''n''</sup> ''n''-state Turing machines meeting the definition because the general form of the formula is (''symbols'' × ''directions'' × (''states'' + 1))<sup>(''symbols'' × ''states'')</sup> Given these rules, for any transition to the Halt state, writing a 1 always produces a higher score than writing a 0. Only one direction while transitioning to Halt need be considered, since the final position of the tape does not impact the score. Therefore, in practice, the number of ''n''-state Turing machines to consider can be reduced to (4''n'' + 1)<sup>2''n''</sup>. The search space can be further reduced by a factor of (''n''
==== Non-computability ====
| |||