Busy Beaver
A busy beaver is an 
-state, 2-color Turing
machine which writes a maximum number 
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 
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 
, 2, ..., 
(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 
and 
(Marxen). The illustration above shows a 3-state Turing machine with maximal 
(Lin and Rado 1965, Shallit 1998).
The maximum number of steps which an 
-state 2-color Turing
machine (not necessarily the same Turing machine producing a maximum number
of 1s) can perform before halting 
has the first
few terms 1, 6, 21, 107, ... (OEIS A060843;
Wolfram 2002, p. 889).
Turing machines giving maximal 
for 
, 3, and 4 are
illustrated above. Again, the next few terms of 
are not known,
but explicit constructions give lower bounds of 
and 
(Marxen).
A set of 5-state rules discovered by Marxen and Buntrock (1990) that gives the largest known values 
and 
is
illustrated above (Wolfram 2002, p. 889).
In 2004, Brady explored 3-state, 3-color Turing machines and found a lower limit of 
for 
.
A table of best known results is maintained by Michel (2008).
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 
for the Value 
." IEEE
Trans. Elec. Comput. EC-15, 802-803, 1966.
Brady, A. H. "The Determination of the Value of Rado's Noncomputable Function 
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 
?" 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.
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.
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.
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.
Weisstein, Eric W. "Busy Beaver." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BusyBeaver.html
Contact the MathWorld Team
(2*3 + 3*4 + 4*5) / (10 - 5)
