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.

• 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 was 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 were also studied on the collaborative website bbchallenge: See its pages method, contribute, team, story.
  On July 2, 2024, this team officially announced 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 winner 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¹⁰⁵⁶⁶ (s(M) ≈ (3/8) sigma(M)²). 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¹⁸²⁶⁷ (s(M) ≈ (3/5) sigma(M)²). 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³⁹⁴⁵⁶ (s(M) ≈ (8/3) sigma(M)²). 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⁹⁸⁶⁴¹ (s(M) ≈ (4/3) sigma(M)²).

• 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 (s(M) ≈ (4/15) sigma(M)²).

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

• 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 (s(M) ≈ (3/8) sigma(M)²). 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

• Research is going on about Turing machines with 6 states and 2 symbols.
  • In June 2024, "mxdys" found a machine with 6 states and 2 symbols such that this machine is conjectured never to halt, but this conjecture depends on solving a Collatz-like problem out of reach of current mathematics. This machine has been nicknamed "Antihydra". See the analysis of Antihydra by Shawn Ligocki.
    Thus, it seems that it will be very hard to prove the true values of S(6,2) and Sigma(6,2).

  • Many machines with the same property have been found. See bbchallenge wiki about S(6,2).

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

• In May 2024, "Iijil" built a machine with 7 states and 2 symbols (from a Turing machine with 3 states and 3 symbols, see Shawn Ligocki), 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.
  This machine was superseded by the Turing machine with 6 states and 2 symbols found by "mxdys" in June 2024, the behavior of this machine having the same property.

• The "Wythagoras" machine:

• The "Iijil" machine, conjectured never to halt (not in Tree Normal Form):

• 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, "savask" found a Turing machine, 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. This machine has been nicknamed "Bigfoot". See the analysis of Bigfoot by Shawn Ligocki.
    Thus, it seems that it will be very hard to prove the true values of S(3,3) and Sigma(3,3).
    From this machine, Tristan Stérin built a Turing machine with 8 states and 2 symbols with the same behavior. and, in May 2024, "Iijil" built a Turing machine with 7 states and 2 symbols with the same behavior.
    In June 2024, it was found that there is a machine with 6 states and 2 symbols that has the same property. See bbchallenge wiki about cryptids

  • For more informations about the studies of the busy beaver competition for Turing machines with 3 states and 3 symbols, see bbchallenge wiki about S(3,3)

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

• The record holder and some other good machines:

• The "savask" machine Bigfoot, conjectured never to halt:

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

• This machine was proved to be the winner of the Busy besver competition for Turing machines with 2 states and 4 symbols.
  See Shawn Ligocki for the proof that S(2,4) = 3,932,964 and Sigma(2,4) = 2050:
  • Shawn Ligocki and "Iijil" proved this result in April 2023.

  • Andrew Ducharme and Terry Ligocki proved this result again in August 2024.

  • "mxdys" announced, in August 2024, a Coq proof of this result.

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

• Pavel Kropitz found, in April 2024, a machine M with s(M) > sigma(M) = 2(^¹⁵)5 + 14 (s(M) ≈ (4/3) sigma(M)², computed by S. Ligocki). 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¹⁹⁰¹⁶.

• Daniel Yuan found, in June 2024, a machine M with s(M) > sigma(M) > 10^{10103,314,360}. It is the current record holder.

• There have been attempts to prove that the machine found in 2023 by Pavel Kropitz is the best one.
  In April 2024, among 902 holdouts given by Justin Blanchard, Daniel Yuan found a Turing machine, 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. This machine has been nicknamed "Hydra". See the analysis of Hydra by Shawn Ligocki.
  Thus, it seems that it will be very hard to prove the true values of S(2,5) and Sigma(2,5).

• 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 (s(M) ≈ (2/3) sigma(M)²). (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¹⁰¹¹⁵) (s(M) ≈ (2/3) sigma(M)²). (see analysis by S. Ligocki). It is the current record holder.

• The record holder and the past record holders:

