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

Machines with 3 symbols

Machines with 4 symbols

Machines with 5 symbols

Machines with 6 symbols

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=
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)
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

Link to Pascal Michel's home page