Historical survey of Busy Beavers

Contents

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 7 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

Properties of functions S and Sigma
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 - Busy beavers on a one-way infinite tape
4 - Two-dimensional busy beavers
5 - Beeping busy beavers
References
Links to the web

Last update: May 2023

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 May 2023 Kropitz (3,4)-TM: s > sigma > 10^^2048 (2,6)-TM: s > sigma > 10^^(10^^(10^(10^115)))

Turing machines with 2 states and 2 symbols

• Rado (1963) claimed that Sigma(2,2) = 4, but that S(2,2) was yet unknown.

• The value S(2,2) = 6 was probably set by Lin in 1963.
See study of the winner by H. Marxen.

• The winner and some other good machines:

 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

• Soon after the definition of the functions S and Sigma, by Rado (1962), it was conjectured that S(3,2) = 21, and Sigma(3,2) = 6.

• Lin (1963) proved this conjecture and this proof was eventually published by Lin and Rado (1965).
See studies by Heiner Marxen of the winners for the S function, and the Sigma function.

• The winners and some other good machines:

 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

• Brady (1964,1965,1966) found a machine M such that s(M) = 107 and sigma(M) = 13 (see study by H. Marxen), and conjectured that S(4,2) = 107 and Sigma(4,2) = 13.

• Brady (1974,1975) proved this conjecture, and the proof was eventually published in Brady (1983).

• Independently, Machlin and Stout (1990) published another proof of the same result, first reported by Kopp (1981) (Kopp is the maiden name of Machlin).

• Independently, Weimann, Casper and Fenzl (1973) claimed that they proved this conjecture.

• The winner and some other good machines:

 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

• Green (1964) found a machine M with sigma(M) = 17.

• Lynn (1972) found machines M and N with s(M) = 435 and sigma(N) = 22.

• Weimann (1973) found a machine M with s(M) = 556 and sigma(M) = 40.

• Lynn, cited by Brady (1983), found in 1974 machines M and N with s(M) = 7,707 and sigma(N) = 112.

• Uwe Schult, cited by Ludewig et al. (1983) and by Dewdney (1984a), found, in August 1982, a machine M with s(M) = 134,467 and sigma(M) = 501. This machine was analyzed independently by Ludewig (in Ludewig et al. (1983)), by Robinson (cited by Dewdney (1984b)), and by Michel (1993).

• George Uhing, cited by Dewdney (1985a,b), found, in December 1984, a machine M with s(M) = 2,133,492 and sigma(M) = 1,915. This machine was analyzed by Michel (1993).

• George Uhing, cited by Brady (1988), found, in February 1986, a machine M with s(M) = 2,358,064 (and sigma(M) = 1,471). This machine was analyzed by Michel (1993). Machine 7 in Marxen's bb-list can be obtained from Uhing's one, as given by Brady (1988), by the permutation of states (A D B E) (see study by H. Marxen).

• Heiner Marxen and Jürgen Buntrock found, in August 1989, a machine M with s(M) = 11,798,826 and sigma(M) = 4,098. This machine was cited by Marxen and Buntrock (1990), and by Machlin and Stout (1990), and was analyzed by Michel (1993). See study by H. Marxen.

• Heiner Marxen and Jürgen Buntrock found, in September 1989, a machine M with s(M) = 23,554,764 (and sigma(M) = 4,097). This machine was cited by Machlin and Stout (1990), and was analyzed by Michel (1993). See study by H. Marxen. See analysis by P. Michel.

• Heiner Marxen and Jürgen Buntrock found, in September 1989, a machine M with s(M) = 47,176,870 and sigma(M) = 4,098. This machine was cited by Marxen and Buntrock (1990), and was analyzed by Buro (1990) (p. 64-67) and by Michel (1993). See study by H. Marxen. See analysis by P. Michel. It is the current record holder.

• Marxen gives a list of machines M with high values of s(M) and sigma(M).

• The study of Turing machines with 5 states and 2 symbols is still going on. Marxen and Buntrock (1990), Skelet, and Hertel (2009) created programs to detect never halting machines, and manually proved that some machines, undetected by their programs, never halt. In each case, about a hundred holdouts were resisting computer and manual analyses. The number of holdouts is gradually shrinking, due to the work of many people. See the 42 holdouts of Skelet. See the resolution of 14 of them.

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.

