The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 10
0, 1, 4, 6, 13 (list; graph; refs; listen; history; text; internal format)



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)


Bob Boonstra, Programmer's Challenge, MacTech Journal, Volume Number: 16 (2000), Issue Number: 9; [http://preserve.mactech.com/articles/mactech/Vol.16/16.09/Sep00Challenge/index.html] reports that in December 1984 George Uhing found a 5-state machine that produced 1915 1's before halting.

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.


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

Daniel Forgues, Busy Beaver numbers

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

H. Marxen, Busy Beaver

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

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.

M. Somos, Busy Beaver Turing Machine

M. Somos, Busy Beaver

Eric Weisstein's World of Mathematics, Busy Beaver

Index entries for sequences related to Busy Beaver problem


Cf. A004147, A052200, A060843.

Sequence in context: A133454 A061072 A130435 * A003973 A034747 A168015

Adjacent sequences:  A028441 A028442 A028443 * A028445 A028446 A028447




Scott Aaronson (sja8(AT)cornell.edu)


The next two terms are at least 4098 and 1.29*10^865.

Edited by Daniel Forgues, Mar 25 2010, Jun 05 2011

Edited by N. J. A. Sloane, Aug 30 2011



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 21:35 EDT 2020. Contains 337322 sequences. (Running on oeis4.)