The Busy Beaver Competitions
with: Current Records, Winning Turing Machines, References
Created by Pascal Michel in 2004
Last update: September 2024
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), bbchallenge (2024)
-
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),
Shawn Ligocki and "Iijil" (2023)
-
S(2,4) = 3,932,964
-
Sigma(2,4) = 2,050
-
3 states : Pavel Kropitz (2024)
-
S(3,4) > 2(^15)5 + 14
-
Sigma(3,4) =? 2(^15)5 + 14
-
4 states :
-
S(4,4) = ?
-
Sigma(4,4) = ?
Machines with 5 symbols
-
2 states : Daniel Yuan (2024)
-
S(2,5) > 1010103,314,360
-
Sigma(2,5) > 1010103,314,360
-
3 states :
-
S(3,5) = ?
-
Sigma(3,5) = ?
Machines with 6 symbols
-
2 states : Pavel Kropitz (2023)
-
S(2,6) > 10^^(10^^1010115)
-
Sigma(2,6) > 10^^(10^^1010115)
Summary tables
For S(k,n):
6 symbols |
> 10^^(10^^1010115) |
|
|
|
|
5 symbols |
> 10^(10^(10^3,314,360)) |
? |
|
|
|
4 symbols |
3,932,964 |
> 2(^15)5 + 14 |
? |
|
|
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 |
> 10^^(10^^1010115) |
|
|
|
|
5 symbols |
> 10^(10^(10^3,314,360)) |
? |
|
|
|
4 symbols |
2,050 |
2(^15)5 + 14 ? |
? |
|
|
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=
|
|
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) |
bbchallenge (2024) |
s(M) = s(5,2) = 47,176,870 |
sigma(M) = Sigma(5,2) = 4098 |
|
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) |
Shawn Ligocki and "Iijil" (2023) |
s(M) = S(2,4) = 3,932,964 |
sigma(M) = Sigma(2,4) = 2,050 |
|
M=
|
|
0 |
1 |
2 |
3 |
A |
1RB |
2LA |
1RA |
1RA |
B |
1LB |
1LA |
3RB |
1RH |
|
Turing machines with 3 states and 4 symbols
Pavel Kropitz (2024) |
s(M) and S(3,4) > 2(^15)5 + 14 |
sigma(M) = 2(^15)5 + 14 =? Sigma(3,4) |
|
M=
|
|
0 |
1 |
2 |
3 |
A |
1RB |
3LB |
1RH |
2RA |
B |
2LC |
3RB |
1LC |
2RA |
C |
3RB |
1LB |
3LC |
2RC |
|
Turing machines with 2 states and 5 symbols
Daniel Yuan (2024) |
s(M) and S(2,5) > 1010103,314,360 |
sigma(M) and Sigma(2,5) > 1010103,314,360
|
|
M=
|
|
0 |
1 |
2 |
3 |
4 |
A |
1RB |
3LA |
4RB |
0RB |
2LA |
B |
1LB |
2LA |
3LA |
1RA |
1RH |
|
|
Turing machines with 2 states and 6 symbols
Pavel Kropitz (2023) |
s(M) and S(2,6) > 10^^(10^^1010115) |
sigma(M) and Sigma(2,6) > 10^^(10^^1010115) |
|
M=
|
|
0 |
1 |
2 |
3 |
4 |
5 |
A |
1RB |
3RB |
5RA |
1LB |
5LA |
2LB |
B |
2LA |
2RA |
4RB |
1RH |
3LB |
2LA |
|
|
References
-
Brady A.H. (1983)
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
-
Rado T. (1962)
On non-computable functions
Bell System Technical Journal 41 (3), May 1962, 877-884
Link to Pascal Michel's home page