Pascal Michel
email: michel@math.univ-paris-diderot.fr

The Busy Beaver Competition: a historical survey

Keywords: Turing machine, busy beaver Mathematics Subject Classification (2010): Primary 03D10, Secondary 68Q04

Tibor Rado defined the Busy Beaver Competition in 1962. He used Turing machines to give explicit definitions for some functions that are not computable and grow faster than any computable function. He put forward the problem of computing the values of these functions on numbers 1, 2, 3, . . .. More and more powerful computers have made possible the computation of lower bounds for these values. In 1988, Brady extended the definitions to functions on two variables.

We give a historical survey of these works. The successive record holders in the Busy Beaver Competition are displayed, with their discoverers, the date they were found, and, for some of them, an analysis of their behavior.

We also survey the relations between busy beaver functions, the variants of their definitions, and the links with logical unprovability.

1 Introduction

Noncomputable functions

In 1936, Turing succeeded in making formal the intuitive notion of a function computable by a finite, mechanical, procedure. He defined what is now called a Turing machine and stated that a function on integers is intuitively computable if and only if it is computable by a Turing machine. Other authors, such as Church, Kleene, Post, and, later, Markov, defined other models of computation that turn out to compute the same functions as Turing machines do. See [START_REF] Soare | Computability and recursion[END_REF][START_REF] Soare | Computability and incomputability in[END_REF][START_REF] Soare | Turing oracle machines, online computing, and three displacements in computability theory[END_REF] for more details about the history of the Church-Turing Thesis, naturally defined functions growing as fast as the k-th busy beaver functions for k ≥ 2. Such functions were found by [START_REF] Nabutovsky | Betti numbers of finitely presented groups and very rapidly growing functions[END_REF]. By using homology of groups, they defined a function growing as fast as the third busy beaver function, and another one growing as fast as the fifth busy beaver function. Michel (2010) went on studying these functions. Scott [START_REF] Aaronson | The busy beaver frontier[END_REF] defined the beeping busy beaver function, which grows as fast as the second busy beaver function. See the definition and values in Section 7.5.

Contents

The paper is structured as follows.

1. Introduction.

Preliminaries.

3. Historical overview.

4. Historical survey (lower bounds for S(n, k) and Σ(n, k), and tables of the Turing machines that achieve these lower bounds).

5. Behaviors of busy beavers. We also display the relations between these behaviors and open problems in mathematics called Collatz-like problems and we resume some machines with non-Collatz-like behaviors. We also present pairs of machines that have the same behaviors, but not the same numbers of states and symbols.

6. Properties of the busy beaver functions and relations between S(n) and Σ(n).

Variants of busy beavers:

-Busy beavers defined by 4-tuples.

-Busy beavers whose head can stand still.

-Busy beavers on a one-way infinite tape.

-Two-dimensional busy beavers.

-Beeping busy beavers 8. The methods.

9. Busy beavers and unprovability.

Preliminaries

There are many possible definitions for a Turing machine. We will follow the conventions chosen by Rado (1962) in his definition of functions Σ and S. A Turing machine has a tape, made of cells, infinite to the left and to the right. On each cell a symbol is written. There is a finite set S = {0, 1, . . .} of symbols. The symbol 0 is the blank symbol. A Turing machine has a tape head, which reads and writes symbols on the tape, and can move in both directions left or right, denoted by L and R. A Turing machine has a finite set of states Q = {A, B, . . .}, plus a special state H, the halting state. A Turing machine has a next move function

δ : Q × S -→ (S × {L, R} × Q) ∪ {(1, R, H)}.
If we have δ(q, a) = (b, d, p), then it means that, when the Turing machine is in state q and reads symbol a on the tape, then it writes symbol b instead of a on the cell currently read, it moves one cell in the direction d ∈ {L, R}, and it changes the state from q to p. Each application of next move function δ is a step of the computation. If δ(q, a) = (1, R, H), then, when the machine is in state q reading symbol a, it writes a 1, moves right, enters state H, and stops. We follow Rado (1962) in not allowing the center direction, that is in compelling the tape head to move left or right at each step. Like Rado, we keep the halting state H out of the set of states. We differ from Rado in not allowing transitions δ(q, a) = (b, d, H) with b = 1, d = R.

Note that such a machine is a universal model of computation. That is, any computable function on integers can be computed by a Turing machine as defined above. Initially, a finite string of symbols is written on the tape. It is called the input, and can be a code for an integer. All other cells contain the blank symbol. The tape head reads the leftmost symbol of the input and the state is the initial state A. Then the computation is launched according to the next move function. If it stops, by entering the halting state H, then the string of symbols written on the tape is the output, which can be a code for an integer. So a Turing machine defines a partial function on integers. Reciprocally, any computable partial function on integers can be computed by a Turing machine as defined above.

In order to define functions Σ and S, Rado (1962) considers Turing machines with n states and two symbols 0 and 1. His definitions can be easily extended to Turing machines with n states and k symbols, k ≥ 3, as Brady (1988) does. We consider the set T M (n, k) of Turing machines with n states and k symbols. With our definitions, it is a finite set with (2kn + 1) kn members. We launch each of these (2kn + 1) kn Turing machines on a blank tape, that is a tape with the blank symbol 0 in each cell. Some of these machines never stop. The other ones, that eventually stop, are called busy beavers, and they are competing in two competitions, for the maximum number of steps and for the maximum number of non-blank symbols left on the tape. Let s(M ) be the number of computation steps taken by the busy beaver M to stop. Let σ(M ) be the number of non-blank symbols left on the tape by the busy beaver M when it stops. Then the busy beaver functions are S(n, k) = max{s(M ) : M is a busy beaver with n states and k symbols}, Σ(n, k) = max{σ(M ) : M is a busy beaver with n states and k symbols}.

For k = 2, we find Rado's functions S(n) = S(n, 2) and Σ(n) = Σ(n, 2).

Note that a permutation of the states, symbols or directions does not change the behavior of a Turing machine. The choice between machines that differ only by such permutations is settled by the following normalizing rule: when a Turing machine is launched on a blank tape, it enters states in the order A, B, C, . . ., it writes symbols in the order 1, 2. . ., and it first moves right. So, normally, the first transition is δ(A, 0) = (1, R, B) or δ(A, 0) = (0, R, B).

Note about terminology and notations

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 [START_REF] Rado | On a simple source for non-computable functions in[END_REF]), 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 [START_REF] Oberschelp | Castor quadruplorum Archive for Mathematical Logic[END_REF], a busy beaver is any Turing machine that participates to the busy beaver competition and halts. For others, such as [START_REF] Uhing | [END_REF] and Ben-Amram and [START_REF] Ben-Amram | Improved bounds for functions related to busy beavers Theory of Computing Systems[END_REF], 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 σ(M ), since Rado (1962). It is called the productivity by [START_REF] Boolos | Computability and Logic Cambridge[END_REF], a term used again by Hertel (2009) and Harland (2013Harland ( ,2016)). Harland uses the term activity for the number of moves of a Turing machine.

