.png)
4 months ago
4
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 a lower bound 
.
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;
Michel).
In May 2022, Pavel Kropitz constructed a 6-state 2-symbol Turing machine which takes approximately
(or 
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
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 
for 
.
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 
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.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. "
."
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
Cite this as:
Weisstein, Eric W. "Busy Beaver." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BusyBeaver.html
