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

• 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

• 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

• 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

• 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 has been going on since 1989.
  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.
  Holdouts have been also studied on the collaborative website bbchallenge: See its pages method, contribute, team, story.
  In September 2023, this team wrote that the analysis of the holdouts is over, allowing the writing of an article.

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

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

• 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 × 10⁴² and sigma(M) > 2.5 × 10²¹. 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 × 10¹¹⁹ and sigma(M) > 1.4 × 10⁶⁰. 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 × 10⁹²⁵ and sigma(M) > 6.4 × 10⁴⁶². 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 × 10¹⁷³⁰ and sigma(M) > 1.2 × 10⁸⁶⁵. 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 × 10¹⁷⁶² and sigma(M) > 2.5 × 10⁸⁸¹. 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 × 10²⁸⁷⁹ and sigma(M) > 4.6 × 10¹⁴³⁹. See study by H. Marxen. See analysis by P. Michel.

• Pavel Kropitz found, in May 2010, a machine M with s(M) > 3.8 × 10²¹¹³² and sigma(M) > 3.1 × 10¹⁰⁵⁶⁶. 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 × 10³⁶⁵³⁴ and sigma(M) > 3.5 × 10¹⁸²⁶⁷. 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 × 10⁷⁸⁹¹³ and sigma(M) > 6.0 × 10³⁹⁴⁵⁶. See study by S. Ligocki.

• Pavel Kropitz found, in May 2022, a machine M with s(M) > 5.4 × 10¹⁹⁷²⁸² and sigma(M) > 2.0 × 10⁹⁸⁶⁴¹.

• Pavel Kropitz found, in May 2022, a machine M with s(M) > 8.2 × 10^{1,292,913,985} and sigma(M) > 1.7 × 10^646,456,993.

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

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

• 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) > 10^{10101018,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:

• 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

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

• There have been attempts to prove that the machine found in 2007 by Terry and Shawn Ligocki is the best one.
  In October 2023, among 160 holdouts given by Justin Blanchard, a specific Turing machine was discovered, such that this machine is conjectured never to halt, but the conjecture depends on solving a Collatz-like problem out of reach of current mathematics.
  Thus, it seems that it will be very hard to prove the true values of S(3,3) and Sigma(3,3). See analysis by Shawn Ligocki.
  From this machine, Tristan Stérin built a Turing machine with 8 states and 2 symbols with the same behavior. Thus, the values of S(8,2) and Sigma(8,2) will also be very hard to prove.

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

• The record holder and some other good machines:

• 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 × 10¹⁴²⁶ and sigma(M) > 1.1 × 10⁷¹³ (see study by H. Marxen).

• Terry and Shawn Ligocki found successively, in November 2007, machines M with
  • s(M) > 7.7 × 10¹⁶¹⁸ and sigma(M) > 1.6 × 10⁸⁰⁹ (see study by H. Marxen),
  • s(M) > 3.7 × 10¹⁹⁷³ and sigma(M) > 8.0 × 10⁹⁸⁶ (see study by H. Marxen),
  • s(M) > 3.9 × 10⁷⁷²¹ and sigma(M) > 4.0 × 10³⁸⁶⁰ (see study by H. Marxen),
  • s(M) > 3.9 × 10⁹¹²² and sigma(M) > 2.5 × 10⁴⁵⁶¹ (see study by H. Marxen).

• Terry and Shawn Ligocki found successively, in December 2007, machines M with
  • s(M) > 7.9 × 10⁹⁸⁶³ and sigma(M) > 8.9 × 10⁴⁹³¹ (see study by H. Marxen),
  • s(M) > 5.3 × 10¹²⁰⁶⁸ and sigma(M) > 4.2 × 10⁶⁰³⁴ (see study by H. Marxen).

• Terry and Shawn Ligocki found, in January 2008, a machine M with s(M) > 1.0 × 10¹⁴⁰⁷² and sigma(M) > 1.3 × 10⁷⁰³⁶ (see study by H. Marxen). It is the current record holder.

• The record holder and the past record holders:

• 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

• 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 × 10⁵² and sigma(M) > 2.4 × 10²⁶ (see study by H. Marxen),

• Terry and Shawn Ligocki found successively, in October 2007, machines M with
  • s(M) > 4.3 × 10²⁸¹ and sigma(M) > 6.0 × 10¹⁴⁰ (see study by H. Marxen),
  • s(M) > 7.6 × 10⁸⁶⁸ and sigma(M) > 4.6 × 10⁴³⁴ (see study by H. Marxen),
  • s(M) > 3.1 × 10¹²⁵⁶ and sigma(M) > 2.1 × 10⁶²⁸ (see study by H. Marxen).

• Terry and Shawn Ligocki found successively, in November 2007, machines M with
  • s(M) > 8.4 × 10²⁶⁰¹ and sigma(M) > 1.7 × 10¹³⁰¹ (see study by H. Marxen),
  • s(M) > 3.4 × 10⁴⁷¹⁰ and sigma(M) > 1.4 × 10²³⁵⁵ (see study by H. Marxen),
  • s(M) > 5.9 × 10⁴⁷⁴⁴ and sigma(M) > 2.2 × 10²³⁷² (see study by H. Marxen).

• Terry and Shawn Ligocki found, in December 2007, a machine M with s(M) > 5.2 × 10¹³⁰³⁶ and sigma(M) > 3.7 × 10⁶⁵¹⁸ (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:

• 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 × 10⁶¹ and sigma(M) > 9.3 × 10³⁰ (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 × 10²¹¹ and sigma(M) = sigma(N) > 5.2 × 10¹⁰⁵ (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 × 10⁷⁰⁴ and sigma(M) > 1.7 × 10³⁵² (see study by H. Marxen). See analysis by P. Michel. See detailed analysis in Michel (2015), Section 5.

• Pavel Kropitz found, in July 2023, a machine M with s(M) > 6.5 × 10³⁸⁰³³ and sigma(M) > 7.3 × 10¹⁹⁰¹⁶. It is the current record holder.

• The record holder and some other good machines:

• Previous record holders and some other good machines:

• 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 × 10⁵⁴ and sigma(M) > 1.9 × 10²⁷ (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
  • s(M) > 4.9 × 10¹⁶⁴³ and sigma(M) > 8.6 × 10⁸²¹ (see study by H. Marxen),
  • s(M) > 2.5 × 10⁹⁸⁶³ and sigma(M) > 6.9 × 10⁴⁹³¹ (see study by H. Marxen).

• Terry and Shawn Ligocki found, in January 2008, a machine M with s(M) > 2.4 × 10⁹⁸⁶⁶ and sigma(M) > 1.9 × 10⁴⁹³³ (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¹⁰¹¹⁵). (see analysis by S. Ligocki). It is the current record holder.

• The record holder and the past record holders:

• 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

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 S₂(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₂(k,n):

  3 symbols	10	?
  2 symbols	4	11	244 ?	935,508,401 ?
  	2 states	3 states	4 states	5 states

  Note that

  S₂(3,2) = 32 > S(3,2) = 21,

  and

  Sigma₂(3,2) = 11 > Sigma(3,2) = 6.

• Tim Hutton also studied higher-dimensional machines and found that, for all n > 0, S_n(2,2) = 6 and Sigma_n(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, 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)
  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

Links to the web