Historical survey of Busy Beavers
Contents
Turing machines with 2 states and 2 symbols
Turing machines with 2 states and 3 symbols
Turing machines with 2 states and 4 symbols
Turing machines with 2 states and 5 symbols
Properties of functions S and Sigma
Variants of busy beavers:
1 - Busy beavers defined by 4-tuplesReferences
2 - Busy beavers whose head can stand still
3 - Busy beavers on a one-way infinite tape
4 - Two-dimensional busy beavers
5 - Beeping busy beavers
Last update: April 2022
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 (7,2)-TM: sigma = 22961 |
1972 | Lynn | (5,2)-TM: s = 435, sigma = 22 (6,2)-TM: s = 522, sigma = 42 |
1973 | Weimann | (5,2)-TM: s = 556, sigma = 40 |
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: s = 4,208,824, 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 |
March 2014 | "Wythagoras" | (7,2)-TM: s > sigma > 10^(10^(10^(10^18,705,352))) |
Turing machines with 2 states and 2 symbols
A0 | A1 | B0 | B1 | sigma(M) | s(M) |
1RB | 1LB | 1LA | 1RH | 4 | 6 |
1RB | 1RH | 1LB | 1LA | 3 | 6 |
1RB | 0LB | 1LA | 1RH | 3 | 6 |
Turing machines with 3 states and 2 symbols
A0 | A1 | B0 | B1 | C0 | C1 | sigma(M) | s(M) |
1RB | 1RH | 1LB | 0RC | 1LC | 1LA | 5 | 21 |
1RB | 1RH | 0LC | 0RC | 1LC | 1LA | 5 | 20 |
1RB | 1LA | 0RC | 1RH | 1LC | 0LA | 5 | 20 |
0RB | 1RH | 0LC | 1RA | 1RB | 1LC | 4 | 17 |
0RB | 1LC | 1LA | 1RB | 1LB | 1RH | 5 | 16 |
1RB | 1RH | 0RC | 1RB | 1LC | 1LA | 6 | 14 |
1RB | 1RC | 1LC | 1RH | 1RA | 0LB | 6 | 13 |
1RB | 1LC | 1LA | 1RB | 1LB | 1RH | 6 | 13 |
0RB | 1LC | 1RC | 1RB | 1LA | 1RH | 5 | 13 |
1RB | 1RA | 1LC | 1RH | 1RA | 1LB | 6 | 12 |
1RB | 1LC | 1RC | 1RH | 1LA | 0LB | 6 | 11 |
Turing machines with 4 states and 2 symbols
A0 | A1 | B0 | B1 | C0 | C1 | D0 | D1 | sigma(M) | s(M) |
1RB | 1LB | 1LA | 0LC | 1RH | 1LD | 1RD | 0RA | 13 | 107 |
1RB | 1LD | 1LC | 0RB | 1RA | 1LA | 1RH | 0LC | 9 | 97 |
1RB | 0RC | 1LA | 1RA | 1RH | 1RD | 1LD | 0LB | 13 | 96 |
1RB | 1LB | 0LC | 0RD | 1RH | 1LA | 1RA | 0LA | 6 | 96 |
1RB | 1LD | 0LC | 0RC | 1LC | 1LA | 1RH | 0LA | 11 | 84 |
1RB | 1RH | 1LC | 0RD | 1LA | 1LB | 0LC | 1RD | 8 | 83 |
1RB | 0RD | 1LC | 0LA | 1RA | 1LB | 1RH | 0RC | 12 | 78 |
Turing machines with 5 states and 2 symbols
Daniel Briggs did some work on this question. See his analyses of some machines. He wrote, in October 2021, that only 10 machines are truly difficult.
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 | 1LC | 1LB | 1RA | 0LD | 0RB | 1LE | 1RH | 0RB | 4097 | 11,821,234 |
1RB | 1RA | 1LC | 1LB | 1RA | 0LD | 1RC | 1LE | 1RH | 0RB | 4097 | 11,821,220 |
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 | 1LC | 1LB | 1RA | 0LD | 0RB | 1LE | 1RH | 1LC | 4097 | 11,811,040 |
1RB | 1RA | 1LC | 1LB | 0RC | 1LD | 1RA | 0LE | 1RH | 1LC | 4097 | 11,811,040 |
1RB | 1RA | 1LC | 1LB | 1RA | 0LD | 1RC | 1LE | 1RH | 1LC | 4097 | 11,811,026 |
1RB | 1RA | 0LC | 0RC | 1RH | 1RD | 1LE | 1RB | 1LA | 1LE | 4096 | 11,811,010 |
1RB | 1RA | 1LC | 1LB | 1RA | 1LD | 0RE | 0LE | 1RH | 1LC | 4097 | 11,804,940 |
1RB | 1RA | 1LC | 1LB | 1RA | 1LD | 1RA | 0LE | 1RH | 1LC | 4097 | 11,804,926 |
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 | 1LA | 0RB | 4097 | 11,792,696 |
1RB | 1RA | 1LC | 1RD | 1LA | 1LC | 1RH | 1RE | 1RA | 0RB | 4097 | 11,792,682 |
0RB | 0LC | 1RC | 1RD | 1LA | 0LE | 1RE | 1RH | 1LA | 1RA | 1471 | 2,358,065 |
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 |
(All these machines can be found in Buro (1990), pp. 69-70. The machines M with sigma(M) > 1471 were discovered by Marxen and Buntrock. The machine with the transition A0 --> 0RB was discovered by Buro, 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 7 states and 2 symbols
A0 | A1 | B0 | B1 | C0 | C1 | D0 | D1 | E0 | E1 | F0 | F1 | G0 | G1 |
1RB | 1RC | 0LG | 1LD | 1RB | 1LF | 1LE | 1RH | 1LF | 1RG | 0LD | 1LB | 0RF |
Turing machines with 2 states and 3 symbols
A0 | A1 | A2 | B0 | B1 | B2 | sigma(M) | s(M) |
1RB | 2LB | 1RH | 2LA | 2RB | 1LB | 9 | 38 |
1RB | 0LB | 1RH | 2LA | 1RB | 1RA | 8 | 29 |
0RB | 2LB | 1RH | 1LA | 1RB | 1RA | 6 | 27 |
1RB | 2LA | 1RH | 1LB | 1LA | 0RA | 6 | 26 |
1RB | 1LA | 1LB | 0LA | 2RA | 1RH | 6 | 26 |
1RB | 1LB | 1RH | 2LA | 2RB | 1LB | 7 | 24 |
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
A0 | A1 | A2 | A3 | B0 | B1 | B2 | B3 | sigma(M) | s(M) |
1RB | 2LA | 1RA | 1RA | 1LB | 1LA | 3RB | 1RH | 2,050 | 3,932,964 |
1RB | 3LA | 1LA | 1RA | 2LA | 1RH | 3RA | 3RB | 90 | 7,195 |
1RB | 3LA | 1LA | 1RA | 2LA | 1RH | 3LA | 3RB | 84 | 6,445 |
1RB | 3LA | 1LA | 1RA | 2LA | 1RH | 2RA | 3RB | 84 | 6,445 |
1RB | 2RB | 3LA | 2RA | 1LA | 3RB | 1RH | 1LB | 60 | 2,351 |
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 |
Properties of functions S and Sigma
S(n) > Sigma(n) > f(n).This was proved by Rado (1962) who defined these functions in order to get noncomputable functions.
S(n,k) > S(m,k) and Sigma(n,k) > Sigma(m,k).
Relations between functions S and Sigma
S(n) < (n+1) Sigma(5n) 2^{Sigma(5n)}.
S(n) < Sigma(28n).
S(n) < Sigma(20n).
S(n) < Sigma(10n).
S(n) < Sigma(9n).
S(n) < Sigma(8n),and that there is a constant c such that
S(n) < Sigma(3n+c).
S(n) < Sigma(3n+6),and
S(n) < (2n-1) Sigma(3n+3).
S(n) < Sigma(n + 8n/log_{2}n + c).
Variants of busy beavers
1 - Busy beavers defined by 4-tuples
(A,0) --> (1,R,B)and generally a transition is
(state, scanned symbol) --> (new written symbol, move of the head, new state)Instead of both writing a symbol and moving the head in one transition, these actions can be split up into two transitions, in the form of a 4-tuple:
(state, scanned symbol) --> (new written symbol or move of the head, new state)This alternative definition was introduced by Post in 1947 (Recursive unsolvability of a problem of Thue, The Journal of Symbolic Logic, Vol. 12, 1-11). So Turing machines defined by 4-tuples are also called Post machines (see the Wikipedia site on Post-Turing machines).
2 - Busy beavers whose head can stand still
3 - Busy beavers on a one-way infinite tape
4 - Two-dimensional busy beavers
For S_{2}(k,n): (k states, n symbols)
3 symbols | 38 | ? | ||
2 symbols | 6 | 32 | 4632 ? | 25,772,988,638 ? |
2 states | 3 states | 4 states | 5 states |
For Sigma_{2}(k,n):
3 symbols | 10 | ? | ||
2 symbols | 4 | 11 | 244 ? | 935,508,401 ? |
2 states | 3 states | 4 states | 5 states |
Note that
S_{2}(3,2) = 32 > S(3,2) = 21,and
Sigma_{2}(3,2) = 11 > Sigma(3,2) = 6.
5 - Beeping busy beavers
Then the beeping busy beaver function is defined by
BBB(k,n) = 1 + max{s(M,q) : M is a Turing machine with k states and n symbols, q is a state of M and s(M,q) is finite}.(The "1 + " is added for technical reasons).
BBB(1,2) = 1 (Scott Aaronson)
BBB(2,2) = 6 (Scott Aaronson)
BBB(3,2) >= 55 (Scott Aaronson)
BBB(4,2) >= 32,779,478 (Nicholas Drozd, July 2021). See analysis by Shawn Ligocki
BBB(5,2) > 2.1 × 10^18 (Nicholas Drozd, January 2022)
BBB(5,2) > 1.7 × 10^502 (Shawn Ligocki, February 2022). See analysis by Shawn Ligocki
BBB(5,2) > 7.4 × 10^4079 (Nicholas Drozd, March 2022)
BBB(5,2) > 10^14006 (Shawn Ligocki, April 2022)
BBB(5,2) > 10^(10^286574) (Shawn Ligocki, April 2022). See analysis by Shawn Ligocki
BBB(2,3) >= 59 (Nicholas Drozd, September 2020)
BBB(3,3) > 7.2 × 10^62 (Shawn Ligocki, February 2022). See analysis by Shawn Ligocki
BBB(2,4) > 1.3 × 10^12 (Nicholas Drozd, January 2022)Nicholas Drozd said that it is not difficult to prove that BBB(3,2) = 55 and BBB(2,3) = 59.
BBB(2,4) > 6.7 × 10^16 (Nicholas Drozd, January 2022)
BBB(2,4) > 2.0 × 10^23 (Shawn Ligocki, February 2022)
See also the web site of the google group Busy Beaver Discuss.
References
Links to the web