Almost all authors use the notations Σ(n) and S(n) for the busy beaver functions. Notable exceptions are: ones (n) and time(n) by [START_REF] Ben-Amram | A note on busy beavers and other creatures Mathematical Systems Theory[END_REF] and Ben-Amram and [START_REF] Ben-Amram | Improved bounds for functions related to busy beavers Theory of Computing Systems[END_REF]; bb(n) and f f (n) by Harland (2013Harland ( ,2016Harland ( ,2022)).

Historical overview

The search for champions in the busy beaver competition can be roughly divided into the following stages. Note that, from the beginnings, computers have been tools to find good competitors, so better results follow more powerful computers.

First stage: Following the definitions. The definitions of the busy beaver functions Σ(n) and S(n) by Rado (1962) were quickly followed by conjectures and proofs for n = 2, 3, by Rado and Lin. Brady (1964) gave a conjecture for n = 4, and Green (1964) gave lower bounds for many values of n. Lynn (1972) improved these lower bounds for n = 5, 6. Brady proved his conjecture for n = 4 in 1974, and published the result in 1983. Details on this first stage can be found in the articles of Lynn (1972) and Brady (1983Brady ( , 1988)).

Second stage: Following the Dortmund contest. More results for n = 5, 6 followed the contest that was organized at Dortmund in 1983, and was wun by Schult. Uhing improved twice the result in 1984 and in 1986. Marxen and Buntrock began a search for competitors for n = 5, 6 in 1989. They quickly found a conjectural winner for n = 5, and went on finding many good machines for n = 6, up to 2001. Michel (1993) studied the behaviors of many competitors for n = 5, proving that they depend on well known open problems in number theory. Details on this second stage can be found in the articles of Dewdney (1984ab,1985ab), Brady (1988), and Marxen and Buntrock (1990). From 1997, results began to be put on the web, either on Google groups, or on personal websites.

Third stage: Machines with more than two symbols. As soon as 1988, Brady extended the busy beaver competition to machines with more than two symbols and gave some lower bounds. Michel (2004) The winner and some other good machines:

A0 A1 B0 B1 s(M ) σ(M ) 1RB 1LB 1LA 1RH 6 4 1RB 1RH 1LB 1LA 6 3 1RB 0LB 1LA 1RH 6 3
4.2 Turing machines with 3 states and 2 symbols

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

• Lin (1963) proved this conjecture and this proof was eventually published by Lin and Rado (1965) [START_REF] Brady | Solutions to restricted cases of the halting problem[END_REF][START_REF] Brady | Solutions of restricted cases of the halting problem used to determine particular values of a non-computable function[END_REF][START_REF] Brady | The conjectured highest scoring machines for Rado's Σ(k) for the value k = 4 IEEE Transactions on Electronic Computers[END_REF] found a machine M such that s(M ) = 107 and σ(M ) = 13.

See study by H. Marxen in http://turbotm.de/~heiner/BB/simTM42_bb.html Brady conjectured that S(4, 2) = 107 and Σ(4, 2) = 13.

• Brady (1974Brady ( ,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, [START_REF] Weimann | 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[END_REF] claimed that they proved this conjecture.

1964 Brady s = 107 σ = 13 1974 Brady S(4, 2) = 107 Σ(4, 2) = 13

The winner and some other good machines:

A0 A1 B0 B1 C0 C1 D0 D1 s(M ) σ(M ) 1RB 1LB 1LA 0LC 1RH 1LD 1RD 0RA 107 1RB 1LD 1LC 0RB 1RA 1LA 1RH 0LC 97 9 1RB 0RC 1LA 1RA 1RH 1RD 1LD 0LB 96 1RB 1LB 0LC 0RD 1RH 1LA 1RA 0LA 96 6 1RB 1LD 0LC 0RC 1LC 1LA 1RH 0LA 84 1RB 1RH 1LC 0RD 1LA 1LB 0LC 1RD 83 8 1RB 0RD 1LC 0LA 1RA 1LB 1RH 0RC 78
• Marxen gives a list of machines M with high values of s(M ) and σ(M ) in http://turbotm.de/~heiner/BB/bb-list

• The study of Turing machines with 5 states and 2 symbols is still going on. Marxen andBuntrock (1990), Skelet, andHertel (2009) (All these machines can be found in Buro (1990), pp. 69-70. The machines M with σ(M ) > 1471 were discovered by Marxen and Buntrock. The machine with the transition (A, 0) → (0, R, B) 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 σ values within the σ range above).

Turing machines with 6 states and 2 symbols

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

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

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

• Uwe Schult, cited by [START_REF] Schult | and by Dewdney (1984a), found, in August 1982, a machine M with s(M ) = 134, 467 and σ(M ) = 501[END_REF] and by Dewdney (1984a), found, in December 1982, a machine M with s(M ) = 4, 208, 824 and σ(M ) = 2, 075.

• Heiner Marxen and Jürgen Buntrock found, in January 1990, a machine M with s(M ) = 13, 122, 572, 797 and σ(M ) = 136, 612. This machine was cited by Marxen and Buntrock (1990) The record holder and some other good machines:

A0 A1 B0 B1 C0 C1 D0 D1 E0 E1 F0 F1 s(M ) > σ(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
.4 × 1RB 0LB 1LC 0RE 1RE 0LD 1LA 1LA 0RA 0RF 1RE 1RH 5.5 × 10 99 6.9 × 1RB 0LC 1LA 1LD 1RD 0RC 0LB 0RE 1RC 1LF 1LE 1RH 3.2 × 10 98 1.1 × 1RB 0LC 1LA 1RD 1RA 0LE 1RA 0RB 1LF 1LC 1RD 1RH 2.0 × 10 95 6.7 × 1RB 0LC 1LA 1RD 0LB 0LE 1RA 0RB 1LF 1LC 1RD 1RH 2.0 × 10 95 6.7 × 1RB 0RC 0LA 0RD 1RD 1RH 1LE 0LD 1RF 1LB 1RA 1RE 5.3 × 10 42 2.5 ×
4.6 Turing machines with 7 states and 2 symbols

• Green (1964) found a machine M with σ(M ) = 22, 961.

• 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 ) > σ(M ) > 10 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
4.7 Turing machines with 2 states and 3 symbols

• Brady (1988) found a machine M with s(M ) = 38 See study by H. Marxen in http://turbotm.de/~heiner/BB/simTM23_cb.html

• This machine was found independently by Michel (2004), who gave σ(M ) = 9 and conjectured that S(2, 3) = 38 and Σ(2, 3) = 9. The winner and some other good machines: 119,112,334,170,342,540 σ = 374,676,383 The record holder and some other good machines: (The first two machines were discovered by Terry and Shawn Ligocki, the next five ones were by Lafitte and Papazian, the next three ones were by Souris, and the last four ones were by Brady).

A0 A1 A2 B0 B1 B2 s(M ) σ(M ) 1RB 2LB 1RH 2LA 2RB 1LB 38 9 1RB 0LB 1RH 2LA 1RB 1RA 29 8 0RB 2LB 1RH 1LA 1RB 1RA 27 6 1RB 2LA 1RH 1LB 1LA 0RA 26 6 1RB 1LA 1LB 0LA 2RA 1RH 26 6 1RB 1LB 1RH 2LA 2RB 1LB 24
A0 A1 A2 B0 B1 B2 C0 C1 C2 s(M) σ(M) 1RB 2LA 1LC 0LA 2RB 1LB 1RH 1RA 1RC
4.9 Turing machines with 4 states and 3 symbols The record holder and the past record holders: • Brady (1988) found a machine M with s(M ) = 7, 195.

A0 A1 A2 B0 B1 B2 C0 C1 C2 D0 D1 D2 s(M ) σ(M ) 1RB 1RH 2RC 2LC 2RD 0LC 1RA 2RB 0LB 1LB 0LD 2RC > 1.0 × 10 14072 > 1.3 × 1RB 0LB 1RD 2RC 2LA 0LA 1LB 0LA 0LA 1RA 0RA 1RH > 5.3 × 10 12068 > 4.2 × 1RB 1LD 1RH 1RC 2LB 2LD 1LC 2RA 0RD 1RC 1LA 0LA > 7.9 × 10 9863 > 8.9 × 1RB 2LD 1RH 2LC 2RC 2RB 1LD 0RC 1RC 2LA 2LD 0LB > 3.9 × 10 9122 > 2.5 × 1RB 1LA 1RD 2LC 0RA 1LB 2LA 0LB 0RD 2RC 1RH 0LC > 3.9 × 10 7721 > 4.0 × 1RB 1RA 0LB 2LC 1LB 1RC 0RD 2LC 1RA 2RA 1RH 1RC > 3.7 ×
• This machine was found independently and analyzed by Michel (2004) 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: The record holder and the past record holders: (These machines were discovered by Terry and Shawn Ligocki).

A0 A1 A2 A3 B0 B1 B2 B3 s(M ) σ(M ) 1RB 2LA 1RA 1RA 1LB 1LA 3RB 1RH
A0 A1 A2 A3 B0 B1 B2 B3 C0 C1 C2 C3 s(M ) σ(M ) 1RB 1RA 2LB 3LA 2LA 0LB 1LC 1LB 3RB 3RC 1RH 1LC > 5.2 × 10 13036 > 3.7 × 1RB 1RA 1LB 1RC 2LA 0LB 3LC 1RH 1LB 0RC 2RA 2RC > 5.9 × 10 4744 > 2.2 × 1RB 2LB 2RA 1LA 2LA 1RC 0LB 2RA 1RB 3LC 1LA 1RH > 3.4 × 10 4710 > 1.4 × 1RB 1LA 3LA 3RC 2LC 2LB 1RB 1RA 2LA 3LC 1RH 1LB > 8.4 × 10 2601 > 1.7 × 1RB 3LA 3RC 1RA 2RC 1LA 1RH 2RB 1LC 1RB 1LB 2RA > 3
Previous record holders and some other good machines: (The first eleven machines were discovered by Lafitte and Papazian, and the last three ones were by T. and S. Ligocki). The record holder and the past record holders: 5 Behaviors of busy beavers

A0 A1 A2 A3 A4 B0 B1 B2 B3 B4 s(M ) σ(M ) 1RB 3LA 1LA 4LA 1RA 2LB 2RA 1RH 0RA 0RB
A0 A1 A2 A3 A4 A5 B0 B1 B2 B3 B4 B5 s(M ) σ(M ) 1RB 2LA 1RH 5LB 5LA 4LB 1LA 4RB 3RB 5LB 1LB 4RA > 2.4 ×

Introduction

How do good machines behave? We give below the tricks that allow them to reach high scores.

A configuration of the Turing machine M is a description of the tape. The position of the tape head and the state are indicated by writing together between parentheses the state and the symbol currently read by the tape head.

For example, the initial configuration on a blank tape is:

. . . 0(A0)0 . . .

We denote by a k the string a . . . a, k times. We write C ⊢ (t) D if the next move function leads from configuration C to configuration D in t computation steps.

Turing machines with 5 states and 2 symbols

Marxen and Buntrock's champion

This machine is the record holder in the Busy Beaver Competition for machines with 5 states and 2 symbols, since 1990.

It was analyzed by Buro (1990) (p. 64-67), and independently by Michel (1993).

Marxen and Buntrock ( 1990) s(M ) = 47, 176, 870 =? S(5, 2) σ(M ) = 4098 =? Σ(5, 2) . . . 01(H0)1(001) 4095 10 . . .

0 1 A 1RB 1LC B 1RC 1RB C 1RD 0LE D 1LA 1LD E 1RH 0LA Let C(n) = . . . 0(

Marxen and Buntrock's runner-up

Marxen and Buntrock ( 1990)

s(M ) = 23, 554, 764 σ(M ) = 4097 0 1 A 1RB 0LD B 1LC 1RD C 1LA 1LC D 1RH 1RE E 1RA 0RB Let C(n) = . . . 0(A0)1 n 0 . . ..

Kropitz's machine found in June 2010

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from June 2010 to May 2022. Kropitz ( 2010) s(M ) and S(6, 2) > 7.4 × 10 36534 σ(M ) and Σ(6, 2) > 3.5 × 10 18267 . A proof of this fact is given by "Cloudy176" in http://googology.wikia.com/wiki/User_blog:Cloudy176/Proving_the_bound_for_S (7) This property was used by "Wythagoras", in March 2014, to define a (7,2)-TM that extends the present (6,2)-TM and enters this configuration C( 2) in two steps. See http://googology.wikia.com/wiki/User_blog:Wythagoras/A_good_bound_for_S (7)%3F

0 1 A 1RB 1LE B 1RC 1RF C 1LD 0RB D 1RE 0LC E 1LA 0RD F 1RH 1RC Let C(n) = . . . 0(
See detailed analysis in [START_REF] Michel | Problems in number theory from busy beaver competition Logical Methods in[END_REF], Section 6.

Kropitz's machine found in May 2010

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from May 2010 to June 2010.

Kropitz ( 2010)

s(M ) > 3.8 × 10 21132 σ(M ) > 3.1 × 10 10566 0 1 A 1RB 0LD B 1RC 0RF C 1LC 1LA D 0LE 1RH E 1LA 0RB F 0RC 0RE
Analysis adapted from Shawn Ligocki: Let C(n, k) = . . . 010 n 1(C1)1 3k 0 . . .. Then we have, for all k ≥ 0, all n ≥ 0, . . . 0(A0)0 . . .

⊢ (47) C(5, 2) C(0, k) ⊢ (3) . . . 01(H0)1 3k+1 0 . . . C(1, k) ⊢ (3k + 37) C(3k + 2, 2) C(2, k) ⊢ (12k + 44) C(4, k + 2) C(3, k) ⊢ (3k + 57) C(3k + 8, 2) C(n + 4, k) ⊢ (27k
• • • Note that C(4n + r, 2) ⊢ (t n ) C(r, u n ), with u n = (3 n+2 -5)/2, and t n = (3 × 9 n+3 -80 × 3 n+3 + 584n -27)/32.
Some configurations take a long time to halt. For example, C(1, 9) ⊢ (t) END with t > 10 10 10 10 10 3520 . See detailed analysis in [START_REF] Michel | Problems in number theory from busy beaver competition Logical Methods in[END_REF], Section 7.

Ligockis' machine found in December 2007

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from December 2007 to May 2010. Terry and Shawn Ligocki (2007) s(M ) > 2.5 × 10 2879 σ(M ) > 4.6 × 10 1439 [START_REF] Michel | [END_REF] n R(bin(p))0 . . ., where R(bin(p)) is the number p written in binary in reverse order, so that C(n, 4m + 1) = C(n + 1, m). The number of transitions between configurations C(n, p) is infinite, but only 18 transitions are used in the computation

0 1 A 1RB 0LE B 1LC 0RA C 1LD 0RC D 1LE 0LF E 1LA 1LC F 1LE 1RH Let C(n, p) = . . . 0(A0)

Ligockis' machine found in November 2007

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from November to December 2007. Terry and Shawn Ligocki (2007) s(M ) > 8.9 × 10 1762 σ(M ) > 2.5 × 10 881 10) n R(bin(p))0 . . ., where R(bin(p)) is the number p written in binary in reverse order, so that C(n, 4m + 1) = C(n + 1, m). The number of transitions between configurations C(n, p) is infinite, but only 12 transitions are used in the computation on a blank tape. For all m ≥ 0, all k ≥ 0, . . . 0(A0)0 . . . [START_REF] Michel | Problems in number theory from busy beaver competition Logical Methods in[END_REF], Section 8.

0 1 A 1RB 0RF B 0LB 1LC C 1LD 0RC D 1LE 1RH E 1LF 0LD F 1RA 0LE Let C(n, p) = . . . 0(F 0)(
⊢ (6) C(0, 15) C(k, 4m + 3) ⊢ (4k + 6) C(k + 2, m) C(2k, 4m) ⊢ (30k 2 + 20k + 15) C(5k + 2, 2m + 1) C(2k + 1, 4m) ⊢ (30k 2 + 40k + 25) C(5k + 2, 32m + 20) C(k, 8m + 2) ⊢ (8k + 20) C(k + 3, 2m + 1) C(2k, 16m + 6) ⊢ (30k 2 + 40k + 23) C(5k + 2, 32m + 20) C(2k + 1, 16m + 6) ⊢ (30k 2 + 80k + 63) C(5k + 7, 2m + 1) C(k, 32m + 14) ⊢ (4k + 18) C(k + 3, 2m +

See detailed analysis in

Marxen and Buntrock's machine found in March 2001

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from March 2001 to November 2007.

Marxen and Buntrock ( 2001) 01) n R(bin(p))0 . . ., where R(bin(p)) is the number p written in binary in reverse order, so that C(n, 4m + 2) = C(n + 1, m). The number of transitions between configurations C(n, p) is infinite, but only 20 transitions are used in the computation Note: Clive Tooth posted an analysis of this machine on Google Groups (sci.math>The Turing machine known as #r), on June 28, 2002. He used the configurations S(n, x) = . . . 0101(B1)010(01) n x0 . . . His analysis can be easily connected to the present one, by noting that C(n, p) ⊢ (15) S(n -2, R(bin(p))).

s(M ) > 3.0 × 10 1730 σ(M ) > 1.2 × 10 865 0 1 A 1RB 0LF B 0RC 0RD C 1LD 1RE D 0LE 0LD E 0RA 1RC F 1LA 1RH Let C(n, p) = . . . 0(A0)(

Marxen and Buntrock's second machine

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from October 2000 to March 2001.

Marxen and Buntrock ( 2000)

s(M ) > 6.1 × 10 925 σ(M ) > 6.4 × 10 462 0 1 A 1RB 0LB B 0RC 1LB C 1RD 0LA D 1LE 1LF E 1LA 0LD F 1RH 1LE Let C(n) = . . . 01 n (B0)0 . . .. Then we have, for all k ≥ 0, . . . 0(A0)0 . . . ⊢ (1) C(1) C(3k) ⊢ (54 × 4 k+1 -27 × 2 k+3 + 26k + 86) C(9 × 2 k+1 -8) C(3k + 1) ⊢ (2048 × (4 k -1)/3 -3 × 2 k+7 + 26k + 792) C(2 k+5 -8) C(3k + 2)
⊢ (3k + 8) . . . 01(H1)( 011) k (0101)0 . . .

So we have:

. . . 0(A0)0 . . . ⊢ (1) C( 1) ⊢ (408) C( 24) ⊢ (14, 100, 774) C( 4600 Note that

C(6k + 1) ⊢ ( ) C(3m) ⊢ ( ) C(6p + 4) ⊢ ( ) C(3q + 2) ⊢ ( ) END, with m = (2 2k+5 -8)/3, p = 3 × 2 m -2, q = (2 2p+6 -10)/3.
So all configurations C(n) lead to a halting configuration. Those taking the most time are C(6k + 1). For example: C( 7) ⊢ (t) END with t > 10 3.9×10 12 .

More generally:

C(6k + 1) ⊢ (t(k)) END with t(k) > 10 10 10 (3k+2)/5

.

See also the analyses by Robert Munafo: the short one in http://mrob.com/pub/math/ln-notes1-4.html#mb6q and the detailed one in http://mrob.com/pub/math/ln-mb6q.html See detailed analysis in [START_REF] Michel | Problems in number theory from busy beaver competition Logical Methods in[END_REF], Section 9.

Marxen and Buntrock's third machine

Marxen and Buntrock ( 2000)

s(M ) > 6.1 × 10 119 σ(M ) > 1.4 × 10 60 0 1 A 1RB 0LC B 1LA 1RC C 1RA 0LD D 1LE 1LC E 1RF 1RH F 1RA 1RE also, for all k, m ≥ 0, . . . 0(A0)0 . . . ⊢ (18) C(1, 2) C(2k, 2m) ⊢ (6k 2 + 22k + 15) C(3k + 1, 4m + 2) C(2k, 32m + 3) ⊢ (6k 2 + 34k + 41) C(3k + 4, 4m + 2) C(2k, 128m + 7) ⊢ (6k 2 + 34k + 45) C(3k + 5, 4m + 2) C(2k, 32m + 15) ⊢ (6k 2 + 28k + 25) . . . 01 6k+11 (H0)R(bin(m))0 . . . C(2k + 1, 4m) ⊢ (6k 2 + 34k + 43) C(3k + 4, 2m) C(2k + 1, 32m + 2) ⊢ (6k 2 + 22k + 27) C(3k + 4, 4m + 2) C(2k + 1, 8m + 6) ⊢ (6k 2 + 22k + 23) C(3k + 4, m) C(2k + 1, 4m + 3) ⊢ (6k 2 + 34k + 41)
C(3k + 4, 2m)

Another Marxen and Buntrock's machine

This machine was discovered in January 1990, and was published on the web (Google groups) on September 3, 1997. It was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols up to July 2000.

Marxen and Buntrock (1997) s(M ) = 8, 690, 333, 381, 690, 951 σ(M ) = 95, 524, 079

0 1 A 1RB 1RA B 1LC 1LB C 0RF 1LD D 1RA 0LE E 1RH 1LF F 0LA 0LC
Note the likeness to the machine N with 3 states and 3 symbols discovered, in August 2006, by Terry and Shawn Ligocki, and studied in Section 5.4.2. For this machine N , we have s(N ) = 4, 345, 166, 620, 336, 565 and σ(N ) = 95, 524, 079, that is, same value of σ, and almost half the value of s. See analysis of this similarity in Section 5.9.

Analysis by Robert Munafo:

Let C(n) = . . . 0(D0)1 n 0 . . .. Then we have, for all k ≥ 0, . . . 0(A0)0 . . .

⊢ (3) C(2) C(4k) ⊢ (8k + 6) . . . 01(H0)(10) 2k 110 . . . C(4k + 1) ⊢ (20k 2 + 56k + 30) C(10k + 9) C(4k + 2) ⊢ (20k 2 + 56k + 33) C(10k + 9) C(4k + 3) ⊢ (20k 2 + 68k + 51) C(10k + 12)
So we have:

. . . 0(A0)0 . . . ⊢ (3) C( 2) ⊢ (33) C( 9 (7, 299, 879, 658, 619, 323) C(191, 048, 152) ⊢ (382, 096, 310) . . . 01(H0)(10) 95524076 110 . . .

5.4

Turing machines with 3 states and 3 symbols

Ligockis' champion

This machine is the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, since November 2007.

Terry and Shawn Ligocki ( 2007) 119, 112, 334, 170, 342, 540 =? S(3, 3) σ(M ) = 374, 676, 383 =? Σ(3, 3)

s(M ) =
0 1 2 A 1RB 2LA 1LC B 0LA 2RB 1LB C 1RH 1RA 1RC Let C(n) = . . . 0(A0)2 n 0 . . .. Then we have, for all k ≥ 0, . . . 0(A0)0 . . . ⊢ (3) C(1) C(8k + 1) ⊢ (112k 2 + 116k + 13) C(14k + 3) C(8k + 2) ⊢ (112k 2 + 144k + 38) C(14k + 7) C(8k + 3) ⊢ (112k 2 + 172k + 54) C(14k + 8) C(8k + 4) ⊢ (112k 2 + 200k + 74) C(14k + 9) C(8k + 5) ⊢ (112k 2 + 228k + 97) . . . 01(H1)2 14k+9 0 . . . C(8k + 6) ⊢ (112k 2 + 256k + 139) C(14k + 14) C(8k + 7) ⊢ (112k 2 + 284k + 169) C(14k + 15) C(8k + 8) ⊢ (112k 2 + 312k + 203) C(14k + 16)
So we have (in 34 transitions):

. . . 0(A0)0 . . . ⊢ (3) C( 1) ⊢ ( 13) C(122, 343, 306) ⊢ (26, 193, 799, 261, 043, 238) C(214, 100, 789) ⊢ (80, 218, 511, 093, 348, 089) . . . 01(H1)2 374676381 0 . . . [START_REF] Michel | Problems in number theory from busy beaver competition Logical Methods in[END_REF], Section 3.

C(3) ⊢ (54) C(8) ⊢ (203) C(16) ⊢ (627) C(30) ⊢ (1915) • • •

See detailed analysis in

Ligockis' machine found in August 2006

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from August 2006 to November 2007.

Terry and Shawn Ligocki ( 2006) s(M ) = 4, 345, 166, 620, 336, 565 σ(M ) = 95, 524, 079

0 1 2 A 1RB 2RC 1LA B 2LA 1RB 1RH C 2RB 2RA 1LC
Note the likeness to the machine N with 6 states and 2 symbols discovered, in January 1990, by Heiner Marxen and Jürgen Buntrock, and studied in Section 5.3.9. For this machine N , we have s(N ) = 8, 690, 333, 381, 690, 951 and σ(N ) = 95, 524, 079, that is, same value of σ, and almost twice the value of s. See analysis of this similarity in Section 5.9.

Analysis by Shawn Ligocki:

Let C(n, 0) = . . . 0(A0)12 n 0 . . ., and C(n, 1) = . . . 0(C0)12 n 0 . . ..

Then we have, for all k ≥ 0,

C(2k, 0) ⊢ (40k 2 + 32k + 5) C(5k + 1, 1) C(2k + 1, 0) ⊢ (40k 2 + 82k + 42) . . . 01 10k+9 (H0)0 . . . C(2k + 1, 1) ⊢ (40k 2 + 52k + 19) C(5k + 3, 1) C(2k + 2, 1) ⊢ (40k 2 + 92k + 53)
C(5k + 5, 0) A. H. Brady (2004)

s(M ) = 3, 932, 964 σ(M ) = 2, 050 0 1 2 A 1RB 1LC 1RH B 1LA 1LC 2RB C 1RB 2LC 1RC
There is a step-by-step correspondence between the configurations of these machines. 5.9.2 (6,2)-TM and (3,3)-TM Marxen and Buntrock (1997) s(M ) = 8, 690, 333, 381, 690, 951 σ(M ) = 95, 524, 079

0 1 A 1RB 1RA B 1LC 1LB C 0RF 1LD D 1RA 0LE E 1RH 1LF F 0LA 0LC
This machine was discovered in January 1990, and was published on the web (Google groups) on September 3, 1997. It was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols up to July 2000. Terry and Shawn Ligocki (2006) s(M ) = 4, 345, 166, 620, 336, 565 σ(M ) = 95, 524, 079

0 1 2 A 1RB 2RC 1LA B 2LA 1RB 1RH C 2RB 2RA 1LC
This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from August 2006 to November 2007.

Note that these machines have same σ value, and the s value of the first one is almost twice the s value of the second one.

The behaviors of these machines can be related as follows. Given the analyses of the (6,2)-TM in Section 5.3.9 and the (3,3)-TM in Section 5.4.2, the following functions f and g can be defined:

       f (4k) undefined, f (4k + 1) = 10k + 9, f (4k + 2) = 10k + 9, f (4k + 3) = 10k + 12.        g(2k, 0) = (5k + 1, 1), g(2k + 1, 0)
undefined, g(2k, 1) = (5k, 0), g(2k + 1, 1) = (5k + 3, 1). Now, let h be defined by h(n, 0) = 10n + 2, h(n, 1) = 10n -1.

Then:

h • g = f • h.
There is no step-by-step correspondence between these machines, but there is a phase correspondence, according to functions f and g.

6 Properties of the busy beaver functions 6.1 Growth properties • Rado (1962) defined S(n) and Σ(n), that are denoted in this article S(n, 2) and Σ(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) > Σ(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 Σ(n, k) are increasing with the number n of states if the number k of symbols is constant. Formally, for any integer k ≥ 2, if n > m, then S(n, k) > S(m, k) and Σ(n, k) > Σ(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. [START_REF] Petersen | Busy beaver scores and alphabet size in[END_REF] proved that functions S(n, k) and Σ(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 the busy beaver functions

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

This machine beats the current champion for the number of steps (s = [START_REF] Rado | On a simple source for non-computable functions in[END_REF]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.

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. [START_REF] Walsh | The busy beaver on a one-way infinite tape SIGACT News[END_REF] 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 M 's head is the kth cell from the left. Σ(n, m) is defined as the largest score of all halting n-state, m-symbol Turing machines. Walsh proved that, with this definition, Σ(2, 3) = 6.

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,. 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. See https://github.com/GollyGang/ruletablerepository/wiki/TwoDimensionalTuringMachines He gave the following results: For S 2 (k, n): (k states, n symbols) Tim Hutton also studied higher-dimensional machines and found that, for all n > 0, S n (2, 2) = 6 and Σ 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.

Beeping busy beavers

In a survey article about busy beavers, Scott [START_REF] Aaronson | The busy beaver frontier[END_REF] 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 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).

• BBB (3,3)

The methods

The machines presented in this paper were discovered by means of computer programs. These programs contain procedures that achieve the following tasks:

1. To enumerate Turing machines without repetition.

2. To simulate Turing machines efficiently.

3. To recognize non-halting Turing machines.

Note that these procedures are often mixed together in real programs as follows: A tree of transition tables is generated, and, as soon as some transitions are defined, the corresponding Turing machine is simulated. If the definition of a new transition is necessary, the tree is extended. If the computation seems to loop, a proof of this fact is provided.

If the purpose is to prove a value for the busy beaver functions, then all Turing machines in a class have to be studied. The machines that pass through the three procedures above are either halting machines, from which the better one is selected, or holdouts waiting for better programs or for hand analyses.

If the purpose is to find lower bounds, a systematic enumeration of machines is not necessary. Terry and Shawn Ligocki said they used simulated annealing to find some of their machines.

The following references can be consulted for more information:

• Brady (1983) and Machlin and Stout (1990) for (4,2)-TM,

• Marxen and Buntrock (1990) and Hertel (2009) for (5,2)-TM,

• Lafitte and Papazian ( 2007) for (2,3)-TM,

• Page about Macro Machines on Marxen's website. See http://turbotm.de/~heiner/BB/macro.html

• Harland (2016) and Harland (2022).

9 Busy beavers and unprovability 9.1 The result Let S(n) = S(n, 2) be Rado's busy beaver function. We know that S(2) = 6, S(3) = 21, S(4) = 107, and we can hope to prove that S(5) = 47, 176, 870. As we will see below, the fact that the busy beaver function S is not computable implies that it is not possible to prove that, for any natural number n, S(n) has its true value. Formally, we have the following theorem.

Theorem. Let T be a well-known mathematical theory such as Peano arithmetic (PA) or Zermelo-Fraenkel set theory with axiom of choice (ZFC). Then there exist numbers N and L such that S(N ) = L, but the sentence "S(N ) = L" is not provable in T . This theorem is an easy consequence of the following proposition.

Proposition. Let T be a well-known mathematical theory such as PA or ZFC. Then there exists a Turing machine with two symbols M that does not stop when it is launched on a blank tape, but the fact that it does not stop is not provable in T .

Proof of the theorem from the proposition. Let M be the Turing machine given by the proposition, let N be the number of states of M , and let L = S(N ). Then, to prove that "S(N ) = L", we have to prove that M does not stop. But, by the proposition, such a proof does not exist.

Note that, if "S(N ) = L" is a true sentence unprovable in theory T , then, for all m > L, "S(N ) < m" is also a true sentence unprovable in theory T .

In the following, we consider many kinds of proofs of the proposition and of the theorem.

A direct proof

This proposition is well-known and a one line proof can be given, as follows.

Proof. If all non-halting machines were provably non-halting, then an algorithm that gives simultaneously the computable enumeration of the halting machines and the computable enumeration of the provably non-halting machines would solve the halting problem on a blank tape. We give a detailed proof for nonspecialist readers.

Detailed proof. Let M 1 , M 2 , . . . be a computably enumerable sequence of all Turing machines with two symbols. Such a sequence can be obtained as follows: we list machines according to their number of states, and, inside the set of machines with n states, we list the machines according to the alphabetical order of their transition tables. Let T 1 , T 2 , . . . be a computably enumerable sequence of the theorems of the theory T . The existence of such a sequence is the main requirement that theory T has to satisfy in order that the proposition holds, and of course such a sequence exists for well-known mathematical theories such as PA or ZFC. Now consider the following algorithms A and B. Algorithm A. We launch the machines M i on the blank tape as follows:

• one step of computation of M 1 ,

• 2 steps of computation of M 1 , 2 steps of computation of M 2 ,

• 3 steps of computation of M 1 , 3 steps of computation of M 2 , 3 steps of computation of M 3 ,

• . . . When a machine M i stops, we add it to a list of machines that stop when they are launched on a blank tape.

Note that, given a machine M , by running Algorithm A we will know that M stops if M stops, but we will never know that M doesn't stop if M doesn't stop. Algorithm B. We launch the algorithm that provides the computably enumerable sequence of theorems of theory T , and each time we get a theorem T i , we look and see if this is a theorem of the form "The Turing machine M does not stop when it is launched on a blank tape". If that is the case, we add M to a list of Turing machines that provably do not stop on a blank tape.

Note that, given a machine M , by running Algorithm B we will know that M is provably non-halting if M is provably non-halting, but we will never know that M is not provably non-halting if M is not provably non-halting. Now we have two algorithms, A and B, and

• Algorithm A gives us a computably enumerable list of the Turing machines that stop when they are launched on a blank tape.

• Algorithm B gives us a computably enumerable list of the Turing machines that provably do not stop on a blank tape.

We mix together these two algorithms, by a procedure called dovetailing, to get Algorithm C, as follows. Algorithm C. So Algorithm C gives us both the list of halting Turing machines and the list of provably non-halting Turing machines (on a blank tape). Now we are ready to prove the proposition. If all non-halting Turing machines were provably non-halting, then Algorithm C would give us the list of halting Turing machines and the list of non-halting Turing machines (on a blank tape). So, given a Turing machine M , by running Algorithm C, we would see M appearing in one of the lists, and we could settle the halting problem for machine M on a blank tape. So Algorithm C would give us a computable procedure to settle the halting problem on a blank tape. But it is known that such a computable procedure does not exist. Thus, there exists a non-halting Turing machine that is not provably non-halting on a blank tape.

• one step of Algorithm

The proposition as a special case of a general result

The proposition is a special case of the following theorem.

Theorem. Let A be a set of natural numbers that is computably enumerable but not computable, and let T be a well-known mathematical theory such as PA or ZFC. Then there exists a natural number n such that the sentence "n is not a member of A" is true but not provable in theory T . Proof. Since A is computably enumerable, there exists an algorithm that enumerates the natural numbers in A. If all natural numbers not in A were provably not in A, then, by enumerating the proofs of theorems of theory T , we would get an algorithm that enumerates the natural numbers not in A. By running simultaneously both these algorithms, we could get a procedure that decides membership in A, contradicting the fact that A is not computable.

The proposition is obtained from this theorem by numbering the list of Turing machines, and by defining A as the set of numbers of Turing machines that stop on a blank tape.

Some theoretical examples of Turing machines that satisfy the proposition

Consider the Turing machine M given by the proposition: M does not stop when it is launched on a blank tape, but this fact is not provable in theory T . Can we get an idea of what such a machine M looks like? We give below some examples of such a Turing machine.

Example 1: Using Gödel's Second Incompleteness Theorem

Let M be a machine that enumerates the theorems of theory T , and stops when it finds a contradiction (such as 0 = 1 if T is Peano arithmetic). Then a proof within theory T that M does not stop would be a proof within theory T of the consistency of T , which is impossible by Gödel's Second Incompleteness Theorem (if theory T is consistent).

Example 2: Using Gödel's First Incompleteness Theorem

Another example can be given using Gödel's First Incompleteness Theorem. If T is PA or ZFC, supposed to be consistent, the proof of this theorem provides a formula F that asserts its own unprovability. Thus F is true, but unprovable within theory T .

Consider the machine M that enumerates the theorems of theory T , and stops when it finds formula F . Machine M does not stop, since F is unprovable, but a proof that it does not stop would be a proof that F is unprovable, so, since F is "F is unprovable", a proof of F , which is impossible, since F is unprovable.

Example 3: Using the Recursion Theorem

As a third example, consider the machine M that enumerates the theorems of theory T (PA or ZFC, supposed to be consistent), and stops when it finds a formula F that says that M itself does not stop. Such a machine can be proved to exist by applying the Recursion Theorem to the function f such that machine M f (x) stops if it finds a proof that machine M x does not stop.

Then F is true, because, if F were false, then M would stop, so F would be a theorem of T , so F would be true. But F is unprovable, because since F is true, M does not stop, so F is not a theorem of theory T . So the fact that M does not stop is true and unprovable.

Some explicit examples of Turing machines that satisfy the proposition

Since May 2016, there are explicit constructions of Turing machines whose behaviors are independent of ZFC. These machines never halt on a blank tape, but this fact cannot be proved in ZFC.

A proof using Kolmogorov complexity

There is another proof of unprovability, based on Kolmogorov complexity. The Kolmogorov complexity of a number is the length of the shortest program from which a universal Turing machine can output this number. By Chaitin's Incompleteness Theorem, for any well-known mathematical theory T , there exists a number n(T ) such that, for all numbers of complexity greater than n(T ), the fact that they have complexity greater than n(T ) is true but unprovable within theory T .

Chaitin's theorem also applies to the complexity defined as follows: The complexity of a number k is the smallest number n of states of a Turing machine with n states and two symbols that outputs this number k, written as a string of k symbols 1, when the machine is launched on a blank tape.

So there exists a number n(T ) such that, for any number k of complexity greater than n(T ), the sentence "the complexity of k is greater than n(T )" is true but unprovable within theory T . But "k > Σ(n(T ))" implies "the complexity of k is greater than n(T )", so, for any number k > Σ(n(T )), the sentence "k > Σ(n(T ))" is true but unprovable within theory T .

For more details, see Chaitin (1987), [START_REF] Boolos | Computability and Logic[END_REF], p. 230, who note that n(T ) < 10 ↑↑ 10, a stack of 10 powers of 10, and Lafitte (2009).

  resumed the search, and his lower bounds were quickly overtaken by those from Brady. Between 2005 and 2008, more than forty new machines, each one breaking a record, were found by two teams: the French one made of Grégory Lafitte TM: s = 92,649,163, σ = 13,949 February 2005 T. and S. Ligocki (2,4)-TM: s = 3,932,964, σ = 2,050 (2,5)-TM: s = 16,268,767, σ = 4,099 (2,6)-TM: s = 98,364,599, σ = 10,574 April 2005 T. and S. Ligocki (4,3)-TM: s = 250,096,776, σ = 15,008 (3,4)-TM: s = 262,759,288, σ = 17,323 (2,5)-TM: s = 148,304,214, σ = 11,120 (2,6)-TM: s = 493,600,387, σ = 15,828 July Souris (3,3)-TM: s = 544,884,219, σ = 36,089 August 2005 Lafitte, Papazian (3,3)-TM: s = 4,939,345,068, σ = 107,900 (2,5)-TM: s = 8,619,024,596, σ = 90,604 September 2005 Lafitte, Papazian (3,3)-TM: s = 987,522,842,126, σ = 1,525,688 (2,5)-TM: σ = 97,104 October 2005 Lafitte, Papazian (2,5)-TM: s = 233,431,192,481, σ = 458,357 (2,5)-TM: s = 912,594,733,606, σ = 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, σ = 2,950,149 May Lafitte, Papazian (2,5)-TM: s = 3,793,261,759,791, σ = 2,576,467 June 2006 Lafitte, Papazian (2,5)-TM: s = 14,103,258,269,249, σ = 4,848,239 July 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, σ = 95,524,079 (2,5)-TM: s > 7.0 × 10 21 , σ = 172,312,766,455

  10 10 10 18,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). See http://googology.wikia.com/wiki/User_blog:Wythagoras/A_good_bound_for_S(7)%3F• This machine was superseded by the machine with 6 states and 2 symbols found in May 2022 by Pavel Kropitz.

•

  [START_REF] Lafitte | • Grégory Lafitte and Christophe Papazian found[END_REF] proved this conjecture. T. and S. Ligocki (unpublished) proved this conjecture, independently.

7 4. 8

 78 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 σ(M ) = 12, and a machine N found by R. Blodgett, with s(M ) = 57 and σ(M ) = 9. Note that the definition of Σ(3, 3) is different from the usual definition (number of 1s instead of number of non-blank symbols). These machines are cited by Korthage (1966) (p. 114).

  1988 Brady s = 7,195 σ = 90 February 2005 T. and S. Ligocki s = 3,932,964 σ = 2,050

4. 13

 13 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 σ(N ) = 10, 574. See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig26_a.html • Terry and Shawn Ligocki found, in April 2005, a machine M with s(M ) = 493, 600, 387 and σ(M ) = 15, 828. See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig26_c.html • This machine was superseded by the machine with 2 states and 5 symbols found in August 2005 by Grégory Lafitte and Christophe Papazian.

5. 3

 3 Turing machines with 6 states and 2 symbols 5.3.1 Kropitz's machine found in May 2022 This machine is the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, since May 2022. Kropitz (2022) s(M ) and S(6, 2) > 10 ∧∧ 15 σ(M ) and Σ(6, 2) > 10 ∧∧ 15 Pavel Kropitz and Shawn Ligocki: Let C(n) = . . . 010 n 110 5 (C0)0 . . .. Then we have, for all k ≥ 0, 9 k+3 -80 × 3 k+3 + 712k + 261)/32) . . . 01(H0)1 n-1 0 . . . C(4k + 1) ⊢ ((3 × 9 k+3 -64 × 3 k+3 + 712k + 981)/32) C((3 k+3 -11)/2) C(4k + 2) ⊢ ((3 × 9 k+3 -64 × 3 k+3 + 712k + 1045)/32) C((3 k+3 -11)/2) C(4k + 3) ⊢ ((3 × 9 k+3 -64 × 3 k+3 + 712k + 1749)/32) C((3 k+3 + 1)/2) with n = (3 k+3 -11)/2. So we have (the final configuration is reached in 17 transitions): . . . 0(A0)0 . . . ⊢ (45) C(5) ⊢ (506) C(35) ⊢ (2, 941, 620, 277) C(88574) ⊢ () • • • . . . 01(H0)1 n 0 . . . with n > 10 ∧∧ 15.

  1) C(2k, 128m + 94) ⊢ (30k 2 + 40k + 39) C(5k + 2, 256m + 84) C(2k + 1, 128m + 94) ⊢ (30k 2 + 80k + 79) C(5k + 9, m) C(k, 256m + 190) ⊢ (4k + 34) C(k + 5, m) C(k, 512m + 30) ⊢ (2k + 43) . . . 0(10) k 1(H0)10100101R(bin(m))0 . . .

  ) ⊢ (2048 × (4 1533 -1)/3 -3 × 2 1540 + 40650) C(2 1538 -8) ⊢ (2 1538 -2) . . . 01(H1)(011) p (0101)0 . . . with p = (2 1538 -10)/3. So the total time is T = 2048 × (4 1533 -1)/3 -11 × 2 1538 + 14141831, and the final number of 1 is 2 × (2 1538 -10)/3 + 4.

  the record holder in the Busy Beaver Competition for machines with 2 states and 4 symbols, since February 2005.

  A, one step of Algorithm B, • 2 steps of Algorithm A, 2 steps of Algorithm B, • 3 steps of Algorithm A, 3 steps of Algorithm B, • . . . Algorithm C gives us simultaneously both the computably enumerable lists provided by Algorithm A and Algorithm B.

Table 2 :

 2 Busy Beaver Competition from 2004 to 2006 Christophe Papazian, and the father-and-son collaboration of Terry and Shawn Ligocki.Four new machines for the classical busy beaver competition of machines with 6 states and 2 symbols were also found, by the Ligockis and by Pavel Kropitz. In May 2022, Shawn Ligocki and Pavel Kropitz found many new machines with 6 states and 2 symbols.With the coming of the web age, researchers have faced two problems: how to announce results, and how to store them. In 1997, Heiner Marxen chose to post them on Google groups, but it seems that the oldest reports are no longer available. From 2004, most results have been announced by sending them by email to several people (for example, the new machines with 6 states and 2 symbols found by Terry and Shawn Ligocki in November and December 2007 were sent by email to six persons: Allen H. Brady, Grégory Lafitte, Heiner Marxen, Pascal Michel, Christophe Papazian and Myron P. Souris). Storing results have been made on web pages (see websites list after the references). Brady has stored results on machines with 3 states and 3 symbols on his own website. Both Marxen and Michel have kept account of all results on their websites. Moreover, Marxen has held simulations, with four variants, of each discovered machine. Michel has held theoretical analyses of many machines. In February 2022, Shawn Logocki created a Google Group email list: https://groups.google.com/g/busy-beaver-discuss on which many results have been posted.

	4 Historical survey
	4.1 Turing machines with 2 states and 2 symbols
	• Rado (1963) claimed that Σ(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
	http://turbotm.de/~heiner/BB/simTM22_bb.html
	for a study of the winner by H. Marxen.
	1963 Rado, Lin S(2, 2) = 6 Σ(2, 2) = 4

  . See studies by Heiner Marxen of the winners for the S function in

	and for the Σ function in
	http://turbotm.de/~heiner/BB/simTM32_bbO.html
				1963 Rado, Lin S(3, 2) = 21 Σ(3, 2) = 6
	The winners and some other good machines:
	A0	A1	B0	B1	C0	C1	s(M ) σ(M )
	1RB 1RH 1LB 0RC 1LC 1LA	21	5
	1RB 1RH 0LC 0RC 1LC 1LA	20	5
	1RB 1LA 0RC 1RH 1LC 0LA	20	5
	0RB 1RH 0LC 1RA 1RB 1LC	17	4
	0RB 1LC 1LA 1RB 1LB 1RH	16	5
	1RB 1RH 0RC 1RB 1LC 1LA	14	6
	1RB 1RC 1LC 1RH 1RA 0LB	13	6
	1RB 1LC 1LA 1RB 1LB 1RH	13	6
	0RB 1LC 1RC 1RB 1LA 1RH	13	5
	1RB 1RA 1LC 1RH 1RA 1LB	12	6
	1RB 1LC 1RC 1RH 1LA 0LB	11	6
	4.3 Turing machines with 4 states and 2 symbols
	http://turbotm.de/~heiner/BB/simTM32_bbS.html

•

  Terry and Shawn Ligocki found, in November 2007, a machine M with s(M ) = 119, 112, 334, 170, 342, 540 and σ(M ) = 374, 676, 383. See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig33_b.html See analysis by P. Michel in Section 5.4.1.

	It is the current record holder.
	• Brady gives a list of machines with high values of s(M ) in
	http://www.cse.unr.edu/~al/BusyBeaver.html
	1966	cited by Korfhage	s = 57	σ ′ = 12
	October 2004	Michel	s = 40,737	σ = 208
	November 2004	Brady	s = 29,403,894	σ = 5,600
	December 2004	Brady	s = 92,649,163	σ = 13,949
	July 2005	Souris	s = 544,884,219	σ = 36,089
	August 2005	Lafitte, Papazian	s = 4,939,345,068	σ = 107,900
	September 2005 Lafitte, Papazian	s = 987,522,842,126	σ = 1,525,688
	April 2006	Lafitte, Papazian	s = 4,144,465,135,614	σ = 2,950,149
	August 2006	T. and S. Ligocki	s = 4,345,166,620,336,565	σ = 95,524,079
	November 2007 T. and S. Ligocki s =

•

  Terry and Shawn Ligocki found, in April 2005, a machine M with s(M ) = 250, 096, 776 and σ(M ) = 15, 008. See study by H. Marxen in November 2007 T. and S. Ligocki s > 3.7 × 10 1973σ > 8.0 × 10 986 s > 3.9 × 10 7721 σ > 4.0 × 10 3860 s > 3.9 × 10 9122 σ > 2.5 × 10 4561 December 2007 T. and S. Ligocki s > 7.9 × 10 9863 σ > 8.9 × 10 4931

	April 2005	T. and S. Ligocki s = 250,096,776	σ = 15,008
	July 2005	Souris	superseded by a (3,3)-TM
	October 2007	T. and S. Ligocki s > 1.5 × 10 1426	σ > 1.1 × 10 713
			s > 7.7 × 10 1618	σ > 1.6 × 10 809
	http://turbotm.de/~heiner/BB/simLig43_a.html
	• This machine was superseded by the machines with 3 states and 3 symbols found in
	July 2005 by Myron P. Souris.

http://turbotm.de/~heiner/BB/simLig43_i.html It is the current record holder. s > 5.3 × 10 12068 σ > 4.2 × 10 6034 January 2008 T. and S. Ligocki s > 1.0 × 10 14072 σ > 1.3 × 10 7036

  × 10 2601 σ > 1.7 × 10 1301 November 2007 T. and S. Ligocki s > 3.4 × 10 4710 σ > 1.4 × 10 2355 s > 5.9 × 10 4744 σ > 2.2 × 10 2372 December 2007 T. and S. Ligocki s > 5.2 × 10 13036 σ > 3.7 × 10 6518

	April 2005	T. and S. Ligocki s = 262,759,288	σ = 17,323
	July 2005	Souris	superseded by a (3,3)-TM
	September 2007 T. and S. Ligocki	s > 5.7 × 10 52	σ > 2.4 × 10 26
			3,932,964 2,050 s > 4.3 × 10 281 σ > 6.0 × 10 140
	1RB 3LA 1LA 1RA 2LA 1RH 3RA 3RB October 2007 T. and S. Ligocki s > 7.6 × 10 868	7,195 σ > 4.6 × 10 434 90
	1RB 3LA 1LA 1RA 2LA 1RH 3LA 3RB s > 3.1 × 10 1256	6,445 σ > 2.1 × 10 628 84
	1RB 3LA 1LA 1RA 2LA 1RH 2RA 3RB 1RB 2RB 3LA 2RA 1LA 3RB 1RH 1LB s > 8.4	6,445 2,351	84 60
	4.11 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 σ(M ) = 17, 323. See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig34_a.html • 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 52 and σ(M ) > 2.4 × 10 26 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig34_b.html • Terry and Shawn Ligocki found successively, in October 2007, machines M with s(M ) > 4.3 × 10 281 and σ(M ) > 6.0 × 10 140 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig34_c.html http://turbotm.de/~heiner/BB/simLig34_i.html It is the current record holder.

  Note: Two machines were discovered by T. and S. Ligocki in February 2005 with s(M ) = 16, 268, 767, and two were in October 2007 with s(M ) > 1.6 × 10 211 .

	A0	A1	A2	A3	A4	B0	B1	B2	B3	B4		s(M )		σ(M )
	1RB	2LA	1RA	2LB	2LA	0LA	2RB	3RB	4RA	1RH	> 1.9 × 10 704	> 1.7 × 10 352
	1RB	2LA	4RA	2LB	2LA	0LA	2RB	3RB	4RA	1RH	> 1.6 × 10 211	> 5.2 × 10 105
	1RB	2LA	4RA	2LB	2LA	0LA	2RB	3RB	1RA	1RH	> 1.6 × 10 211	> 5.2 × 10 105
	1RB	2LA	4RA	1LB	2LA	0LA	2RB	3RB	2RA	1RH		> 5.2 × 10 61	> 9.3 × 10 30
	1RB	0RB	4RA	2LB	2LA	2LA	1LB	3RB	4RA	1RH		> 7.0 × 10 21	172,312,766,455
	1RB	3LA	3LB	0LB	1RA	2LA	4LB	4LA	1RA	1RH	339,466,124,499,007,251	1,194,050,967
	1RB	3RB	3RA	1RH	2LB	2LA	4RA	4RB	2LB	0RA	339,466,124,499,007,214	1,194,050,967
	1RB	1RH	4LA	4LB	2RA	2LB	2RB	3RB	2RA	0RB	91,791,666,497,368,316	620,906,587
	1RB	3LA	1LA	0LB	1RA	2LA	4LB	4LA	1RA	1RH	37,716,251,406,088,468	398,005,342
	1RB	2RA	1LA	3LA	2RA	2LA	3RB	4LA	1LB	1RH	9,392,084,729,807,219	114,668,733
	1RB	2RA	1LA	1LB	3LB	2LA	3RB	1RH	4RA	1LA	417,310,842,648,366	36,543,045
	It is the current record holder.
	February 2005	T. and S. Ligocki	s = 16,268,767			σ = 4,099
	April 2005	T. and S. Ligocki	s = 148,304,214			σ = 11,120
	August 2005	Lafitte, Papazian	s = 8,619,024,596		σ = 90,604
	September 2005 Lafitte, Papazian						σ = 97,104
	October 2005	Lafitte, Papazian	s = 233,431,192,481		σ = 458,357
								s = 912,594,733,606	σ = 1,957,771
	December 2005 Lafitte, Papazian	s = 924,180,005,181
	May 2006	Lafitte, Papazian s = 3,793,261,759,791	σ = 2,576,467
	June 2006	Lafitte, Papazian s = 14,103,258,269,249	σ = 4,848,239
	July 2006	Lafitte, Papazian s = 26,375,397,569,930
	August 2006	T. and S. Ligocki	s > 7.0 × 10 21		σ = 172,312,766,455
	October 2007	T. and S. Ligocki	s > 5.2 × 10 61		σ > 9.3 × 10 30
								s > 1.6 × 10 211		σ > 5.2 × 10 105
	November 2007 T. and S. Ligocki	s > 1.9 × 10 704		σ > 1.7 × 10 352
													.1 × 10 1256	> 2.1 × 10 628
	1RB	0RB	3LC	1RC	0RC	1RH	2RC	3RC	1LB	2LA	3LA	2RB	> 7.6 × 10 868	> 4.6 × 10 434
	1RB	3RB	2LC	3LA	0RC	1RH	2RC	1LB	1LB	2LA	3RC	2LC	> 4.3 × 10 281	> 6.0 × 10 140
	1RB	1LA	1LB	1RA	0LA	2RB	2LC	1RH	3RB	2LB	1RC	0RC	> 5.7 × 10 52	> 2.4 × 10 26
	1RB	3LC	0RA	0LC	2LC	3RC	0RC	1LB	1RA	0LB	0RB	1RH	262,759,288	17,323
	4.12 Turing machines with 2 states and 5 symbols The record holder and some other good machines:
	• Terry and Shawn Ligocki found, in February 2005, machines M and N with s(M ) =
	16, 268, 767 and σ(N ) = 4, 099. See study by H. Marxen in
	http://turbotm.de/~heiner/BB/simLig25_a.html

  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 1643 and σ(M ) > 8.6 × 10 821 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig26_e.html -s(M ) > 2.5 × 10 9863 and σ(M ) > 6.9 × 10 4931 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig26_f.html • Terry and Shawn Ligocki found, in January 2008, a machine M with s(M ) > 2.4×10 9866 and σ(M ) > 1.9 × 10 4933 . See study by H. Marxen in Ligocki s > 4.9 × 10 1643 σ > 8.6 × 10 821 s > 2.5 × 10 9863 σ > 6.9 × 10 4931 January 2008 T. and S. Ligocki s > 2.4 × 10 9866 σ > 1.9 × 10 4933

	http://turbotm.de/~heiner/BB/simLig26_g.html
	It is the current record holder.
	February 2005	T. and S. Ligocki s = 98,364,599	σ = 10,574
	April 2005	T. and S. Ligocki s = 493,600,387	σ = 15,828
	August 2005	Lafitte, Papazian	superseded by a (2,5)-TM
	September 2007 T. and S. Ligocki	s > 2.3 × 10 54	σ > 1.9 × 10 27
	October 2007	T. and S. Ligocki	superseded by a (2,5)-TM
	November 2007 T. and S.

• Terry and Shawn Ligocki found, in September 2007, a machine M with s(M ) > 2.3 × 10 54 and σ(M ) > 1.9 × 10 27 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig26_d.html •

  A0)1 n 0 . . ..

	Then we have, for all k ≥ 0,
	C(3k)	⊢ (5k 2 + 19k + 15)	C(5k + 6)
	C(3k + 1) ⊢ (5k 2 + 25k + 27)	C(5k + 9)
	C(3k + 2)	⊢ (6k + 12)	. . . 01(H0)1(001) k+1 10 . . .
	So we have:	. . . 0(A0)0 . . . =
		C(0) ⊢ (15)
		C(6) ⊢ (73)
		C(16) ⊢ (277)
		C(34) ⊢ (907)
		C(64) ⊢ (2, 757)
		C(114) ⊢ (7, 957)
		C(196) ⊢ (22, 777)
		C(334) ⊢ (64, 407)
		C(564) ⊢ (180, 307)
		C(946) ⊢ (504, 027)
		C(1, 584) ⊢ (1, 403, 967)
		C(2, 646) ⊢ (3, 906, 393)
		C(4, 416) ⊢ (10, 861, 903)
		C(7, 366) ⊢ (30, 196, 527)
		C(12, 284) ⊢ (24, 576)

  Then we have, for all k ≥ 0,

	C(3k)	⊢ (10k 2 + 10k + 4)	C(5k + 3)
	C(3k + 1)	⊢ (3k + 3)	. . . 01(110) k 11(H0)0 . . .
	C(3k + 2) ⊢ (10k 2 + 26k + 12)	C(5k + 7)
	So we have:
		. . . 0(A0)0 . . . =
		C(0) ⊢ (4)
		C(3) ⊢ (24)
		C(8) ⊢ (104)
		C(17) ⊢ (392)
		C(32) ⊢ (1, 272)
		C(57) ⊢ (3, 804)
		C(98) ⊢ (11, 084)
		C(167) ⊢ (31, 692)
		C(282) ⊢ (89, 304)
		C(473) ⊢ (250, 584)
		C(792) ⊢ (699, 604)
		C(1, 323) ⊢ (1, 949, 224)
		C(2, 208) ⊢ (5, 424, 324)
		C(3, 683) ⊢ (15, 087, 204)
		C(6, 142) ⊢ (6, 144)
		. . . 01(110) 2047 11(H0)0 . . .

  A0)1 n 0 . . ..

	with p = (50 × 4 30340 -2)/9.
	So the total time is s(M ) = (125 × 16 30341 + 1750 × 4 30340 + 15)/27 + 19, 885, 154, 163,
	and the final number of 1 is σ(M ) = (25 × 4 30341 + 23)/9.
	Some configurations take a long time to halt. For example, C(2) ⊢ (t) END with t >
	10 10 10 10 18,705,352
	Then we have, for all k ≥ 0,
	. . . 0(A0)0 . . .	⊢ (29)	C(9)
	C(3k + 1)	⊢ (3k + 3)	. . . 0111(011) k (H0)0 . . .
	C(9k + 9)	⊢ ((125 × 16 k+2 + 325 × 4 k+2 + 228k -2289)/27) C((50 × 4 k+1 -11)/3)
	C(9k + 12)	⊢ ((125 × 16 k+2 + 325 × 4 k+2 + 228k -912)/27)	C((50 × 4 k+1 + 1)/3)
	So we have:
		. . . 0(A0)0 . . . ⊢ (29)
		C(9) ⊢ (1293)
		C(63) ⊢ (19, 884, 896, 677)
		C(273063) ⊢ (125 × 16 30341 + 325 × 4 30341 + 6, 916, 380)/27)
	C(50 × 4 30340 + 1)/3) ⊢ (50 × 4 30340 + 7)/3)
		. . . 0111(011) p (H0)0 . . .

  > 7.2 × 10 62 (Shawn Ligocki, February 2022) See analysis by Shawn Ligocki in

	https://www.sligocki.com/2022/02/27/bb-recurrence-relations.html
	• 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.

  9.5.1 Example 1: Yedidia and Aaronson's machineAdam Yedidia and Scott Aaronson gave, in May 2016, a Turing machine with 7910 states and two symbols such as it cannot be proved in ZFC that it never halts. They note that enumerating the theorems of ZFC would need a big number of states. They use a graph theoretic statement that Harvey Friedman proved to be equivalent to the consistency of a theory that implies the consistency of ZFC. By using a new high-level language that is easily compiled down to Turing machine description, they build a machine that would halt if it finds a counterexample to Friedman's statement. See[START_REF] Yedidia | A relatively small Turing machine whose behavior is independent of set theory Complex Systems[END_REF]. 9.5.2 Example 2: O'Rear's machine S. O'Rear improved the number of states to 1919, in September 2016. He improved later the number of states to 748. His machines enumerate the theorems of a formal system which has the same power as ZFC. See https://github.com/sorear/metamath-turing-machines For a general presentation, see also Scott Aaronson's blog, available at http://www.scottaaronson.com/blog/?p=2725

Acknowledgments

This historical survey would not have been possible without the contributions of many people. In particular, many thanks to Scott Aaronson, Norbert Bátfai, Allen Brady, Daniel Briggs, Nicholas Drozd, Serge Grigorieff, James Harland, Tim Hutton, Pavel Kropitz, Grégory Lafitte, Shawn Ligocki, Terry Ligocki, Maurice Margenstern, Heiner Marxen, Armando Matos, Robert Munafo, Christophe Papazian, Holger Petersen, Myron Souris, H.J.M. Wijers, and Hector Zenil.

• Terry and Shawn Ligocki found, in October 2007, a machine M with s(M ) > 1.5×10 1426 and σ(M ) > 1.1 × 10 713 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig43_b.html • Terry and Shawn Ligocki found successively, in November 2007, machines M with s(M ) > 7.7 × 10 1618 and σ(M ) > 1.6 × 10 809 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig43_c.html s(M ) > 3.7 × 10 1973 and σ(M ) > 8.0 × 10 986 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig43_d.html s(M ) > 3.9 × 10 7721 and σ(M ) > 4.0 × 10 3860 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig43_e.html s(M ) > 3.9 × 10 9122 and σ(M ) > 2.5 × 10 4561 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig43_f.html • Terry and Shawn Ligocki found successively, in December 2007, machines M with s(M ) > 7.9 × 10 9863 and σ(M ) > 8.9 × 10 4931 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig43_g.html s(M ) > 5.3 × 10 12068 and σ(M ) > 4.2 × 10 6034 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig43_h.html • Terry and Shawn Ligocki found, in January 2008, a machine M with s(M ) > 1.0 × 10 14072 and σ(M ) > 1.3 × 10 7036 . See study by H. Marxen in -s(M ) > 7.6 × 10 868 and σ(M ) > 4.6 × 10 434 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig34_d.html s(M ) > 3.1 × 10 1256 and σ(M ) > 2.1 × 10 628 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig34_e.html • Terry and Shawn Ligocki found successively, in November 2007, machines M with s(M ) > 8.4 × 10 2601 and σ(M ) > 1.7 × 10 1301 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig34_f.html s(M ) > 3.4 × 10 4710 and σ(M ) > 1.4 × 10 2355 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig34_g.html s(M ) > 5.9 × 10 4744 and σ(M ) > 2.2 × 10 2372 . See study by H. Marxen in http://turbotm.de/~heiner/BB/simLig34_h.html • Terry and Shawn Ligocki found, in December 2007, a machine M with s(M ) > 5.2 × 10 13036 and σ(M ) > 3.7 × 10 6518 . See study by H. Marxen in

The following results are known:

• 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 in https://www.sligocki.com/2021/07/17/bb-collatz.html • 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 in https://www.sligocki.com/2022/02/22/collatz-complex.html 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 in https://www.sligocki.com/2022/04/03/mother-of-giants.html • BBB(2, 3) ≥ 59 (Nicholas Drozd, September 2020)

on a blank tape. For all m ≥ 0, all k ≥ 0, C(k, 4m + 3) ⊢ (4k + 6) C(k + 2, m) C(2k + 1, 4m) ⊢ (6k ⊢ (9k 2 + 13k + 10) . . . 0 [START_REF] Michel | [END_REF] 3k+1 11(H0)10R(bin(m))0 . . . Let C(n, x) = . . . 0(E0)1000( 10) n x0 . . ., so that C(n, 10y) = C(n + 1, y). The number of transitions between configurations C(n, x) is infinite, but only 9 transitions are used in the computation on a blank tape. For all k ≥ 0, . . . 0(A0)0 . . .

So we have (the final configuration is reached in 337 transitions):

. . . 0(A0)0 . . . . . . 0(A0)0 . . .

Note that we have also, for all k ≥ 0,

C(25k + 31, 1) C(4k + 3, 1) ⊢ (40k 2 + 162k + 158) . . . 01(H2)2 10k+16 10 . . .

Lafitte and Papazian's machine found in September 2005

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from September 2005 to April 2006. Lafitte and Papazian (2005) s(M ) = 987, 522, 842, 126

Let C(n, 0) = . . . 0(A0)2 n 0 . . ., and C(n, 1) = . . . 0(A0)2 n 10 . . ..

Then we have, for all k ≥ 0, (444,833,917) . . . 011(H2)2 32210 0 . . .

5.4.7

Souris's machine for Σ (3,3) This machine was the record holder in the Busy Beaver Competition for Σ (3,3), from July to August 2005.

Souris ( 2005) andC(n, 1) = . . . 0(C0)1 n 210 . . ..

Then we have, for all k ≥ 0,

So we have:

Note that we have also, for all k ≥ 0,

C(25k + 24, 0)

Brady's machine

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from December 2004 to July 2005.

Brady ( 2004) andC(n, 1) = . . . 0(A0)1 n 210 . . ..

Then we have, for all k ≥ 0,

So we have:

. . . 0(A0)0 . . . ⊢ (6) C(0 ,1) ⊢ (18) C(5,1) ⊢ (202) C(22,0) ⊢ (1,160) C(53,1) ⊢ (8,146) C(142,0) ⊢ (50,060) C(353,1) ⊢ (318,796) C(892,0) ⊢ (1,986,935) C(2228,1) ⊢ (12,440,056) C(5575,1) ⊢ (77,815,887) C(13947,0) ⊢ (27,897) . . . 01(H2)2 13946 10 . . .

Note that we have also, for all k ≥ 0,

Turing machines with 2 states and 4 symbols

Ligockis' champion

This machine is the record holder in the Busy Beaver Competition for machines with 2 states and 4 symbols, since February 2005.

Terry and Shawn Ligocki (2005) s(M ) = 3, 932, 964 =? S (2,4) σ(M ) = 2, 050 =? Σ(2, 4)

Let C(n, 1) = . . . 0(A0)2 n 10 . . ., and C(n, 2) = . . . 0(A0)2 n 110 . . ..

Then we have, for all k ≥ 0, [START_REF] Michel | Problems in number theory from busy beaver competition Logical Methods in[END_REF], Section 4.

See detailed analysis in

Brady's runner-up

This machine was the record holder in the Busy Beaver Competition for machines with 2 states and 4 symbols, from 1988 to February 2005. Brady (1988)

Let C(n, 0) = . . . 0(A0)3 n 0 . . ., and C(n, 1) = . . . 0(A0)3 n 20 . . ..

Then we have, for all k ≥ 0,

So we have:

⊢ (3k 2 + 5k + 3) . . . 01(H2)2 3k 0 . . .

So we have:

. . . 0(A0)0 . . . ⊢ (1)

See detailed analysis in [START_REF] Michel | Problems in number theory from busy beaver competition Logical Methods in[END_REF], Section 5.

Ligockis' machine found in August 2006

This machine was the record holder in the Busy Beaver Competition for machines with 2 states and 5 symbols, from August 2006 to October 2007.

Terry and Shawn Ligocki ( 2006) s(M ) = 7, 069, 449, 877, 176, 007, 352, 687 σ(M ) = 172, 312, 766, 455

Analysis by Shawn Ligocki:

Let C(n, 1) = . . . 03 n (B0)0 . . ., and C(n, 2) = . . . 013 n (B0)0 . . ., and C(n, 3) = . . . 01403 n (B0)0 . . ., and C(n, 4) = . . . 01413 n (B0)0 . . ..

Then we have, for all k ≥ 0, . . . 0(A0)0 . . .

⊢ (5k 2 + 9k + 4) . . . 011(H1)2 5k+2 0 . . . So we have (in 30 transitions):

. . . 0(A0)0 . . . ⊢ (1) (5,938,337,896,640,612,100,114) . . . 011(H1)2 172312766452 0 . . . ⊢ (3k 2 + 12k + 15)

So we have:

. . . 0(A0)0 . . . ⊢ (69) 18,2) ⊢ (1,522) C(48,1) ⊢ (8,690) C(118,2) ⊢ (54,122) C(298,1) ⊢ (333,315) C(743,2) ⊢ (2,087,687 (766,577,764,781) . . . 013 1957769 1(H0)0 . . .

Note that we have also, for all k ≥ 0,

C(25k + 8, 1) C(4k + 3, 2) ⊢ (145k 2 + 321k + 167) . . . 013 25k+19 1(H0)0 . . .

Collatz-like problems

Sameness of behaviors of the Turing machines above is striking. Their behaviors depend on transitions in the following form:

where a, c are fixed, and b = 0, . . . , a-1. Sometimes, another parameter is added: C(ak+b, p).

These transitions can be compared to the following problem. Let T be defined by

This can also be written

When T is iterated over positive integers, do we always reach the loop:

This question is a famous open problem in mathematics, called 3x + 1 problem, or Collatz problem.

A similar question can be asked about iterating transitions of configurations C(ak + b, p) on positive integers. Do the iterated transitions always reach a halting configuration? For all the machines above (except for the machine with 6 states and 2 symbols in Section 5.3.7), this question is presently an open problem in mathematics. Because of likeness to Collatz problem, these problems are called Collatz-like problems. Thus, for each machine above (except for the machine with 6 states and 2 symbols in Section 5.3.7), the halting problem (that is, on what inputs does this machine stop?) depends on an open Collatz-like problem.

Non-Collatz-like behaviors

Some Turing machines run a large number of steps on a small piece of tape. Such machines do not seem to be Collatz-like. We list below some interesting machines with this sort of behavior.

Turing machines with 3 states and 3 symbols

A. H. Brady (November 2004) s(M ) = 2, 315, 619

Brady called this machine "Surprise-in-a-Box".

See also the simulation by Heiner Marxen: http://turbotm.de/~heiner/BB/simAB3Y_SB.html

Turing machines in distinct classes with similar behaviors

In this section, we give examples of machines that have similar behaviors, but not the same numbers of states and symbols.

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

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

• [START_REF] Wang | New relation between the shift function and the busy beaver function[END_REF] proved that S(n) < Σ(10n).

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

• Yang, Ding and Xu (1997) proved that

and that there is a constant c such that

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

• Ben-Amram and [START_REF] Ben-Amram | Improved bounds for functions related to busy beavers Theory of Computing Systems[END_REF] proved that there is a constant c such that S(n) < Σ(n + 8n/ log 2 n + c).

7 Variants of busy beavers 7.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

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][2][3][4][5][START_REF] Brady | Solutions to restricted cases of the halting problem[END_REF][7][8][START_REF] Heiner Marxen | [END_REF][START_REF] Michel | [END_REF][11]. So Turing machines defined by 4-tuples are also called Post machines, or Post-Turing machines.

A busy beaver competition for such machines was studied by [START_REF] Oberschelp | Castor quadruplorum Archive for Mathematical Logic[END_REF], 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, see http://fmachado.dei.uc.pt/publications and B. van Heuveln and his team, see http://www.cogsci.rpi.edu/~heuveb/Research/BB/index.html In their book, [START_REF] Boolos | Computability and Logic Cambridge[END_REF] used the 4-tuples variant to display the busy beaver problem. Harland (2022) tackled 4-tuples machines and he gave a proof of the following theorem: Theorem. For any n-state, m-symbol, 4-tuples machine M , halting on a blank tape, there exists a n-state, m-symbol, 5-tuples machine N , halting on a blank tape, such that σ(N ) = σ(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.

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