Busy Beaver Competitions

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

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 (2010)
- S(6,2) > 7.4 × 10³⁶⁵³⁴
- Sigma(6,2) > 3.5 × 10¹⁸²⁶⁷

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 × 10¹⁴⁰⁷²
- Sigma(4,3) > 1.3 × 10⁷⁰³⁶
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 × 10¹³⁰³⁶
- Sigma(3,4) > 3.7 × 10⁶⁵¹⁸
4 states :
- S(4,4) = ?
- Sigma(4,4) = ?

Machines with 5 symbols

2 states : Terry and Shawn Ligocki (2007)
- S(2,5) > 1.9 × 10⁷⁰⁴
- Sigma(2,5) > 1.7 × 10³⁵²
3 states :
- S(3,5) = ?
- Sigma(3,5) = ?

Machines with 6 symbols

2 states : Terry and Shawn Ligocki (2008)
- S(2,6) > 2.4 × 10⁹⁸⁶⁶
- Sigma(2,6) > 1.9 × 10⁴⁹³³

Summary tables

For S(k,n):

6 symbols	> 2.4 × 10⁹⁸⁶⁶
5 symbols	> 1.9 × 10⁷⁰⁴	?
4 symbols	3,932,964 ?	> 5.2 × 10¹³⁰³⁶	?
3 symbols	38	> 1.1 × 10¹⁷	> 1.0 × 10¹⁴⁰⁷²	?
2 symbols	6	21	107	47,176,870 ?	> 7.4 × 10³⁶⁵³⁴
	2 states	3 states	4 states	5 states	6 states

For Sigma(k,n):

6 symbols	> 1.9 × 10⁴⁹³³
5 symbols	> 1.7 × 10³⁵²	?
4 symbols	2,050 ?	> 3.7 × 10⁶⁵¹⁸	?
3 symbols	9	374,676,383 ?	> 1.3 × 10⁷⁰³⁶	?
2 symbols	4	6	13	4098 ?	> 3.5 × 10¹⁸²⁶⁷
	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

	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

	0	1
A	1RB	1RH
B	1LB	0RC
C	1LC	1LA

Lin and Rado (1965)

s(M) = 14

sigma(M) = Sigma(3,2) = 6

	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

	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)

	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 × 10³⁶⁵³⁴

sigma(M) and Sigma(6,2) > 3.5 × 10¹⁸²⁶⁷

	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

	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)

	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 × 10¹⁴⁰⁷²

sigma(M) and Sigma(4,3) > 1.3 × 10⁷⁰³⁶

	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)

	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 × 10¹³⁰³⁶

sigma(M) and Sigma(3,4) > 3.7 × 10⁶⁵¹⁸

	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 × 10⁷⁰⁴

sigma(M) and Sigma(2,5) > 1.7 × 10³⁵²

	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 × 10⁹⁸⁶⁶

sigma(M) and Sigma(2,6) > 1.9 × 10⁴⁹³³

	0	1	2	3	4	5
A	1RB	2LA	1RH	5LB	5LA	4LB
B	1LA	4RB	3RB	5LB	1LB	4RA

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