A busy beaver is an -state,
2-symbol Turing machine that leaves the maximum
number
of 1s on an initially all-zero tape when it halts (Rado 1962, Lin and Rado 1965,
Shallit 1998). Alternatively, some authors define a busy beaver as a Turing
machine that performs the maximum number of steps before halting from the same initial tape (Wolfram
2002, p. 889). Here
is a positive integer counting the nonhalting
states, the tape is infinite in both directions, and each transition writes 0 or
1 and moves one cell left or right. The final transition into a separate halting
state counts as a step.
The process leading to the solution of the three-state problem is discussed by Lin and Rado (1965), and the process leading to the solution of the four-state problem 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, 4098, ... (OEIS A028444; Rado 1962;
Wolfram 2002, p. 889).
The equality
is proved by The bbchallenge Collaboration et al. (2026, p. 37). An earlier
construction gives the lower bound (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-symbol Turing machine
(not necessarily the sameTuring machine
producing a maximum number of 1s) can perform before halting is . Its first few terms are 1, 6, 21, 107, 47176870, ... (OEIS
A060843; Wolfram 2002, p. 889).
Turing machines giving maximal for , 3, and 4 are illustrated above. The equality is proved using the Coq proof assistant (The bbchallenge
Collaboration et al. 2026, p. 2).
A set of 5-state rules found by Marxen and Buntrock (1990) that attains both proved maxima
and is illustrated above (Wolfram
2002, p. 889;
The bbchallenge Collaboration et al. 2026, pp. 9, 37).
Pavel Kropitz constructed a 6-state, 2-symbol Turing
machine in May 2022 (Ligocki 2022). Goucher (2022) reports that it takes approximately
timesteps to halt, and Ligocki (2022) proves that it takes more than steps in Knuth
up-arrow notation. In the preceding display, exponentiation
is right-associative, so the rightmost exponentiation
is applied first. The machine leaves
1s when the machine halts (Goucher 2022, Ligocki 2022).
Brady found a 3-state, 3-symbol Turing machine in December 2004 giving the lower bound for (Michel 2022). Here is the analogous maximum step count for nonhalting states and tape symbols, one of which is the initial blank symbol.
Historical results and analyses of the machines are collected by Michel (2022).
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. ACM12,
196-212, 1965.Machlin, R. and Stout, Q. F. "The Complex Behavior
of Simple Machines." Physica42D, 85-98, 1990. https://web.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. EATCS40,
247-251, Feb. 1990.Michel, P. "The Busy Beaver Competition: A Historical
Survey." 14 Dec 2022. https://arxiv.org/abs/0906.3749v7.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." https://grail.cba.csuohio.edu/~somos/bb.html.The
bbchallenge Collaboration; Blanchard, J.; Briggs, D.; Deka, K.; Fenner, N.; Forster,
Y.; Georgiev, G.; House, M. L.; Hunter, R.; Iijil; Kądziołka, M.;
Kropitz, P.; Ligocki, S.; mxdys; Naściszewski, M.; savask; Stérin, T.;
Xu, C.; Yuen, J.; and Zimmermann, T. "Determination of the Fifth Busy Beaver
Value." 23 Mar 2026. https://arxiv.org/abs/2509.12337v2.Wolfram,
S. A
New Kind of Science. Champaign, IL: Wolfram Media, pp. 889
and 1144,
2002.
-state,
2-symbol Turing machine that leaves the maximum
number 
of 1s on an initially all-zero tape when it halts (Rado 1962, Lin and Rado 1965,
Shallit 1998). Alternatively, some authors define a busy beaver as a Turing
machine that performs the maximum number 
of steps before halting from the same initial tape (Wolfram
2002, p. 889). Here 
is a positive integer counting the nonhalting
states, the tape is infinite in both directions, and each transition writes 0 or
1 and moves one cell left or right. The final transition into a separate halting
state counts as a step.
, 2, ..., 
(also known as Rado's sigma function) is given by 1,
4, 6, 13, 4098, ... (OEIS A028444; Rado 1962;
Wolfram 2002, p. 889).
The equality 
is proved by The bbchallenge Collaboration et al. (2026, p. 37). An earlier
construction gives the lower bound 
(Marxen). The illustration above
shows a 3-state Turing machine with maximal 
(Lin and Rado 1965, Shallit
1998).
-state 2-symbol Turing machine
(not necessarily the same Turing machine
producing a maximum number of 1s) can perform before halting is 
. Its first few terms are 1, 6, 21, 107, 47176870, ... (OEIS
A060843; Wolfram 2002, p. 889).
Turing machines giving maximal 
for 
, 3, and 4 are illustrated above. The equality 
is proved using the Coq proof assistant (The bbchallenge
Collaboration et al. 2026, p. 2).
and 
is illustrated above (Wolfram
2002, p. 889;
The bbchallenge Collaboration et al. 2026, pp. 9, 37).
steps in Knuth
up-arrow notation. In the preceding display, exponentiation
is right-associative, so the rightmost exponentiation
is applied first. The machine leaves
for 
(Michel 2022). Here 
is the analogous maximum step count for 
nonhalting states and 
tape symbols, one of which is the initial blank symbol.
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')." 
?" 
."
Jun. 21, 2022.