The Busy Beaver Competitions

with: Current Records, Winning Turing Machines, References

Last update: May 2022

If you do not understand the following definitions,
you need elementary stuff on Turing machines and Busy Beavers.

Definitions

S(k,n) is the maximum number of steps made by a Turing machine with k states and n symbols that stops when starting from a blank tape.

Sigma(k,n) is the maximum number of non-blank symbols left on the tape by such a machine.

Records for the Busy Beaver Competitions

Only the current records are given here.
The previous records are given in the historical survey of the busy beaver competition.

Machines with 2 symbols
• 2 states : Rado (1962)
• S(2,2) = 6
• Sigma(2,2) = 4
• 3 states : Lin and Rado (1965)
• S(3,2) = 21
• Sigma(3,2) = 6
• 4 states : Brady (1983) and Kopp (cited by Machlin and Stout (1990))
• S(4,2) = 107
• Sigma(4,2) = 13
• 5 states : Marxen and Buntrock (1990)
• S(5,2) =? 47,176,870
• Sigma(5,2) =? 4098
• 6 states : Kropitz (2022)
• S(6,2) > 10^^15 (a tower of powers of 10 with 15 occurences of 10)
• Sigma(6,2) > 10^^15 (a tower of powers of 10 with 15 occurences of 10)
• 7 states : "Wythagoras" (2014). Superseded by the (6,2) champion.
• S(7,2) > 1010101018705352.841
• Sigma(7,2) > 1010101018705352.841

Machines with 3 symbols
• 2 states : Lafitte and Papazian (2007)
• S(2,3) = 38
• Sigma(2,3) = 9
• 3 states : Terry and Shawn Ligocki (2007)
• S(3,3) =? 119,112,334,170,342,540
• Sigma(3,3) =? 374,676,383
• 4 states : Terry and Shawn Ligocki (2008)
• S(4,3) > 1.0 × 1014072
• Sigma(4,3) > 1.3 × 107036
• 5 states :
• S(5,3) = ?
• Sigma(5,3) = ?

Machines with 4 symbols
• 2 states : Terry and Shawn Ligocki (2005)
• S(2,4) =? 3,932,964
• Sigma(2,4) =? 2,050
• 3 states : Terry and Shawn Ligocki (2007)
• S(3,4) > 5.2 × 1013036
• Sigma(3,4) > 3.7 × 106518
• 4 states :
• S(4,4) = ?
• Sigma(4,4) = ?

Machines with 5 symbols
• 2 states : Terry and Shawn Ligocki (2007)
• S(2,5) > 1.9 × 10704
• Sigma(2,5) > 1.7 × 10352
• 3 states :
• S(3,5) = ?
• Sigma(3,5) = ?

Machines with 6 symbols
• 2 states : Terry and Shawn Ligocki (2008)
• S(2,6) > 2.4 × 109866
• Sigma(2,6) > 1.9 × 104933

Summary tables

For S(k,n):

 6 symbols > 2.4 × 109866 5 symbols > 1.9 × 10704 ? 4 symbols 3,932,964 ? > 5.2 × 1013036 ? 3 symbols 38 > 1.1 × 1017 > 1.0 × 1014072 ? 2 symbols 6 21 107 47,176,870 ? > 10^^15 2 states 3 states 4 states 5 states 6 states

For Sigma(k,n):

 6 symbols > 1.9 × 104933 5 symbols > 1.7 × 10352 ? 4 symbols 2,050 ? > 3.7 × 106518 ? 3 symbols 9 374,676,383 ? > 1.3 × 107036 ? 2 symbols 4 6 13 4098 ? > 10^^15 2 states 3 states 4 states 5 states 6 states

Winning machines

Other good machines are given in the historical survey.

Turing machines with 2 states and 2 symbols
 Rado (1962) s(M) = S(2,2) = 6 sigma(M) = Sigma(2,2) = 4
M=
 0 1 A 1RB 1LB B 1LA 1RH

Turing machines with 3 states and 2 symbols
 Lin and Rado (1965) s(M) = S(3,2) = 21 sigma(M) = 5
M=
 0 1 A 1RB 1RH B 1LB 0RC C 1LC 1LA
 Lin and Rado (1965) s(M) = 14 sigma(M) = Sigma(3,2) = 6
M=
 0 1 A 1RB 1RH B 0RC 1RB C 1LC 1LA

Turing machines with 4 states and 2 symbols
 Brady (1983) s(M) = S(4,2) = 107 sigma(M) = Sigma(4,2) = 13