• Norbert Bátfai, allowing transitions where the head can stand still, found, in August 2009, a machine M with s(M) = 70,740,810 and sigma(M) = 4098. Note that this machine does not follow the current rules of the busy beaver competition.

• The record holder and some other good machines:

 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

• Green (1964) found a machine M with sigma(M) = 35.

• Lynn (1972) found a machine M with s(M) = 522 and sigma(M) = 42.

• Brady (1983) found machines M and N with s(M) = 13,488 and sigma(N) = 117.

• Uwe Schult, cited by Ludewig et al. (1983) and by Dewdney (1984a), found, in December 1982, a machine M with s(M) = 4,208,824 and sigma(M) = 2,075.

• Heiner Marxen and Jürgen Buntrock found, in January 1990, a machine M with s(M) = 13,122,572,797 and sigma(M) = 136,612. This machine was cited by Marxen and Buntrock (1990). See study by H. Marxen.

• Heiner Marxen and Jürgen Buntrock found, in January 1990, a machine M with s(M) = 8,690,333,381,690,951 and sigma(M) = 95,524,079. This machine was posted on the web (Google groups) on September 3, 1997. See machine 2 in Marxen's bb-list. See study by H. Marxen. See analysis by R. Munafo in his website, and in the present website.

• Heiner Marxen and Jürgen Buntrock found, in July 2000, a machine M with s(M) > 5.3 × 1042 and sigma(M) > 2.5 × 1021. This machine was posted on the web (Google groups) on August 5, 2000. See machine 3 in Marxen's bb-list, and machine k in Marxen's bb-6list. See study by H. Marxen.

• Heiner Marxen and Jürgen Buntrock found, in August 2000, a machine M with s(M) > 6.1 × 10119 and sigma(M) > 1.4 × 1060. This machine was posted on the web (Google groups) on October 23, 2000. See machine o in Marxen's bb-6list. See study by H. Marxen. See analysis by P. Michel.

• Heiner Marxen and Jürgen Buntrock found, in August 2000, a machine M with s(M) > 6.1 × 10925 and sigma(M) > 6.4 × 10462. This machine was posted on the web (Google groups) on October 23, 2000. See machine q in Marxen's bb-6list. See study by H. Marxen. See analyses by R. Munafo, the short one or the long one, and by P. Michel. See detailed analysis in Michel (2015), Section 9.

• Heiner Marxen and Jürgen Buntrock found, in February 2001, a machine M with s(M) > 3.0 × 101730 and sigma(M) > 1.2 × 10865. This machine was posted on the web (Google groups) on March 5, 2001. See machine r in Marxen's bb-6list. See study by H. Marxen. See analysis by P. Michel.

• Marxen gives a list of machines M with high values of s(M) and sigma(M).

• Terry and Shawn Ligocki found, in November 2007, a machine M with s(M) > 8.9 × 101762 and sigma(M) > 2.5 × 10881. See study by H. Marxen. See analysis by P. Michel. See detailed analysis in Michel (2015), Section 8.

• Terry and Shawn Ligocki found, in December 2007, a machine M with s(M) > 2.5 × 102879 and sigma(M) > 4.6 × 101439. See study by H. Marxen. See analysis by P. Michel.

• Pavel Kropitz found, in May 2010, a machine M with s(M) > 3.8 × 1021132 and sigma(M) > 3.1 × 1010566. See study by H. Marxen. See analysis. See detailed analysis in Michel (2015), Section 7.

• Pavel Kropitz found, in June 2010, a machine M with s(M) > 7.4 × 1036534 and sigma(M) > 3.5 × 1018267. See study by H. Marxen. See analysis by P. Michel. See detailed analysis in Michel (2015), Section 6.

• Shawn Ligocki found, in May 2022, a machine M with s(M) > 9.6 × 1078913 and sigma(M) > 6.0 × 1039456. See study by S. Ligocki.

• Pavel Kropitz found, in May 2022, a machine M with s(M) > 5.4 × 10197282 and sigma(M) > 2.0 × 1098641.

• Pavel Kropitz found, in May 2022, a machine M with s(M) > 8.2 × 101,292,913,985 and sigma(M) > 1.7 × 10646,456,993.

• Shawn Ligocki found, in May 2022, a machine M with s(M) > sigma(M) > 1010101020823.

• Pavel Kropitz found, in May 2022, a machine M with s(M) > sigma(M) > 10^^15, that is a tower of powers of 10, with 15 occurences of 10. See analysis by P. Michel. See study by S. Ligocki. It is the current record holder.

