%I #96 Aug 22 2024 07:59:55
%S 0,1,4,6,13
%N 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.
%C 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.
%C 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).
%C 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).
%C 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.
%C Rado's Sigma function grows faster than any computable function and is thus noncomputable.
%C From _Daniel Forgues_, Jun 05-06 2011: (Start)
%C H in H_(n, k) is a halting* Turing machine with n states and k symbols;
%C * (on a blank tape (all 0's) as input)
%C States q, q+ in set Q_n of n distinct states (plus the Halt state);
%C Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol);
%C Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here);
%C sigma(H) is the number of non-blank symbols left on the tape by H;
%C s(H) is the number of steps (or shifts in our case) taken by H;
%C Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}
%C S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}
%C a(n) is Sigma(n) = Sigma(n, 2) since a 2-symbol BB-class Turing machine is assumed.
%C For all n, S(n, k) >= Sigma(n, k), k >= 2. (End)
%C From _Jianing Song_, Nov 12 2023: (Start)
%C 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).
%C 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)
%D John Hopcroft, Turing Machines, Sci. Amer. vol. 250, #5, 86-98, May 1984, table on page 92 gives old lower bounds.
%D Shallit, Jeffrey. A second course in formal languages and automata theory. Cambridge University Press, 2008. See Fig. 6.2, p. 185.
%H Bob Boonstra, <a href="http://preserve.mactech.com/articles/mactech/Vol.16/16.09/Sep00Challenge/index.html">Busy Beavers</a>, 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.
%H J. P. Jones, <a href="https://www.jstor.org/stable/2319560">Recursive undecidability - an exposition</a>, Amer. Math. Monthly, 81 (1974), 724-738.
%H S. Ligocki, <a href="https://www.sligocki.com/2022/06/21/bb-6-2-t15.html">BB(6, 2) > 10↑↑15</a>, 2022.
%H H. Marxen, <a href="http://turbotm.de/~heiner/BB/">Busy Beaver</a>
%H H. Marxen and J. Buntrock, <a href="https://pdfs.semanticscholar.org/6fa1/3c10697ee4f2815089f0c5f71bab7caf650a.pdf">Attacking the Busy Beaver 5</a>, Bulletin of the EATCS, 40, pages 247-251, 1990.
%H Math Stack Exchange, <a href="https://math.stackexchange.com/q/3854667">What does it mean to say BB(7918) is not computable from ZFC?</a>
%H Pascal Michel, <a href="https://bbchallenge.org/~pascal.michel/ha.html">Historical survey of Busy Beavers</a>, 2011.
%H Pascal Michel, <a href="https://bbchallenge.org/~pascal.michel/beh.html">Behavior of busy beavers</a>, 2010.
%H Pascal Michel, <a href="https://bbchallenge.org/~pascal.michel/bbc.html">The Busy Beaver Competitions</a>, 2010.
%H Pascal Michel, <a href="http://arxiv.org/abs/0906.3749">The Busy Beaver Competition: a historical survey</a>, arXiv:0906.3749 [math.LO], 2009-2017.
%H Tibor Rado, <a href="https://archive.org/details/bstj41-3-877">On Noncomputable Functions</a>, Bell System Technical Journal, vol. 41, # 3, 877-884, May 1963.
%H Michael Somos, <a href="https://grail.eecs.csuohio.edu/~somos/bb.html">Busy Beaver Turing Machine</a>.
%H Michael Somos, <a href="https://grail.eecs.csuohio.edu/~somos/busy.html">Busy Beaver</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BusyBeaver.html">Busy Beaver</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Busy_beaver">Busy beaver</a>
%H <a href="/index/Br#beaver">Index entries for sequences related to Busy Beaver problem</a>
%Y Cf. A004147, A052200, A060843.
%K nonn,hard,nice
%O 0,3
%A Scott Aaronson (sja8(AT)cornell.edu)
%E The next two terms are at least 4098 and 10^^15.
%E Edited by _Daniel Forgues_, Mar 25 2010, Jun 05 2011
%E Edited by _N. J. A. Sloane_, Aug 30 2011