Busy Beaver Competitions

The Busy Beaver Competitions

with: Current Records, Winning Turing Machines, References

Created by Pascal Michel in 2004
Last update: September 2023

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) > 10^{10^{10^{10^18705352.841}}}
- Sigma(7,2) > 10^{10^{10^{10^18705352.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 × 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 : Pavel Kropitz (2023)
- S(3,4) > 10^^2048 (a tower of powers of 10 with 2048 occurences of 10)
- Sigma(3,4) > 10^^2048 (a tower of powers of 10 with 2048 occurences of 10)
4 states :
- S(4,4) = ?
- Sigma(4,4) = ?

Machines with 5 symbols

2 states : Pavel Kropitz (2023)
- S(2,5) > 6.5 × 10³⁸⁰³³
- Sigma(2,5) > 7.3 × 10¹⁹⁰¹⁶
3 states :
- S(3,5) = ?
- Sigma(3,5) = ?

Machines with 6 symbols

2 states : Pavel Kropitz (2023)
- S(2,6) > 10^^(10^^10^10¹¹⁵)
- Sigma(2,6) > 10^^(10^^10^10¹¹⁵)

Summary tables

For S(k,n):

6 symbols	> 10^^(10^^10^10¹¹⁵)
5 symbols	> 6.5 × 10³⁸⁰³³	?
4 symbols	3,932,964 ?	> 10^^2048	?
3 symbols	38	> 1.1 × 10¹⁷	> 1.0 × 10¹⁴⁰⁷²	?
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^^10^10¹¹⁵)
5 symbols	> 7.3 × 10¹⁹⁰¹⁶	?
4 symbols	2,050 ?	> 10^^2048	?
3 symbols	9	374,676,383 ?	> 1.3 × 10⁷⁰³⁶	?
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

	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 (2022)

s(M) and S(6,2) > 10^^15

sigma(M) and Sigma(6,2) > 10^^15

	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) > 10^{10^{10^{10^18705352.841}}}

sigma(M) and Sigma(7,2) > 10^{10^{10^{10^18705352.841}}}

	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

	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

Pavel Kropitz (2023)

s(M) and S(3,4) > 10^^2048

sigma(M) and Sigma(3,4) > 10^^2048

	0	1	2	3
A	1RB	0LB	1RH	3LA
B	0LC	3RB	3RC	1LB
C	2RB	2LA	3RA	1LC

Turing machines with 2 states and 5 symbols

Pavel Kropitz (2023)

s(M) and S(2,5) > 6.5 × 10³⁸⁰³³

sigma(M) and Sigma(2,5) > 7.3 × 10¹⁹⁰¹⁶

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

Turing machines with 2 states and 6 symbols

Pavel Kropitz (2023)

s(M) and S(2,6) > 10^^(10^^10^10¹¹⁵)

sigma(M) and Sigma(2,6) > 10^^(10^^10^10¹¹⁵)

	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