• See more analysis of the machines found in May 2022 in https://groups.google.com/g/busy-beaver-discuss

• The record holder and some other good machines:

 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

Turing machines with 7 states and 2 symbols

• Green (1964) found a machine M with sigma(M) = 22961.

• This machine was superseded by the machine with 6 states and 2 symbols found in January 1990 by Heiner Marxen and Jürgen Buntrock.

• "Wythagoras" found, in March 2014, a machine M with s(M) > sigma(M) > 1010101018,705,352.
This machine comes from the (6,2)-TM found by Pavel Kropitz in June 2010, as follows: A seventh state G is added, with the transition (G,0)--> (1,L,E). This state G becomes the initial state. Then the machine is normalized by swapping Left and Right and by the circular permutation of states (A C F E B D G).

• This machine was superseded by the machine with 6 states and 2 symbols found in May 2022 by Pavel Kropitz.

• The "Wythagoras" machine:

 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

• Brady (1988) found a machine M with s(M) = 38 (see study by H. Marxen).

• This machine was found independently by Michel (2004), who gave sigma(M) = 9, and conjectured that S(2,3) = 38 and Sigma(2,3) = 9.

• Lafitte and Papazian (2007) proved this conjecture. T. and S. Ligocki (unpublished) proved this conjecture, independently.

• The winner and some other good machines:

 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

• Chester Y. Lee (1963) gave two machines: a machine M found by David Jefferson, with s(M) = 44 and sigma(M) = 12, and a machine N found by R. Blodgett, with s(N) = 57 and sigma(N) = 9. Note that the definition of Sigma(3,3) is different from the current definition (number of 1s instead of number of non-blank symbols). These machines are cited by Korfhage (1966) (p. 114).

• Michel (2004) found machines M and N with s(M) = 40,737 and sigma(N) = 208.

• Brady found, in November 2004, a machine M with s(M) = 29,403,894 and sigma(M) = 5600 (see study by H. Marxen).

• Brady found, in December 2004, a machine M with s(M) = 92,649,163 and sigma(M) = 13,949 (see study by H. Marxen). See analysis by P. Michel.

• Myron P. Souris found, in July 2005 (M.P. Souris said: actually in 1995, but then no one seemed to care), machines M and N with s(M) = 544,884,219 and sigma(N) = 36,089 (see study of M and study of N by H. Marxen). See analysis of M, and analysis of N, by P. Michel.

• Grégory Lafitte and Christophe Papazian found, in August 2005, a machine M with s(M) = 4,939,345,068 and sigma(M) = 107,900 (see study by H. Marxen). See analysis by P. Michel.

• Grégory Lafitte and Christophe Papazian found, in September 2005, a machine M with s(M) = 987,522,842,126 and sigma(M) = 1,525,688 (see study by H. Marxen). See analysis by P. Michel.

• Grégory Lafitte and Christophe Papazian found, in April 2006, a machine M with s(M) = 4,144,465,135,614 and sigma(M) = 2,950,149 (see study by H. Marxen). See analysis by P. Michel.

• Terry and Shawn Ligocki found, in August 2006, a machine M with s(M) = 4,345,166,620,336,565 and sigma(M) = 95,524,079 (see study by H. Marxen). See analysis.

• Terry and Shawn Ligocki found, in November 2007, a machine M with s(M) = 119,112,334,170,342,540 and sigma(M) = 374,676,383 (see study by H. Marxen). See analysis by P. Michel. See detailed analysis in Michel (2015), Section 3. It is the current record holder.

• Brady gives a list of machines M with high values of s(M).

• The record holder and some other good machines:

 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

• Terry and Shawn Ligocki found, in April 2005, a machine M with s(M) = 250,096,776 and sigma(M) = 15,008 (see study by H. Marxen).

• This machine was superseded by the machines with 3 states and 3 symbols found in July 2005 by Myron P. Souris.

• Terry and Shawn Ligocki found, in October 2007, a machine M with s(M) > 1.5 × 101426 and sigma(M) > 1.1 × 10713 (see study by H. Marxen).

• Terry and Shawn Ligocki found successively, in November 2007, machines M with

• Terry and Shawn Ligocki found successively, in December 2007, machines M with

