cp's OEIS Frontend

"In 1965 Tibor Rado, together with Shen Lin, proved that a(3) is 21. (...) Next, in 1983, Allan Brady proved that a(4) is 107. (...) Then in 1989 Heiner Marxen and Jürgen Buntrock discovered that a(5) is at least 47176870. (...) As for a(6), Marxen and Buntrock set another record in 1997 by proving that it is at least 8690333381690951." [Based on Aaronson's web page.]

The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1's) that a Turing Machine with n internal states (plus the Halt state), 2 symbols, and a two-way infinite tape can write on an initially blank tape (all 0's) and then halt. The function a(n) (the present sequence) denotes the maximal number of steps S(n) = S(n, 2) (thus shifts, since direction NONE is excluded) that such a machine can make (not necessarily the same Turing machine producing a maximum number of 1s and need not even produce many tape marks).

Given that 5-state 2-symbol halting Turing machines can compute Collatz-like congruential functions (see references), it may be very hard to find the next term.

The sequence grows faster than any computable function of n and so is noncomputable.

From Daniel Forgues, Jun 05-06 2011: (Start)

A more precise definition might be as follows:

Busy Beaver Problem: a(n) is the maximal number of steps that an n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) Turing machine can make on an initially blank tape and then halt.

Further comments:

H in H_(n, k) is a halting* Turing machine with n states and k symbols;

* (on a blank tape (all 0's) as input)

States q, q+ in set Q_n of n distinct states (plus the Halt state);

Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol);

Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here);

sigma(H) is the number of non-blank symbols left on the tape by H;

s(H) is the number of steps (or shifts in our case) taken by H;

Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}

S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}

a(n) is S(n) = S(n, 2) since a 2-symbol BB-class Turing machine is assumed.

For all n, S(n, k) >= Sigma(n, k), k >= 2. (End)

a(6) > 10^^15, a tower of 10's of height 15 [Pavel Kropitz] - see Shawn Ligocki's blog. - N. J. A. Sloane, Jun 22 2022

It is conjectured that a(5) = 47176870 (Conjecture 10 of the Scott Aaronson link "The busy beaver frontier"). - Jianing Song, Feb 21 2024

On July 02, 2024 cosmo (Tristan Stérin) on behalf of the Busy Beaver Challenge group announced: "We have proved 'BB(5) = 47,176,870'". - Peter Luschny, Jul 02 2024

The next term is much too large to include in the OEIS or even to conceive. The BBchallenge has found this month (cf. Scott Aaronson link from June 2025) that a(6) > 2^^^5 >> 10^^(10^7) where the repeated ^ stands for Knuth's arrow notation; 10^^(10^7) (tetration) means the power tower 10^(10^(...)) with 10^7 nested "^10" in the exponent, and ^^^ means pentation which is repeated tetration (cf. Wikipedia). - M. F. Hasler, Jun 30 2025

T in T_(n, k) is a Turing machine with n states and k symbols;

States q, q+ in set Q_n of n distinct states (plus the Halt state;)

Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol;)

Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here;)

+ suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).

This sequence is computable. On the other hand, the busy beaver numbers are noncomputable, found only by examining each of the many n-state Turing machine programs' halting. - Michael Joseph Halm, Apr 29 2003

From Daniel Forgues, Jun 06 2011: (Start)

RE: Busy beaver halting Turing machines:

H in H_(n, k) is a halting* Turing machine with n states and k symbols;

* (on a blank tape, all 0's, as input)

sigma(H) is the number of non-blank symbols left on the tape by H;

s(H) is the number of steps (or shifts in our case) taken by H;

Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}

S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}

Cf. A028444 for Sigma(n, 2), A060843 for S(n, 2). (End)

This sequence also counts machines with unreachable states, and all (up to (n-1)!) permutations of non-start states, which don't affect behavior. In contrast, A107668 only counts state graphs reaching all n states in canonical order. - John Tromp, Oct 17 2024

This sequence is noncomputable, because it could be used to solve the halting problem. In fact, it is of the same degree of difficulty as the halting problem. - David Diamondstone (skeptical.scientist(AT)gmail.com), Dec 28 2007

Sizes of terms are defined as in Binary Lambda Calculus (see Lambda encoding link) by size(lambda M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda.

a(34), a(35) and a(36) correspond to Church numerals 2^2^2^2, 3^3^3, and 2^2^2^3, where numeral n has size 5*n+6.

a(38) > 10^19729, corresponding to Church numeral 2^2^2^2^2.

Only a finite number of entries can be known, as the function is uncomputable.

Quoting from Chaitin's paper below: "to information theorists it is clear that the correct measure is bits, not states [...] to deal with Sigma(number of bits) one would need a model of a binary computer as simple and compelling as the Turing machine model, and no obvious natural choice is at hand."

a(49) > Graham's number, as shown in program melo.lam in the links. - John Tromp, Dec 04 2023

a(111) > f_{ε_0+1}(4), as shown in program E00.lam in the links. - John Tromp, Aug 24 2024

a(404) > f_{PTO(Z_2)+1}(4), as shown in 1st Stackexchange link. - John Tromp, Dec 17 2024

a(1850) > Loader's number, as shown in 2nd Stackexchange link. - John Tromp, Dec 17 2024

A universal form of this Busy Beaver, using the binary input feature of Binary Lambda Calculus, is given in sequence A361211. - John Tromp, May 24 2023

An oracle form of this Busy Beaver is given in sequence A385712. - John Tromp, Jul 23 2025

Given a list of n move instructions (up, right, down, left), the snake starts at the origin and moves according to the instructions, in order. If an instruction tells it to move to a square that has already been visited, the snake skips that instruction. After it has followed (or skipped) the last instruction in the list, it starts again with the first one. The snake is either finite (if it gets stuck at some point) or infinite (if it can go on forever). a(n) is the maximum number of squares visited by a finite snake. For n <= 4, all snakes are infinite. - Pontus von Brömssen, May 08 2022

Let f(a, b) = (3*a / 2, b + 2) if a is even, otherwise ((3*a - 1)/2, b - 1). The Busy Beaver challenge is to find natural numbers n and v, such that after n iterations, starting with f(8, 0), the result is (v, -1). The sequence lists the values of b in the iteration, the values of a are in A386792.

It is strongly suspected that the iteration does not halt according to the random-walk heuristic. Since Antihydra is derived from the transition rules of a 6-state, 2-symbol Turing machine, proving its divergence is equivalent to proving that this machine does not halt. Demonstrating the divergence of Antihydra is likely a necessary step in establishing a lower bound for BB(6), as this Turing machine appears to outrun all known halting 6-state machines.

Let f(a, b) = (3*a / 2, b + 2) if a is even, otherwise ((3*a - 1)/2, b - 1). The Busy Beaver challenge is to find natural numbers n and v, such that after n iterations, starting with f(8, 0), the result is (v, -1).

We consider the sequence to be defined for all values of n, regardless of whether 'b' ever takes the value -1 or not. The sequence records the values of 'a' in this iteration. See A385902 for the values of 'b'.

We start with initially empty registers and include exactly one Halt instruction. Analogous to the Busy Beaver function, Sigma, for Turing Machines.

n<=5 are proved. 5