Historical survey of Busy Beavers

Contents

Chronological summary

Turing machines with 2 states and 2 symbols
Turing machines with 3 states and 2 symbols
Turing machines with 4 states and 2 symbols
Turing machines with 5 states and 2 symbols
Turing machines with 6 states and 2 symbols

Turing machines with 2 states and 3 symbols
Turing machines with 3 states and 3 symbols
Turing machines with 4 states and 3 symbols

Turing machines with 2 states and 4 symbols
Turing machines with 3 states and 4 symbols

Turing machines with 2 states and 5 symbols
Turing machines with 2 states and 6 symbols

Relations between functions S and Sigma

Variants of busy beavers:
1 - Busy beavers defined by 4-tuples
2 - Busy beavers whose head can stand still
3 - Two-dimensional busy beavers
References
Links to the web

Last update: July 2012

See also an introduction to Turing machines and busy beavers for the definitions,
the current results on the busy beaver competitions,
and some advanced topics.

Chronological summary

1963 Rado, Lin     S(2,2) = 6, Sigma(2,2) = 4
    S(3,2) = 21, Sigma(3,2) = 6
1964 Brady (4,2)-TM: s = 107, sigma = 13
1964 Green (5,2)-TM: sigma = 17
(6,2)-TM: sigma = 35
1972 Lynn (5,2)-TM: s = 435, sigma = 22
(6,2)-TM: s = 522, sigma = 42
1974 Lynn (5,2)-TM: s = 7,707, sigma = 112
1974 Brady     S(4,2) = 107, Sigma(4,2) = 13
1983 Brady (6,2)-TM: s = 13,488, sigma = 117
January 1983 Schult (5,2)-TM: s = 134,467, sigma = 501
(6,2)-TM: sigma = 2,075
December 1984 Uhing (5,2)-TM: s = 2,133,492, sigma = 1,915
February 1986 Uhing (5,2)-TM: s = 2,358,064
1988 Brady (2,3)-TM: s = 38, sigma = 9
(2,4)-TM: s = 7,195, sigma = 90
February 1990 Marxen, Buntrock (5,2)-TM: s = 47,176,870, sigma = 4,098
(6,2)-TM: s = 13,122,572,797, sigma = 136,612
September 1997 Marxen, Buntrock (6,2)-TM: s = 8,690,333,381,690,951, sigma = 95,524,079
August 2000 Marxen, Buntrock (6,2)-TM: s > 5.3 × 10^42, sigma > 2.5 × 10^21
October 2000 Marxen, Buntrock (6,2)-TM: s > 6.1 × 10^925, sigma > 6.4 × 10^462
March 2001 Marxen, Buntrock (6,2)-TM: s > 3.0 × 10^1730, sigma > 1.2 × 10^865
October 2004 Michel (3,3)-TM: s = 40,737, sigma = 208
November 2004 Brady (3,3)-TM: s = 29,403,894, sigma = 5,600
December 2004 Brady (3,3)-TM: s = 92,649,163, sigma = 13,949
February 2005 T. and S. Ligocki (2,4)-TM: s = 3,932,964, sigma = 2,050
(2,5)-TM: s = 16,268,767, sigma = 4,099
(2,6)-TM: s = 98,364,599, sigma = 10,574
April 2005 T. and S. Ligocki (4,3)-TM: s = 250,096,776, sigma = 15,008
(3,4)-TM: s = 262,759,288, sigma = 17,323
(2,5)-TM: s = 148,304,214, sigma = 11,120
(2,6)-TM: s = 493,600,387, sigma = 15,828
July 2005 Souris (3,3)-TM: s = 544,884,219, sigma = 36,089
August 2005 Lafitte, Papazian (3,3)-TM: s = 4,939,345,068, sigma = 107,900
(2,5)-TM: s = 8,619,024,596, sigma = 90,604
September 2005 Lafitte, Papazian (3,3)-TM: s = 987,522,842,126, sigma = 1,525,688
(2,5)-TM: sigma = 97,104
October 2005 Lafitte, Papazian (2,5)-TM: s = 233,431,192,481, sigma = 458,357
(2,5)-TM: s = 912,594,733,606, sigma = 1,957,771
December 2005 Lafitte, Papazian (2,5)-TM: s = 924,180,005,181
April 2006 Lafitte, Papazian (3,3)-TM: s = 4,144,465,135,614, sigma = 2,950,149
May 2006 Lafitte, Papazian (2,5)-TM: s = 3,793,261,759,791, sigma = 2,576,467
June 2006 Lafitte, Papazian (2,5)-TM: s = 14,103,258,269,249, sigma = 4,848,239
July 2006 Lafitte, Papazian (2,5)-TM: s = 26,375,397,569,930
August 2006 T. and S. Ligocki (3,3)-TM: s = 4,345,166,620,336,565, sigma = 95,524,079
(2,5)-TM: s > 7.0 × 10^21, sigma = 172,312,766,455
June 2007 Lafitte, Papazian     S(2,3) = 38, Sigma(2,3) = 9
September 2007 T. and S. Ligocki (3,4)-TM: s > 5.7 × 10^52, sigma > 2.4 × 10^26
(2,6)-TM: s > 2.3 × 10^54, sigma > 1.9 × 10^27
October 2007 T. and S. Ligocki (4,3)-TM: s > 1.5 × 10^1426, sigma > 1.1 × 10^713
(3,4)-TM: s > 4.3 × 10^281, sigma > 6.0 × 10^140
(3,4)-TM: s > 7.6 × 10^868, sigma > 4.6 × 10^434
(3,4)-TM: s > 3.1 × 10^1256, sigma > 2.1 × 10^628
(2,5)-TM: s > 5.2 × 10^61, sigma > 9.3 × 10^30
(2,5)-TM: s > 1.6 × 10^211, sigma > 5.2 × 10^105
November 2007 T. and S. Ligocki (6,2)-TM: s > 8.9 × 10^1762, sigma > 2.5 × 10^881
(3,3)-TM: s = 119,112,334,170,342,540, sigma = 374,676,383
(4,3)-TM: s > 7.7 × 10^1618, sigma > 1.6 × 10^809
(4,3)-TM: s > 3.7 × 10^1973, sigma > 8.0 × 10^986
(4,3)-TM: s > 3.9 × 10^7721, sigma > 4.0 × 10^3860
(4,3)-TM: s > 3.9 × 10^9122, sigma > 2.5 × 10^4561
(3,4)-TM: s > 8.4 × 10^2601, sigma > 1.7 × 10^1301
(3,4)-TM: s > 3.4 × 10^4710, sigma > 1.4 × 10^2355
(3,4)-TM: s > 5.9 × 10^4744, sigma > 2.2 × 10^2372
(2,5)-TM: s > 1.9 × 10^704, sigma > 1.7 × 10^352
(2,6)-TM: s > 4.9 × 10^1643, sigma > 8.6 × 10^821
(2,6)-TM: s > 2.5 × 10^9863, sigma > 6.9 × 10^4931
December 2007 T. and S. Ligocki (6,2)-TM: s > 2.5 × 10^2879, sigma > 4.6 × 10^1439
(4,3)-TM: s > 7.9 × 10^9863, sigma > 8.9 × 10^4931
(4,3)-TM: s > 5.3 × 10^12068, sigma > 4.2 × 10^6034
(3,4)-TM: s > 5.2 × 10^13036, sigma > 3.7 × 10^6518
January 2008 T. and S. Ligocki (4,3)-TM: s > 1.0 × 10^14072, sigma > 1.3 × 10^7036
(2,6)-TM: s > 2.4 × 10^9866, sigma > 1.9 × 10^4933
May 2010 Kropitz (6,2)-TM: s > 3.8 × 10^21132, sigma > 3.1 × 10^10566
June 2010 Kropitz (6,2)-TM: s > 7.4 × 10^36534, sigma > 3.5 × 10^18267