• Terry and Shawn Ligocki found, in January 2008, a machine M with s(M) > 1.0 × 1014072 and sigma(M) > 1.3 × 107036 (see study by H. Marxen). It is the current record holder.

• The record holder and the past record holders:

 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

• Brady (1988) found a machine M with s(M) = 7,195.

• This machine was found independently and analyzed by Michel (2004), who gave sigma(M) = 90. See study by H. Marxen. See analysis by P. Michel.

• Terry and Shawn Ligocki found, in February 2005, a machine M with s(M) = 3,932,964 and sigma(M) = 2,050. See study by H. Marxen. See analysis by P. Michel. See detailed analysis in Michel (2015), Section 4. It is the current record holder. There is no machine between the first two ones (Ligocki, Brady). There is no machine such that 3,932,964 < s(M) < 200,000,000 (Ligocki, September 2005).

• The record holder and some other good machines:

 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

• Terry and Shawn Ligocki found, in April 2005, a machine M with s(M) = 262,759,288 and sigma(M) = 17,323 (see study by H. Marxen).

• This machine was superseded by the machines with 3 states and 3 symbols found in July 2005 by Myron P. Souris.

• Terry and Shawn Ligocki found, in September 2007, a machine M with s(M) > 5.7 × 1052 and sigma(M) > 2.4 × 1026 (see study by H. Marxen),

• Terry and Shawn Ligocki found successively, in October 2007, machines M with

• Terry and Shawn Ligocki found successively, in November 2007, machines M with

• Terry and Shawn Ligocki found, in December 2007, a machine M with s(M) > 5.2 × 1013036 and sigma(M) > 3.7 × 106518 (see study by H. Marxen).

• Pavel Kropitz found, in May 2023, a machine M with s(M) > sigma(M) > 10^^2048. (see analysis by S. Ligocki). It is the current record holder.

• The record holder and the past record holders:

 A0 A1 A2 A3 B0 B1 B2 B3 C0 C1 C2 C3 sigma(M) s(M) 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

• Terry and Shawn Ligocki found, in February 2005, machines M and N with s(M) = 16,268,767 and sigma(N) = 4,099 (see study by H. Marxen).

• Terry and Shawn Ligocki found, in April 2005, a machine M with s(M) = 148,304,214 and sigma(M) = 11,120 (see study by H. Marxen).

• Grégory Lafitte and Christophe Papazian found, in August 2005, a machine M with s(M) = 8,619,024,596 and sigma(M) = 90,604 (see study by H. Marxen).

• Grégory Lafitte and Christophe Papazian found, in September 2005, a machine M with sigma(M) = 97,104 (and s(M) = 7,543,673,517) (see study by H. Marxen).

• Grégory Lafitte and Christophe Papazian found, in October 2005, a machine M with s(M) = 233,431,192,481 and sigma(M) = 458,357 (see study by H. Marxen).

• Grégory Lafitte and Christophe Papazian found, in October 2005, a machine M with s(M) = 912,594,733,606 and sigma(M) = 1,957,771 (see study by H. Marxen). See analysis by P. Michel.

• Grégory Lafitte and Christophe Papazian found, in December 2005, a machine M with s(M) = 924,180,005,181 (and sigma(M) = 1,137,477) (see study by H. Marxen). See analysis by P. Michel.

• Grégory Lafitte and Christophe Papazian found, in May 2006, a machine M with s(M) = 3,793,261,759,791 and sigma(M) = 2,576,467 (see study by H. Marxen). See analysis by P. Michel.

• Grégory Lafitte and Christophe Papazian found, in June 2006, a machine M with s(M) = 14,103,258,269,249 and sigma(M) = 4,848,239 (see study by H. Marxen). See analysis by P. Michel.

• Grégory Lafitte and Christophe Papazian found, in July 2006, a machine M with s(M) = 26,375,397,569,930 (and sigma(M) = 143) (see study by H. Marxen). See comments

• Terry and Shawn Ligocki found, in August 2006, a machine M with s(M) = 7,069,449,877,176,007,352,687 and sigma(M) = 172,312,766,455 (see study by H. Marxen). See analysis.

• Terry and Shawn Ligocki found, in October 2007, a machine M with s(M) > 5.2 × 1061 and sigma(M) > 9.3 × 1030 (see study by H. Marxen).

• Terry and Shawn Ligocki found, in October 2007, two machines M and N with s(M) = s(N) > 1.6 × 10211 and sigma(M) = sigma(N) > 5.2 × 10105 (see study of M, and study of N by H. Marxen).

