Historical survey of Busy Beavers
Contents
Chronological summary
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 7 states and 2 symbols
Turing machines with 3 states and 3 symbols
Turing machines with 4 states and 3 symbols
Turing machines with 3 states and 4 symbols
Turing machines with 2 states and 6 symbols
Relations between functions S and Sigma
1 - Busy beavers defined by 4-tuples
References
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
Links to the web
Created by Pascal Michel in 2004
Last update: November 2024
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))) |
May 2022 | S. Ligocki | (6,2)-TM: s > 9.6 × 10^78913, sigma > 6.0 × 10^39456 |
May 2022 | Kropitz | (6,2)-TM: s > 5.4 × 10^197282, sigma > 2.0 × 10^98641 (6,2)-TM: s > 8.2 × 10^1,292,913,985, sigma > 1.7 × 10^646,456,993 |
May 2022 | S. Ligocki | (6,2)-TM: s > sigma > 10^(10^(10^(10^20823))) |
May 2022 | Kropitz | (6,2)-TM: s > sigma > 10^^15 |
April 2023 | S. Ligocki | (2,6)-TM: s > sigma > 10^^70 |
April 2023 | Kropitz | (2,6)-TM: s > sigma > 10^^91 |
April 2023 | S. Ligocki, "Iijil" | S(2,4) = 3,932,964, Sigma(2,4) = 2050 |
May 2023 | Kropitz | (3,4)-TM: s > sigma > 10^^2048 (2,6)-TM: s > sigma > 10^^(10^^(10^(10^115))) |
July 2023 | Kropitz | (2,5)-TM: s > 6.5 × 10^38033, sigma > 7.3 × 10^19016 |
April 2024 | Kropitz | (3,4)-TM: s > sigma = 2(^15)5 + 14 |
June 2024 | Yuan | (2,5)-TM: s > sigma > 10^(10^(10^3,314,360)) |
July 2024 | bbchallenge | S(5,2) = 47,176,870, Sigma(5,2) = 4098 |
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.
Holdouts were also studied on the collaborative website bbchallenge: See its pages method, contribute, team, story.
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 | 0LD | 1RC | 0RF | 1LC | 1LA | 0LE | 1RH | 1LF | 0RB | 0RC | 0RE | 10^^15 | 10^^15 |
1RB | 0LA | 1LC | 1LF | 0LD | 0LC | 0LE | 0LB | 1RE | 0RA | 1RH | 1LD | 10^10^10^10^20823 | 10^10^10^10^20823 |
1RB | 1RH | 0LC | 0LD | 1LD | 1LC | 1RE | 1LB | 1RF | 1RD | 0LD | 0RA | 1.7 × 10^646,456,993 | 8.2 × 10^1,292,913,985 |
1RB | 1RH | 1RC | 1RA | 1RD | 0RB | 1LE | 0RC | 0LF | 0LD | 0LB | 1LA | 2.0 × 10^98641 | 5.4 × 10^197282 |
1RB | 1RC | 1LC | 0RF | 1RA | 0LD | 0LC | 0LE | 1LD | 0RA | 1RE | 1RH | 6.0 × 10^39456 | 9.6 × 10^78913 |
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 |
A0 | A1 | B0 | B1 | C0 | C1 | D0 | D1 | E0 | E1 | F0 | F1 |
1RB | 1RA | 0LC | 1LE | 1LD | 1LC | 1LA | 0LB | 1LF | 1RE | 1RH | 0RA |
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 |
A0 | A1 | B0 | B1 | C0 | C1 | D0 | D1 | E0 | E1 | F0 | F1 | G0 | G1 |
0RB | 1RB | 1LC | 0RA | 1RE | 1LF | 1LF | 1RE | 0RD | 1RD | 1LG | 0LG | 1RH | 1LB |
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).
A0 | A1 | A2 | B0 | B1 | B2 | C0 | C1 | C2 |
1RB | 2RA | 1LC | 2LC | 1RB | 2RB | 1RH | 2LA | 1LA |
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 | 3LB | 1RH | 2RA | 2LC | 3RB | 1LC | 2RA | 3RB | 1LB | 3LC | 2RC | 2(^15)5 + 14 | > 2(^15)5 + 14 |
1RB | 0LB | 1RH | 3LA | 0LC | 3RB | 3RC | 1LB | 2RB | 2LA | 3RA | 1LC | > 10^^2048 | > 10^^2048 |
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 | 3LA | 4RB | 0RB | 2LA | 1LB | 2LA | 3LA | 1RA | 1RH | > 10^(10^(10^3,314,360)) | > 10^(10^(10^3,314,360)) |
1RB | 2LB | 4LB | 3LA | 1RH | 1LA | 3RA | 3LB | 0LB | 0RA | > 7.3 × 10^19016 | > 6.5 × 10^38033 |
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 |
(The first machine was discovered by Daniel Yuan, the second one by Pavel Kropitz, the other ones 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).
A0 | A1 | A2 | A3 | A4 | B0 | B1 | B2 | B3 | B4 |
1RB | 3RB | 1RH | 3LA | 1RA | 2LA | 3RA | 4LB | 0LB | 0LA |
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 | 3RB | 5RA | 1LB | 5LA | 2LB | 2LA | 2RA | 4RB | 1RH | 3LB | 2LA | > 10^^(10^^(10^(10^115))) | > 10^^(10^^(10^(10^115))) |
1RB | 3LA | 4LB | 0RB | 1RA | 3LA | 2LA | 2RA | 4LA | 1RA | 5RB | 1RH | > 10^^91 | > 10^^91 |
1RB | 2LA | 1RA | 4LA | 5RA | 0LB | 1LA | 3RA | 2RB | 1RH | 3RB | 4LA | > 10^^70 | > 10^^70 |
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 |
Note about terminology and notations
The top-down way
According to Shawn Ligocki :
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) 2Sigma(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/log2n + 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 S2(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 Sigma2(k,n):
3 symbols | 10 | ? | ||
2 symbols | 4 | 11 | 244 ? | 935,508,401 ? |
2 states | 3 states | 4 states | 5 states |
Note that
S2(3,2) = 32 > S(3,2) = 21,and
Sigma2(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, conditional on a conjecture in number theory). 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