Turing machines with 2 states and 2 symbols

Turing machines with 3 states and 2 symbols

Turing machines with 4 states and 2 symbols

Turing machines with 5 states and 2 symbols

A0 A1 B0 B1 C0 C1 D0 D1 E0 E1 sigma(M) s(M)
1RB 1LC 1RC 1RB 1RD 0LE 1LA 1LD 1RH 0LA 4098 47,176,870
1RB 0LD 1LC 1RD 1LA 1LC 1RH 1RE 1RA 0RB 4097 23,554,764
1RB 1RA 0LC 0RC 1RH 1RD 1LE 0LA 1LA 1LE 4096 11,821,190*
1RB 1RA 1LC 0RD 1LA 1LC 1RH 1RE 1LC 0LA 4096 11,815,076*
1RB 1RA 0LC 0RC 1RH 1RD 1LE 1RB 1LA 1LE 4096 11,811,010*
1RB 1RA 1LC 0RD 1LA 1LC 1RH 1RE 0LE 1RB 4096 11,804,910
1RB 1RA 1LC 0RD 1LA 1LC 1RH 1RE 1LC 1RB 4096 11,804,896
1RB 1RA 1LC 1LB 1RA 1LD 1RA 1LE 1RH 0LC 4098 11,798,826
1RB 1RA 1LC 1RD 1LA 1LC 1RH 0RE 1LC 1RB 4097 11,798,796
1RB 1RA 1LC 1RD 1LA 1LC 1RH 1RE 0LE 0RB 4097 11,792,724*
1RB 1RA 1LC 1RD 1LA 1LC 1RH 1RE 1RA 0RB 4097 11,792,682*
1RB 1RH 1LC 1RC 0RE 0LD 1LC 0LB 1RD 1RA 1471 2,358,064
1RB 1LC 0LA 0LD 1LA 1RH 1LB 1RE 0RD 0RB 1915 2,133,492
1RB 0LC 1RC 1RD 1LA 0RB 0RE 1RH 1LC 1RA 501 134,467