• Terry and Shawn Ligocki found, in November 2007, a machine M with s(M) > 1.9 × 10704 and sigma(M) > 1.7 × 10352 (see study by H. Marxen). See analysis by P. Michel. See detailed analysis in Michel (2015), Section 5. It is the current record holder.

• The record holder and some other good machines:

 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).

• Previous record holders and some other good machines:

 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

• Terry and Shawn Ligocki found, in February 2005, machines M and N with s(M) = 98,364,599 and sigma(N) = 10,574 (see study by H. Marxen).

• Terry and Shawn Ligocki found, in April 2005, a machine M with s(M) = 493,600,387 and sigma(M) = 15,828 (see study by H. Marxen).

• This machine was superseded by the machine with 2 states and 5 symbols found in August 2005 by Grégory Lafitte and Christophe Papazian.

• Terry and Shawn Ligocki found, in September 2007, a machine M with s(M) > 2.3 × 1054 and sigma(M) > 1.9 × 1027 (see study by H. Marxen).

• This machine was superseded by the machine with 2 states and 5 symbols found in October 2007 by Terry and Shawn Ligocki.

• Terry and Shawn Ligocki found successively, in November 2007, machines M with

• Terry and Shawn Ligocki found, in January 2008, a machine M with s(M) > 2.4 × 109866 and sigma(M) > 1.9 × 104933 (see study by H. Marxen).

• Shawn Ligocki found, in April 2023, a machine M with s(M) > sigma(M) > 10^^70 (see analysis by S. Ligocki).

• Pavel Kropitz found, in April 2023, a machine M with s(M) > sigma(M) > 10^^91.

• Pavel Kropitz found, in May 2023, a machine M with s(M) > sigma(M) > 10^^(10^^(10^(10^115))). (see analysis by S. Ligocki). It is the current record holder.

• The record holder and the past record holders:

 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

Properties of functions S and Sigma

• Rado (1962) defined S(n) and Sigma(n), that are denoted in these pages by S(n,2) and Sigma(n,2).

• These functions grow faster than any computable function.
Formally, for any computable function f, there is an integer N such that, for any integer n > N,
S(n) > Sigma(n) > f(n).
This was proved by Rado (1962) who defined these functions in order to get noncomputable functions.

• It is easy to prove that the two variables functions S(n,k) and Sigma(n,k) are increasing with the number n of states if the number k of symbols is constant.
Formally, for any integer k, if n > m, then
S(n,k) > S(m,k)   and   Sigma(n,k) > Sigma(m,k).

• As Harland (2016b) noticed, the same result for the number of symbols, with a constant number of states, is far from obvious, and still unproven.
Petersen (2017) proved that functions S(n,k) and Sigma(n,k) are increasing with the number k of symbols if the number n of states is sufficiently large.
The proof uses introspective encoding, a tool developped by Ben-Amram and Petersen (2002).

Relations between functions S and Sigma

• Rado (1962) proved that
S(n) < (n+1) Sigma(5n)  2Sigma(5n).

• Julstrom (1993) proved that
S(n) < Sigma(28n).

• Julstrom (1992) proved that
S(n) < Sigma(20n).

• Wang and Xu (1995) proved that
S(n) < Sigma(10n).

• In an unpublished technical report in German, Buro (1990) (p. 5-6) proved that
S(n) < Sigma(9n).

• Yang, Ding and Xu (1997) proved that
S(n) < Sigma(8n),
and that there is a constant c such that
S(n) < Sigma(3n+c).

• Ben-Amram, Julstrom and Zwick (1996) proved that
S(n) < Sigma(3n+6),
and
S(n) < (2n-1) Sigma(3n+3).

• Ben-Amram and Petersen (2002) proved that there is a constant c such that
S(n) < Sigma(n + 8n/log2n + c).

Variants of busy beavers

1 - Busy beavers defined by 4-tuples

• The Turing machines used for regular busy beavers are based on 5-tuples. For example, the initial transition is
(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).

• A busy beaver competition for such machines was studied by Oberschelp, Schmidt-Göttsch and Todt (1988), who defined two busy beaver functions, for the number of non-blank symbols, and for the number of steps, and gave some values and lower bounds for these functions.

• The busy beaver competition for such machines are also studied by P. Machado and F. Pereira, and B. van Heuveln and his team.

