|
| |
|
|
A028444
|
|
Busy Beaver sequence, or Rado's sigma function: maximal number of 1's that an n-state Turing machine can print on an initially blank tape before halting.
|
|
13
|
| |
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Expanded definition from Daniel Forgues: Busy Beaver sequence, or Rado's Sigma function: maximum number of 1s that an n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) halting Turing machine can print on an initially blank tape (all 0's) before halting.
States q and q+ in set Q_n of n distinct states (plus the Halt state), tape symbols s and s+ in set S = {0, 1}, shift direction d+ in {LEFT, RIGHT} (NONE is excluded here), + suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).
The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1's) which a halting Turing Machine H with n internal states, 2 symbols, and a two-way infinite tape can produce onto an initially blank tape (all 0's) and then halt. The function S(n) = S(n, 2) (A060843) denotes the maximal number of steps (thus shifts, since direction NONE is excluded) which a halting machine H can take (not necessarily the same Turing machine producing a maximum number of 1's and need not even produce many tape marks). For all n, S(n) >= Sigma(n).
Given that 5-state 2-symbol halting Turing machines can compute Collatz-like congruential functions (see references under A060843), it may be very hard to find the next term.
Rado's Sigma function grows faster than any computable function and is thus noncomputable.
H in H_(n, k) is a halting* Turing machine with n states and k symbols;
* (on a blank tape (all 0's) as input)
States q, q+ in set Q_n of n distinct states (plus the Halt state);
Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol);
Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here);
sigma(H) is the number of non-blank symbols left on the tape by H;
s(H) is the number of steps (or shifts in our case) taken by H;
Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}
S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}
a(n) is Sigma(n) = Sigma(n, 2) since a 2-symbol BB-class Turing machine is assumed.
For all n, S(n, k) >= Sigma(n, k), k >= 2. (End)
We have a(2*n) > H_n(3,3) = 3 "up-arrow"(n-2) 3, where H_n is the n-th hyperoperator, and "up-arrow" is Knuth up-arrow notation (see the Wikipedia link). This means that a(12) > 3^^^^3 = g(1), where g(1) is the starting value in the sequence that defines Graham's number = g(64).
Note that there is an (n_0)-state binary Turing machine (and hence an n-state one for every n >= n_0) which halts if and only if ZFC is inconsistent, so a(n_0) (and hence a(n) for every n >= n_0) is independent of ZFC, which means that a(n_0) evaluates differently in different models of ZFC; see the section "Non-computability" of the Wikipedia link and the Math Stack Exchange. The minimum such n_0 is not exceeding 745. (End)
|
|
|
REFERENCES
|
John Hopcroft, Turing Machines, Sci. Amer. vol. 250, #5, 86-98, May 1984, table on page 92 gives old lower bounds.
Shallit, Jeffrey. A second course in formal languages and automata theory. Cambridge University Press, 2008. See Fig. 6.2, p. 185.
|
|
|
LINKS
|
Bob Boonstra, Busy Beavers, Programmer's Challenge, MacTech Journal, Volume 16 (2000), Issue 9 - reports that in December 1984 George Uhing found a 5-state machine that produced 1915 1's before halting.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard,nice
|
|
|
AUTHOR
|
Scott Aaronson (sja8(AT)cornell.edu)
|
|
|
EXTENSIONS
|
The next two terms are at least 4098 and 10^^15.
|
|
|
STATUS
|
approved
|
| |
|
|
