Busy Beaver

A busy beaver is an n-state, 2-color Turing machine which writes a maximum number Sigma(n) of 1s before halting (Rado 1962; Lin and Rado 1965; Shallit 1998). Alternatively, some authors define a busy beaver as a Turing machine that performs a maximum number S(n) of steps when started on an initially blank tape before halting (Wolfram 2002, p. 889). The process leading to the solution of the three-state machine is discussed by Lin and Rado (1965) and the process leading to the solution of the four-state machine is discussed by Brady (1983) and Machlin and Stout (1990).


For n=1, 2, ..., Sigma(n) (also known as Rado's sigma function) is given by 1, 4, 6, 13, ... (OEIS A028444; Rado 1962; Wolfram 2002, p. 889). The next few terms are not known, but examples have been constructed giving lower limits of Sigma(5)>=4098 and Sigma(6)>=1.29×10^(865) (Marxen). The illustration above shows a 3-state Turing machine with maximal Sigma(3)=6 (Lin and Rado 1965, Shallit 1998).


The maximum number of steps which an n-state 2-color Turing machine (not necessarily the same Turing machine producing a maximum number of 1s) can perform before halting S(n) has the first few terms 1, 6, 21, 107, ... (OEIS A060843; Wolfram 2002, p. 889). Turing machines giving maximal S(n) for n=2, 3, and 4 are illustrated above. Again, the next few terms of S(n) are not known, but explicit constructions give a lower bound S(5)>=47176870.


A set of 5-state rules discovered by Marxen and Buntrock (1990) that gives the largest known values Sigma(5)=4098 and S(5)=47176870 is illustrated above (Wolfram 2002, p. 889; Michel).

In May 2022, Pavel Kropitz constructed a 6-state 2-symbol Turing machine which takes approximately

 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 4.023873729

(or >10^^15 in Knuth up-arrow notation; Ligocki 2022) timesteps to halt (where exponentiation is right-associative, so the rightmost exponentiation is applied first) and has writen

 (3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ (4)+7)/8)+21)/8)+7)/8)+23)/8)+7)/8)+21)/8)+7)/8)+23)/8)+7)/8)+23)/8)+7)/8)+21)/8)+7)/8)+23)/8)+13)/8)-11)/2

1s when the machine halts (Goucher 2022, Ligocki 2022).

In 2004, Brady explored 3-state, 3-color Turing machines and found a lower limit of 92649163 for S(3,3).

A table of best known results is maintained by Michel (2008).

See also

Halting Problem, Turing Machine

Explore with Wolfram|Alpha


Barwise, J. and Etchemendy, J. "Turing Machines.", A. H. "The Conjectured Highest Scoring Machines for Rado's Sigma(k) for the Value k=4." IEEE Trans. Elec. Comput. EC-15, 802-803, 1966.Brady, A. H. "The Determination of the Value of Rado's Noncomputable Function Sigma(k) for Four-State Turing Machines." Math. Comput. 40, 647-665, 1983.Brady, A. H. "Busy Beaver Problem of Tibor Rado ('Busy Beaver Game').", A. H. "Is This A New Busy Beaver Lower Limit For S(3,3)?", G. J. "Computing the Busy Beaver Function." §4.4 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 108-112, 1987.Dewdney, A. K. "Computer Recreations: A Computer Trap for the Busy Beaver, the Hardest-Working Turing Machine." Sci. Amer. 251, 19-23, Aug. 1984.Dewdney, A. K. "Computer Recreations." Sci. Amer. 252, 12-16, Apr. 1985.Goucher, A. "Tetrational Machines." Jun. 23, 2022., M. W. "A Lower Bound on Rado's Sigma Function for Binary Turing Machines." Switching Circuit Theory and Logical Design, Proceedings of the Fifth Annual Symposium, Princeton University, Princeton, NJ, November 11-13, 1964. New York: IEEE, pp. 91-94, 1964.Herken, R. The Universal Turing Machine: A Half-Century Survey. Oxford, England: Oxford University Press, 1988.Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, 1964.Ligocki, S. "BB(6,2)>10^^15." Jun. 21, 2022., S. and Rado, T. "Computer Studies of Turing Machine Problems." J. ACM 12, 196-212, 1965.Machlin, R. and Stout, Q. F. "The Complex Behavior of Simple Machines." Physica 42D, 85-98, 1990., H. "Busy Beaver.", H. and Buntrock, J. "Attacking the Busy Beaver 5." Bull. EATCS 40, 247-251, Feb. 1990.Michel, P. "The Busy Beaver Competitions." Feb. 2005., P. "Historical Survey of Busy Beavers.", T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.Shallit, J. "The Busy Beaver Problem." Winter 1998., N. J. A. Sequences A028444 and A060843 in "The On-Line Encyclopedia of Integer Sequences."Somos, M. "Busy Beaver Turing Machine.", S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 889 and 1144, 2002.

Referenced on Wolfram|Alpha

Busy Beaver

Cite this as:

Weisstein, Eric W. "Busy Beaver." From MathWorld--A Wolfram Web Resource.

Subject classifications