• Harland (2022) (see preprint arXiv: 1610.03184) gave a proof of the following theorem:
For any n-state, m-symbol, 4-tuples machine M, halting on the blank tape, there exists a n-state, m-symbol 5-tuples machine N, halting on the blank tape, such that sigma(N) = sigma(M), that is, with the same number of non-blank symbols written on the tape when it halts.
Moreover, the proof provides a simple algorithm that transforms a 4-tuples machine into an equivalent 5-tuples machine. So Harland concludes that searching for 5-tuples machines subsumes searching for 4-tuples machines.

2 - Busy beavers whose head can stand still

• In the definition of the Turing machines used for regular busy beavers, the tape head has to move one cell right or left at each step, and cannot stand still.
If we allow the tape head to stand still, new machines come into the competition, and they can beat the current champions.

• So Norbert Bátfai found, in August 2009, a Turing machine M with 5 states and 2 symbols with s(M) = 70,740,810 and sigma(M) = 4098. This machine beats the current champion for the number of steps (s = 47,176,870).
It seems that relaxing this condition on moves does not allow us to obtain machines with behaviors different from those of regular busy beavers. But the study is still to be done.

3 - Busy beavers on a one-way infinite tape

• In the definition of the Turing machines used for regular busy beavers, the tape is infinite on both left and right sides. Walsh (1982) considered Turing machines with one-way infinite tape. Initially, the tape head scans the first (leftmost) tape cell. A Turing machine halts either by entering a halting state or by falling off the left end of the tape, that is, moving left from cell 1. If a Turing machine M halts when it starts from a blank tape, its score is defined to be k if the rightmost tape cell ever visited by the head of M is the kth cell from the left. Sigma(n,m) is defined as the largest score of all halting n-state, m-symbol Turing machines. Walsh proved that, with this definition, Sigma(2,3) = 6.

4 - Two-dimensional busy beavers

• The Turing machines used for regular busy beavers have a one-dimensional tape. Turing machines with two-dimensional or higher-dimensional tapes were first defined by Hartmanis and Stearns in 1965 (On the computational complexity of algorithms, Transactions of the AMS, Vol. 117, 285-306).

• Brady (1988) launched the busy beaver competition for two-dimensional Turing machines. He also defined, first, "TurNing machines", where the head reorients itself at each step, and, second, machines that work on a triangular grid.

• Tim Hutton resumed the search for two-dimensional busy beavers and gave the following results:

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.
• Tim Hutton also studied higher-dimensional machines and found that, for all n > 0, Sn(2,2) = 6 and Sigman(2,2) = 4.
He also studied one-dimensional and higher-dimensional Turing machines with relative movements, that is, where the head has an orientation and reorients itself at each step.

5 - Beeping busy beavers

• In a survey article about busy beavers, Scott Aaronson (2020) defined the beeping busy beaver function.
While the classical busy beaver functions are as complex as the halting problem for Turing machines, this new function is as complex as the halting problem for Turing machines with an oracle for the halting problem for Turing machines.

• Let M be a Turing machine with k states and n symbols, without halting state, and let q be a state of machine M.
Machine M is launched on a blank tape, and beeps when it is in state q.
Let s(M,q) be the last time that machine M beeps on the state q (and s(M,q) is infinite if M beeps on state q infinitely often).

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).

• The following results are known:
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)
BBB(2,4) > 6.7 × 10^16 (Nicholas Drozd, January 2022)
BBB(2,4) > 2.0 × 10^23 (Shawn Ligocki, February 2022)
Nicholas Drozd said that it is not difficult to prove that BBB(3,2) = 55 and BBB(2,3) = 59.

See also the web site of the google group Busy Beaver Discuss.

References

• Aaronson S. (2020)
The busy beaver frontier
ACM SIGACT News 51 (3), September 2020, 32-54.

• Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996)
A note on busy beavers and other creatures
Mathematical Systems Theory 29 (4), July-August 1996, 375-386.

• Ben-Amram A.M. and Petersen H. (2002)
Improved bounds for functions related to busy beavers
Theory of Computing Systems 35 (1), January-February 2002, 1-11.

• Boolos G.S., Burgess J.P. and Jeffrey R.C. (2002)
Computability and Logic, 4th Ed.
Cambridge, 2002.

• Brady A.H. (1964)
Solutions to restricted cases of the halting problem
Ph.D. Thesis, Oregon State University, Corvallis, December 1964.