(Among the first eleven machines, the five starred ones are from Norbert Bátfai. The six machines without star were discovered by Marxen and Buntrock, the next two ones were by Uhing, and the last one was by Schult. Heiner Marxen says there are no other sigma values within the sigma range above).

Turing machines with 6 states and 2 symbols

A0 A1 B0 B1 C0 C1 D0 D1 E0 E1 F0 F1 sigma(M)  > s(M)  >
1RB 1LE 1RC 1RF 1LD 0RB 1RE 0LC 1LA 0RD 1RH 1RC 3.5 × 10^18267 7.4 × 10^36534
1RB 0LD 1RC 0RF 1LC 1LA 0LE 1RH 1LA 0RB 0RC 0RE 3.1 × 10^10566 3.8 × 10^21132
1RB 0LE 1LC 0RA 1LD 0RC 1LE 0LF 1LA 1LC 1LE 1RH 4.6 × 10^1439 2.5 × 10^2879
1RB 0RF 0LB 1LC 1LD 0RC 1LE 1RH 1LF 0LD 1RA 0LE 2.5 × 10^881 8.9 × 10^1762
1RB 0LF 0RC 0RD 1LD 1RE 0LE 0LD 0RA 1RC 1LA 1RH 1.2 × 10^865 3.0 × 10^1730
1RB 0LB 0RC 1LB 1RD 0LA 1LE 1LF 1LA 0LD 1RH 1LE 6.4 × 10^462 6.1 × 10^925
1RB 0LC 1LA 1RC 1RA 0LD 1LE 1LC 1RF 1RH 1RA 1RE 1.4 × 10^60 6.1 × 10^119
1RB 0LB 1LC 0RE 1RE 0LD 1LA 1LA 0RA 0RF 1RE 1RH 6.9 × 10^49 5.5 × 10^99
1RB 0LC 1LA 1LD 1RD 0RC 0LB 0RE 1RC 1LF 1LE 1RH 1.1 × 10^49 3.2 × 10^98
1RB 0LC 1LA 1RD 1RA 0LE 1RA 0RB 1LF 1LC 1RD 1RH 6.7 × 10^47 2.0 × 10^95
1RB 0LC 1LA 1RD 0LB 0LE 1RA 0RB 1LF 1LC 1RD 1RH 6.7 × 10^47 2.0 × 10^95
1RB 0RC 0LA 0RD 1RD 1RH 1LE 0LD 1RF 1LB 1RA 1RE 2.5 × 10^21 5.3 × 10^42

