TOPICS
Search

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).

BusyBeaverSigma

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).

BusyBeaverS

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.

BusyBeaver5Rules

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

References

Barwise, J. and Etchemendy, J. "Turing Machines." http://www-csli.stanford.edu/hp/Turing1.html.Brady, 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')." http://www.cs.unr.edu/~al/BusyBeaver.html.Brady, A. H. "Is This A New Busy Beaver Lower Limit For S(3,3)?" http://www.cs.unr.edu/~al/s3x3-new-value.html.Chaitin, 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. https://cp4space.hatsya.com/2022/06/23/tetrational-machines/.Green, 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. https://www.sligocki.com//2022/06/21/bb-6-2-t15.html.Lin, 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. http://www.eecs.umich.edu/~qstout/abs/busyb.html.Marxen, H. "Busy Beaver." http://www.drb.insel.de/~heiner/BB/.Marxen, H. and Buntrock, J. "Attacking the Busy Beaver 5." Bull. EATCS 40, 247-251, Feb. 1990.Michel, P. "The Busy Beaver Competitions." Feb. 2005. http://www.logique.jussieu.fr/~michel/bbc.html.Michel, P. "Historical Survey of Busy Beavers." https://webusers.imj-prg.fr/~pascal.michel/ha.html#tm62.Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.Shallit, J. "The Busy Beaver Problem." Winter 1998. http://grail.cba.csuohio.edu/~somos/beaver.ps.Sloane, N. J. A. Sequences A028444 and A060843 in "The On-Line Encyclopedia of Integer Sequences."Somos, M. "Busy Beaver Turing Machine." http://grail.cba.csuohio.edu/~somos/bb.html.Wolfram, 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. https://mathworld.wolfram.com/BusyBeaver.html

Subject classifications