• Brady A.H. (1965)
Solutions of restricted cases of the halting problem used to determine particular values of a non-computable function (abstract)
Notices of the AMS 12 (4), June 1965, 476-477.

• Brady A.H. (1966)
The conjectured highest scoring machines for Rado's Sigma(k) for the value k = 4
IEEE Transactions on Electronic Computers, EC-15, October 1966, 802-803.

• Brady A.H. (1974)
UNSCC Technical Report 11-74-1, November 1974.

• Brady A.H. (1975)
The solution to Rado's busy beaver game is now decided for k = 4 (abstract)
Notices of the AMS 22 (1), January 1975, A-25.

• 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.

• Brady A.H. (1988)
The busy beaver game and the meaning of life
in: The Universal Turing Machine: A Half-Century Survey, R. Herken (Ed.), Oxford University Press, 1988, 259-277.

• Buro M. (1990)
Ein Beitrag zur Bestimmung von Rados Sigma(5) oder Wie fängt man fleissige Biber? (German)
[A contribution to the determination of Rado's Sigma(5), or: How to catch a busy beaver?]
Technical Report 146, Rheinisch-Westfälische Technische Hochschule, Aachen, November 1990.

• Chaitin G. (1987)
Computing the busy beaver function
Open Problems in Communication and Computation, Springer, 1987, 108-112.
Reprinted in: Information, Randomness and Incompleteness, World Scientifics, 2nd Ed. 1990.

• Dewdney A.K. (1984a)
Computer recreations
Scientific American 251 (2), August 1984, 10-17.

• Dewdney A.K. (1984b)
Computer recreations
Scientific American 251 (5), November 1984, 27.

• Dewdney A.K. (1985a)
Computer recreations
Scientific American 252 (3), March 1985, 19.

• Dewdney A.K. (1985b)
Computer recreations
Scientific American 252 (4), April 1985, 16.

• Green M.W. (1964)
A lower bound on Rado's sigma function for binary Turing machines
in: Proceedings of the 5th IEEE Annual Symposium on Switching Circuit Theory and Logical Design, November 1964, 91-94.

• Harland J. (2013)
Busy beaver machines and the observant otter heuristic
in: Proceedings of the 19th Computing: The Australasian Theory Symposium (CATS 2013), January 2013.

• Harland J. (2016)
Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons)
Theoretical Computer Science 646, 20 September 2016, 61-85.
Preprint available at arXiv:1602.03228, 10 February 2016.

• Harland J. (2022)
Generating candidate busy beaver machines (or how to build the zany zoo)
Theoretical Computer Science 922, 24 June 2022, 368-394.
Preprint available at arXiv:1610.03184, 11 October 2016.

• Hertel J. (2009)
Computing the uncomputable Rado sigma function
The Mathematica Journal 11 (2), 2009, 270-283.

• Jones J.P. (1974)
Recursive undecidability - an exposition
The American Mathematical Monthly 81 (7), September 1974, 724-738.

• Julstrom B.A. (1992)
A bound on the shift function in terms of the busy beaver function
SIGACT News 23 (3), Summer 1992, 100-106.

• Julstrom B.A. (1993)
Noncomputability and the busy beaver problem
The UMAP Journal 14 (1), Spring 1993, 39-74.

• Kopp R.J. (1981)
The busy beaver problem
M.A. Thesis, State University of New York, Binghamton, 1981.

• Korfhage R.R. (1966)
Logic and Algorithms: With applications to the computer and information sciences, Wiley, 1966.

• Lafitte G. (2009)
Busy beavers gone wild
in: The Complexity of Simple Programs 2008, EPTCS 1, 2009, 123-129.

• 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.

• Lee C.Y. (1963)
Busy beaver examples
in: Automata Theory: Advanced Concepts in Information Processing Systems, Lectures given at the University of Michigan, Summer 1963, 18-21.

• Lin S. (1963)
Computer studies of Turing machine problems
Ph.D. Thesis, The Ohio State University, Columbus, 1963.

• Lin S. and Rado T. (1965)
Computer studies of Turing machine problems
Journal of the ACM 12 (2), April 1965, 196-212.

• Ludewig J., Schult U. and Wankmüller F. (1983)
Chasing the busy beaver. Notes and observations on a competition to find the 5-state busy beaver
Forschungsberichte des Fachbereiches Informatik Nr 159, Universität Dortmund, 1983 (63 pages).