Turing machines with 2 states and 3 symbols

Turing machines with 3 states and 3 symbols

A0 A1 A2 B0 B1 B2 C0 C1 C2 sigma(M) s(M)
1RB 2LA 1LC 0LA 2RB 1LB 1RH 1RA 1RC 374,676,383 119,112,334,170,342,540
1RB 2RC 1LA 2LA 1RB 1RH 2RB 2RA 1LC 95,524,079 4,345,166,620,336,565
1RB 1RH 2LC 1LC 2RB 1LB 1LA 2RC 2LA 2,950,149 4,144,465,135,614
1RB 2LA 1RA 1RC 2RB 0RC 1LA 1RH 1LA 1,525,688 987,522,842,126
1RB 1RH 2RB 1LC 0LB 1RA 1RA 2LC 1RC 107,900 4,939,345,068
1RB 2LA 1RA 1LB 1LA 2RC 1RH 1LC 2RB 43,925 1,808,669,066
1RB 2LA 1RA 1LC 1LA 2RC 1RH 1LA 2RB 43,925 1,808,669,046
1RB 1LB 2LA 1LA 1RC 1RH 0LA 2RC 1LC 32,213 544,884,219
1RB 0LA 1LA 2RC 1RC 1RH 2LC 1RA 0RC 20,240 408,114,977
1RB 2RA 2RC 1LC 1RH 1LA 1RA 2LB 1LC 36,089 310,341,163
1RB 1RH 2LC 1LC 2RB 1LB 1LA 0RB 2LA 13,949 92,649,163
1RB 2LA 1LA 2LA 1RC 2RB 1RH 0LC 0RA 7,205 51,525,774
1RB 2RA 1LA 2LA 2LB 2RC 1RH 2RB 1RB 12,290 47,287,015
1RB 2RA 1LA 2LC 0RC 1RB 1RH 2LA 1RB 5,600 29,403,894

(The first two machines were discovered by Terry and Shawn Ligocki, the next five ones were by Lafitte and Papazian, the next three ones were by Souris, and the last four ones were by Brady).

Turing machines with 4 states and 3 symbols

A0 A1 A2 B0 B1 B2 C0 C1 C2 D0 D1 D2 sigma(M) s(M)
1RB 1RH 2RC 2LC 2RD 0LC 1RA 2RB 0LB 1LB 0LD 2RC > 1.3 × 10^7036 > 1.0 × 10^14072
1RB 0LB 1RD 2RC 2LA 0LA 1LB 0LA 0LA 1RA 0RA 1RH > 4.2 × 10^6034 > 5.3 × 10^12068
1RB 1LD 1RH 1RC 2LB 2LD 1LC 2RA 0RD 1RC 1LA 0LA > 8.9 × 10^4931 > 7.9 × 10^9863
1RB 2LD 1RH 2LC 2RC 2RB 1LD 0RC 1RC 2LA 2LD 0LB > 2.5 × 10^4561 > 3.9 × 10^9122
1RB 1LA 1RD 2LC 0RA 1LB 2LA 0LB 0RD 2RC 1RH 0LC > 4.0 × 10^3860 > 3.9 × 10^7721
1RB 1RA 0LB 2LC 1LB 1RC 0RD 2LC 1RA 2RA 1RH 1RC > 8.0 × 10^986 > 3.7 × 10^1973
1RB 2RC 1RA 2LC 1LA 1LB 2LD 0LB 0RC 0RD 1RH 0RA > 1.6 × 10^809 > 7.7 × 10^1618
1RB 0LC 1RH 2LC 1RD 0LB 2LA 1LC 1LA 1RB 2LD 2RA > 1.1 × 10^713 > 1.5 × 10^1426
0RB 1LD 1RH 1LA 1RC 1RD 1RB 2LC 1RC 1LA 1LC 2RB 15,008 250,096,776