M=
 0 1 A 1RB 1LB B 1LA 0LC C 1RH 1LD D 1RD 0RA

Turing machines with 5 states and 2 symbols
 Marxen and Buntrock (1990) s(M) = 47,176,870 =? S(5,2) sigma(M) = 4098 =? Sigma(5,2)
M=
 0 1 A 1RB 1LC B 1RC 1RB C 1RD 0LE D 1LA 1LD E 1RH 0LA

Turing machines with 6 states and 2 symbols
 Kropitz (2022) s(M) and S(6,2) > 10^^15 sigma(M) and Sigma(6,2) > 10^^15
M=
 0 1 A 1RB 0LD B 1RC 0RF C 1LC 1LA D 0LE 1RH E 1LF 0RB F 0RC 0RE

Turing machines with 7 states and 2 symbols
 "Wythagoras" (2014) Superseded by the (6,2) champion s(M) and S(7,2) > 1010101018705352.841 sigma(M) and Sigma(7,2) > 1010101018705352.841
M=
 0 1 A 1RB B 1RC 0LG C 1LD 1RB D 1LF 1LE E 1RH 1LF F 1RG 0LD G 1LB 0RF

Turing machines with 2 states and 3 symbols
 Lafitte and Papazian (2007) s(M) = S(2,3) = 38 sigma(M) = Sigma(2,3) = 9
M=
 0 1 2 A 1RB 2LB 1RH B 2LA 2RB 1LB

Turing machines with 3 states and 3 symbols
 Terry and Shawn Ligocki (2007) s(M) = 119,112,334,170,342,540 =? S(3,3) sigma(M) = 374,676,383 =? Sigma(3,3)
M=
 0 1 2 A 1RB 2LA 1LC B 0LA 2RB 1LB C 1RH 1RA 1RC

Turing machines with 4 states and 3 symbols
 Terry and Shawn Ligocki (2008) s(M) and S(4,3) > 1.0 × 1014072 sigma(M) and Sigma(4,3) > 1.3 × 107036
M=
 0 1 2 A 1RB 1RH 2RC B 2LC 2RD 0LC C 1RA 2RB 0LB D 1LB 0LD 2RC

Turing machines with 2 states and 4 symbols
 Terry and Shawn Ligocki (2005) s(M) = 3,932,964 =? S(2,4) sigma(M) = 2,050 =? Sigma(2,4)
M=
 0 1 2 3 A 1RB 2LA 1RA 1RA B 1LB 1LA 3RB 1RH

Turing machines with 3 states and 4 symbols
 Terry and Shawn Ligocki (2007) s(M) and S(3,4) > 5.2 × 1013036 sigma(M) and Sigma(3,4) > 3.7 × 106518
M=
 0 1 2 3 A 1RB 1RA 2LB 3LA B 2LA 0LB 1LC 1LB C 3RB 3RC 1RH 1LC

Turing machines with 2 states and 5 symbols
 Terry and Shawn Ligocki (2007) s(M) and S(2,5) > 1.9 × 10704 sigma(M) and Sigma(2,5) > 1.7 × 10352
M=
 0 1 2 3 4 A 1RB 2LA 1RA 2LB 2LA B 0LA 2RB 3RB 4RA 1RH

Turing machines with 2 states and 6 symbols
 Terry and Shawn Ligocki (2008) s(M) and S(2,6) > 2.4 × 109866 sigma(M) and Sigma(2,6) > 1.9 × 104933
M=
 0 1 2 3 4 5 A 1RB 2LA 1RH 5LB 5LA 4LB B 1LA 4RB 3RB 5LB 1LB 4RA

References

The determination of the value of Rado's noncomputable function Sigma(k) for four-state Turing machines
Mathematics of Computation 40 (162), April 1983, 647-665

• Lafitte G. and Papazian C. (2007)
The fabric of small Turing machines
in: Computation and Logic in the Real World, Proceedings of the Third Conference on Computability in Europe, June 2007, 219-227.

• Lin S. and Rado T. (1965)
Computer studies of Turing machine problems
Journal of the ACM 12 (2), April 1965, 196-212

• Machlin R. and Stout Q.F. (1990)
The complex behavior of simple machines
Physica D 42 , June 1990, 85-98

• Marxen H. and Buntrock J. (1990)
Attacking the Busy Beaver 5
Bulletin of the EATCS No 40, February 1990, 247-251