A028444 - OEIS

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.

From Daniel Forgues, Jun 05-06 2011: (Start)

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)

From Jianing Song, Nov 12 2023: (Start)

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

Table of n, a(n) for n=0..4.

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.

J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 81 (1974), 724-738.

S. Ligocki, BB(6, 2) > 10↑↑15, 2022.

H. Marxen, Busy Beaver

H. Marxen and J. Buntrock, Attacking the Busy Beaver 5, Bulletin of the EATCS, 40, pages 247-251, 1990.

Math Stack Exchange, What does it mean to say BB(7918) is not computable from ZFC?

Pascal Michel, Historical survey of Busy Beavers, 2011.

Pascal Michel, Behavior of busy beavers, 2010.

Pascal Michel, The Busy Beaver Competitions, 2010.

Pascal Michel, The Busy Beaver Competition: a historical survey, arXiv:0906.3749 [math.LO], 2009-2017.

Tibor Rado, On Noncomputable Functions, Bell System Technical Journal, vol. 41, # 3, 877-884, May 1963.

Michael Somos, Busy Beaver Turing Machine.

Michael Somos, Busy Beaver.