Turing machines with 2 states and 4 symbols

Turing machines with 3 states and 4 symbols

A0 A1 A2 A3 B0 B1 B2 B3 C0 C1 C2 C3 sigma(M) s(M)
1RB 1RA 2LB 3LA 2LA 0LB 1LC 1LB 3RB 3RC 1RH 1LC > 3.7 × 10^6518 > 5.2 × 10^13036
1RB 1RA 1LB 1RC 2LA 0LB 3LC 1RH 1LB 0RC 2RA 2RC > 2.2 × 10^2372 > 5.9 × 10^4744
1RB 2LB 2RA 1LA 2LA 1RC 0LB 2RA 1RB 3LC 1LA 1RH > 1.4 × 10^2355 > 3.4 × 10^4710
1RB 1LA 3LA 3RC 2LC 2LB 1RB 1RA 2LA 3LC 1RH 1LB > 1.7 × 10^1301 > 8.4 × 10^2601
1RB 3LA 3RC 1RA 2RC 1LA 1RH 2RB 1LC 1RB 1LB 2RA > 2.1 × 10^628 > 3.1 × 10^1256
1RB 0RB 3LC 1RC 0RC 1RH 2RC 3RC 1LB 2LA 3LA 2RB > 4.6 × 10^434 > 7.6 × 10^868
1RB 3RB 2LC 3LA 0RC 1RH 2RC 1LB 1LB 2LA 3RC 2LC > 6.0 × 10^140 > 4.3 × 10^281
1RB 1LA 1LB 1RA 0LA 2RB 2LC 1RH 3RB 2LB 1RC 0RC > 2.4 × 10^26 > 5.7 × 10^52
1RB 3LC 0RA 0LC 2LC 3RC 0RC 1LB 1RA 0LB 0RB 1RH 17,323 262,759,288

Turing machines with 2 states and 5 symbols

A0 A1 A2 A3 A4 B0 B1 B2 B3 B4 sigma(M) s(M)
1RB 2LA 1RA 2LB 2LA 0LA 2RB 3RB 4RA 1RH > 1.7 × 10^352 > 1.9 × 10^704
1RB 2LA 4RA 2LB 2LA 0LA 2RB 3RB 4RA 1RH > 5.2 × 10^105 > 1.6 × 10^211
1RB 2LA 4RA 2LB 2LA 0LA 2RB 3RB 1RA 1RH > 5.2 × 10^105 > 1.6 × 10^211
1RB 2LA 4RA 1LB 2LA 0LA 2RB 3RB 2RA 1RH > 9.3 × 10^30 > 5.2 × 10^61
1RB 0RB 4RA 2LB 2LA 2LA 1LB 3RB 4RA 1RH 172,312,766,455 7,069,449,877,176,007,352,687
1RB 3LA 3LB 0LB 1RA 2LA 4LB 4LA 1RA 1RH 1,194,050,967 339,466,124,499,007,251
1RB 3RB 3RA 1RH 2LB 2LA 4RA 4RB 2LB 0RA 1,194,050,967 339,466,124,499,007,214
1RB 1RH 4LA 4LB 2RA 2LB 2RB 3RB 2RA 0RB 620,906,587 91,791,666,497,368,316
1RB 3LA 1LA 0LB 1RA 2LA 4LB 4LA 1RA 1RH 398,005,342 37,716,251,406,088,468
1RB 2RA 1LA 3LA 2RA 2LA 3RB 4LA 1LB 1RH 114,668,733 9,392,084,729,807,219
1RB 2RA 1LA 1LB 3LB 2LA 3RB 1RH 4RA 1LA 36,543,045 417,310,842,648,366

