The Busy Beaver Competitions

with: Current Records, Winning Turing Machines, References

Last update: July 2010

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 > 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 ? > 7.4 × 1036534
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 ?   > 3.5 × 1018267
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 (2010)
s(M) and S(6,2) > 7.4 × 1036534
sigma(M) and Sigma(6,2) > 3.5 × 1018267
M=
0 1
A 1RB 1LE
B 1RC 1RF
C 1LD 0RB
D 1RE 0LC
E 1LA 0RD
F 1RH 1RC

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

Link to Pascal Michel's home page