• Many names are used by authors: busy beaver game, busy beaver contest, busy beaver problem, busy beaver competition. All of them were first used early:
  • game by Rado (1962),

  • contest and problem by Rado (1963),

  • competition by Green (1964).

• What is exactly a busy beaver is rarely specified. Let us give some exceptions. For some authors, such as Green (1964) and Oberschelp et al. (1988), a busy beaver is any Turing machine that participates to the busy beaver competition and halts. For others, such as Dewdney (1984) and Ben-Amram and Petersen (2002), a busy beaver is a winner of this competition. Rado (1962) called the winner a champion, and this term has been used sometimes afterwards.

• The number of ones left on the tape by the Turing machine M when it stops is often called the score and denoted by sigma(M), since Rado (1962). It is called the productivity by Boolos and Jeffrey (1974), a term used again by Hertel (2009) and Harland (2013,2016). Harland uses the term activity for the number of moves of a Turing machine.

• Almost all authors use the notations Sigma(n) and S(n) for the busy beaver functions. Notable exceptions are:
  • ones (n) and time(n) by Ben-Amram et al. (1996) and Ben-Amram and Petersen (2002),

  • bb(n) and ff(n) by Harland (2013,2016,2022),

  • BB(n) (= S(n)) by Aaronson (2020) and by the bbchallenge collaboration.

• There are two ways to find good competitors in the busy beaver competition.
  • The bottom-up way: by simulating Turing machines with k states and n symbols, you get halting machines, provably non-halting machines, and holdouts.
    Better simulations provide a reduction of holdouts and increasing halting times, in a bottom-up way.

  • The top-down way: you make a program for a Turing machine with k states and n symbols, which executes a prearranged task.
    Better programs provide decreasing numbers of states and symbols, in a top-down way.

• Both bottom-up and top-down ways give lower bounds for the busy beaver functions S(k,n) and Sigma(k,n).
  • The bottom-up way gives lower bounds for small values of k and n. The Turing machines found from this way may be the real winners of the busy beaver competition for k states and n symbols.

  • The top-down way gives lower bounds for large values of k and n. The Turing machines found from this way are certainly very far from the real winners of the busy beaver competition for k states and n symbols.

• The machines presented in these pages come from the bottom-up way, with a notable exception: those discovered by Green (1964).
  See Shawn Ligocki for a modern presentation of Green's machines.

• A list of current champions found using the top-down way is given in the bbchallenge wiki about Champions.
  Notably, "Racheline" claimed that she found, in 2024, the current champions for n × 2 Turing machines for n = 8, 10, 11, 12, 14, 20, 21.
  For example, S(8,2) > 2 ↑⁵ 4.

• Graham's number G was named by Martin Gardner in 1977 in Scientific American. It is famous because it is considered as the largest number ever used in a serious mathematical proof.
  Let g₀ = 4, g_n+1 = 3 ↑^g_n 3 (so g₁ = 3 ↑↑↑↑ 3). Then Graham's number is g₆₄.
  According to Shawn Ligocki :
  • In September 2010, "res001" claimed that Sigma(64, 2) > G.

  • In March 2013, "Deedlit" claimed that Sigma(25, 2) > G.

  • In July 2016, "Wythagoras" claimed that Sigma(18, 2) > G.

  • In March 2021, Daniel Nagaj claimed that Sigma(16, 2) > G. See analysis of this machine by Shawn Ligocki

  • In August 2024, "Racheline" claimed that Sigma(14, 2) > G.

  For more data about Graham's number, see also the bbchallenge wiki about Graham's number.

• For more data about the top-down way, see also the googology wiki website.

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

• Rado (1962) proved that
  

  S(n) < (n+1) Sigma(5n)  2^Sigma(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/log₂n + c).

• 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 busy beavers?]
  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)
  Castor quadruplorum
  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.

• bbchallenge is a collaborative website about busy beavers.
  See its pages method, contribute, team, story, and its wiki.

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

• Shawn Ligocki gives studies about busy beavers.

• Heiner Marxen has been the top web reference on busy beavers.

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

Link to Pascal Michel's home page