• Lynn D.S. (1972)
New results for Rado's sigma function for binary Turing machines
IEEE Transactions on Computers C-21 (8), August 1972, 894-896.

• 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.

• Michel P. (1993)
Busy beaver competition and Collatz-like problems
Archive for Mathematical Logic 32 (5), 1993, 351-367.

• Michel P. (2004)
Small Turing machines and generalized busy beaver competition
Theoretical Computer Science 326 (1-3), October 2004, 45-56.

• Michel P. (2015)
Problems in number theory from busy beaver competition
Logical Methods in Computer Science 11 (4:10), 2015, 1-35.

• Obershelp A., Schmidt-Göttsch K. and Todt G. (1988)
Archive for Mathematical Logic 27 (1), 1988, 35-44.

• Petersen H. (2006)
Computable lower bounds for busy beaver Turing machines
Studies in Computational Intelligence 25, 2006, 305-319.

• Petersen H. (2017)
Busy beaver scores and alphabet size
in: Proceedings of the 21st International Symposium on Fundamentals of Computation Theory, FCT 2017, Lecture Notes in Computer Science Vol. 10472, Springer, 2017, 409-417.
Preprint available at arXiv:1704.08752.

• Rado T. (1962)
On non-computable functions
Bell System Technical Journal 41 (3), May 1962, 877-884.

• Rado T. (1963)
On a simple source for non-computable functions
in: Proceedings of the Symposium on Mathematical Theory of Automata, April 1962, Polytechnic Institute of Brooklyn, April 1963, 75-81.

• Walsh T.R.S. (1982)
The busy beaver on a one-way infinite tape
SIGACT News 14 (1), Winter 1982, 38-43.

• Wang K. and Xu S. (1995)
New relation between the shift function and the busy beaver function
Chinese Journal of Advanced Software Research 2 (2), 1995, 192-197.

• Weimann B. (1973)
Untersuchungen über Rado's Sigma-Funktion und eingeschränkte Halteprobleme bei Turingmaschinen (German)
[Studies about Rado's Sigma function and limited halting problems of Turing machines]
Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn, 1973.

• Weimann B., Casper K. and Fenzl W. (1973)
Untersuchungen über haltende Programme für Turing-Maschinen mit 2 Zeichen und bis zu 5 Befehlen (German)
[Studies about halting programs for Turing machines with 2 symbols and up to 5 states]
in: Deussen P. (eds) GI. Gesellschaft für Informatik e.V. 2. Jahrestagung (Karlsruhe, October 1972), Lecture Notes in Economics and Mathematical Systems Vol. 78, Springer, 1973, 72-81.

• Yang R., Ding L. and Xu S. (1997)
Some better results estimating the shift function in terms of busy beaver function
SIGACT News 28 (1), March 1997, 43-48.

Links to the web

• Heiner Marxen is the top web reference on busy beavers.

• Wikipedia has a busy beaver entry.

• Googology-wiki has a busy beaver entry.

• Busy beaver discuss is a Google Group email list about busy beavers, created and managed by Shawn Ligocki.

• "Wythagoras" gives many lower bounds of Sigma(n,m) for high values of n and m.

• John Baez has a busy beaver entry on his blog.

• H.J.M. Wijers gives a comprehensive bibliography on busy beavers.

• Allen H. Brady gives an interesting study of machines with 3 states and 3 symbols.

• Skelet (Georgi Georgiev) works on Turing machines with 5 states and 2 symbols, and reversal Turing machines.

• Daniel Briggs created a website and a forum dedicated to the study of Turing machines with 5 states and 2 symbols.

• Robert Munafo gives many informations on busy beavers, and analyzes some machines with 6 states and 2 symbols.

• E.W. Weisstein from MathWorld is also a good reference.

• Hector Zenil gives a demonstration, on the Wolfram Demonstrations Project. See also his website.

• James Harland studies some inverse functions of the busy beaver function: placid platypus and weary wombat.

• P. Gammies gave java applets simulating busy beavers with 2, 3, 4 states and 2 symbols.

• P. Machado and F. Pereira study also the 4-tuple busy beavers.

• B. van Heuveln leads a team searching for 4-tuple busy beavers.

• Tim Hutton studies two-dimensional and higher-dimensional busy beavers.

• Scott Aaronson shows how busy beavers allow to name big numbers.