(These machines were discovered by Terry and Shawn Ligocki).

A0 A1 A2 A3 A4 B0 B1 B2 B3 B4 sigma(M) s(M)
1RB 3LA 1LA 4LA 1RA 2LB 2RA 1RH 0RA 0RB 143 26,375,397,569,930
1RB 3LB 4LB 4LA 2RA 2LA 1RH 3RB 4RA 3RB 4,848,239 14,103,258,269,249
1RB 3RA 4LB 2RA 3LA 2LA 1RH 4RB 4RB 2LB 2,576,467 3,793,261,759,791
1RB 3RA 1LA 1LB 3LB 2LA 4LB 3RA 2RB 1RH 1,137,477 924,180,005,181
1RB 3LB 1RH 1LA 1LA 2LA 3RB 4LB 4LB 3RA 1,957,771 912,594,733,606
1RB 2RB 3LA 2RA 3RA 2LB 2LA 3LA 4RB 1RH 668,420 469,121,946,086
1RB 3RB 3RB 1LA 3LB 2LA 3RA 4LB 2RA 1RH 458,357 233,431,192,481
1RB 3LA 1LB 1RA 3RA 2LB 3LA 3RA 4RB 1RH 90,604 8,619,024,596
1RB 2RB 3RB 4LA 3RA 0LA 4RB 1RH 0RB 1LB 97,104 7,543,673,517
1RB 4LA 1LA 1RH 2RB 2LB 3LA 1LB 2RA 0RB 37 7,021,292,621
1RB 2RB 3LA 2RA 3RA 2LB 2LA 1LA 4RB 1RH 64,665 4,561,535,055
1RB 3LA 4LA 1RA 1LA 2LA 1RH 4RA 3RB 1RA 11,120 148,304,214
1RB 3LA 4LA 1RA 1LA 2LA 1RH 1LA 3RB 1RA 3,685 16,268,767
1RB 3RB 2LA 0RB 1RH 2LA 4RB 3LB 2RB 3RB 4,099 15,754,273

(The first eleven machines were discovered by Lafitte and Papazian, and the last three ones were by T. and S. Ligocki).

Turing machines with 2 states and 6 symbols

A0 A1 A2 A3 A4 A5 B0 B1 B2 B3 B4 B5 sigma(M) s(M)
1RB 2LA 1RH 5LB 5LA 4LB 1LA 4RB 3RB 5LB 1LB 4RA > 1.9 × 10^4933 > 2.4 × 10^9866
1RB 1LB 3RA 4LA 2LA 4LB 2LA 2RB 3LB 1LA 5RA 1RH > 6.9 × 10^4931 > 2.5 × 10^9863
1RB 2LB 4RB 1LA 1RB 1RH 1LA 3RA 5RA 4LB 0RA 4LA > 8.6 × 10^821 > 4.9 × 10^1643
1RB 0RB 3LA 5LA 1RH 4LB 1LA 2RB 3LA 4LB 3RB 3RA > 1.9 × 10^27 > 2.3 × 10^54
1RB 2LA 1RA 1RA 5LB 4LB 1LB 1LA 3RB 4LA 1RH 3LA 15,828 493,600,387
1RB 3LA 3LA 1RA 1RA 3LB 1LB 2LA 2RA 4RB 5LB 1RH 10,249 98,364,599
1RB 3LA 4LA 1RA 3RB 1RH 2LB 1LA 1LB 3RB 5RA 1RH 10,574 94,842,383

Relations between functions S and Sigma

Variants of busy beavers

1 - Busy beavers defined by 4-tuples

2 - Busy beavers whose head can stand still

3 - Two-dimensional busy beavers

 

References

 

Links to the web

 

Link to Pascal Michel's home page