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).
-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).
, 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).
-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 
.
and 
is illustrated above (Wolfram
2002, p. 889;
Michel).
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
for 
.
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.