cp's OEIS Frontend

Expanded definition from Daniel Forgues: Busy Beaver sequence, or Rado's Sigma function: maximum number of 1s that an n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) halting Turing machine can print on an initially blank tape (all 0's) before halting.

States q and q+ in set Q_n of n distinct states (plus the Halt state), tape symbols s and s+ in set S = {0, 1}, 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).

The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1's) which a halting Turing Machine H with n internal states, 2 symbols, and a two-way infinite tape can produce onto an initially blank tape (all 0's) and then halt. The function S(n) = S(n, 2) (A060843) denotes the maximal number of steps (thus shifts, since direction NONE is excluded) which a halting machine H can take (not necessarily the same Turing machine producing a maximum number of 1's and need not even produce many tape marks). For all n, S(n) >= Sigma(n).

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

Rado's Sigma function grows faster than any computable function and is thus noncomputable.

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

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 Sigma(n) = Sigma(n, 2) since a 2-symbol BB-class Turing machine is assumed.

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

From Jianing Song, Nov 12 2023: (Start)

We have a(2*n) > H_n(3,3) = 3 "up-arrow"(n-2) 3, where H_n is the n-th hyperoperator, and "up-arrow" is Knuth up-arrow notation (see the Wikipedia link). This means that a(12) > 3^^^^3 = g(1), where g(1) is the starting value in the sequence that defines Graham's number = g(64).

Note that there is an (n_0)-state binary Turing machine (and hence an n-state one for every n >= n_0) which halts if and only if ZFC is inconsistent, so a(n_0) (and hence a(n) for every n >= n_0) is independent of ZFC, which means that a(n_0) evaluates differently in different models of ZFC; see the section "Non-computability" of the Wikipedia link and the Math Stack Exchange. The minimum such n_0 is not exceeding 745. (End)

a(6) >= 2^^(2^^(2^^10)). - Brian Galebach, Jul 10 2025

Shift right of column 1 of triangle A107670, which is the matrix square of triangle A107667.

The o.g.f. A(x) = Sum_{m >= 0} a(m)*x^m is such that, for each integer n > 0, the coefficient of x^n in the expansion of exp(n^2*x)*(1 - x*A(x)) is equal to 0.

Given the o.g.f. A(x), the o.g.f. of A304322 equals 1/(1 - x*A(x)).

Also, a(n) is the number of 2-symbol Turing Machine state graphs in which n states are reached in canonical order. A canonical TM state graph lists for each state 1..n, and each of 2 symbols 0,1 in lexicographic order, a next state that is either the halt state, an already listed state, or the least unlisted state, as in the Haskell program below. Multiplied by 4^(2*n), this gives a much smaller number of TMs to be considered for the Busy Beaver function than given by A052200. - John Tromp, Oct 15 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

If BB(n) = A060843(n), then a(BB(n)) = n and that is the last occurrence of n in this sequence. a(n) will not become monotonic; if it did, we could compute BB(n), since a(n) is computable. a(n) diverges properly, but does so very slowly. The terms with values 1,2,3 were computed by exhaustive search. The terms with value 4 were inferred from knowing that they are greater than 3 and from the observation that for all n, a(n+1) <= a(n) + 1 (an easy construction). Using exhaustive search, may be able to extend the sequence to (most of) the terms up to and a bit beyond a(107) = 4, but going much further would likely require a more sophisticated method (see A052200).

If BB(n) = A060843(n), then a(BB(n)) = n and that is the last occurrence of n in this sequence. a(n) will not become monotonic; if it did, we could compute BB(n), since a(n) is computable. a(n) diverges properly, but does so very slowly. a(n+1) <= a(n) + 1 (an easy construction). - Martin Fuller, Feb 14 2007

The prototypical example of a noncomputable sequence.

A Turing machine is halt-free if none of its instructions lead to the halt state.

This sequence is strictly less than A052200(n) for all n > 0, since halt-free n-state machines are a strict subset of all n-state machines.

Solutions to the so-called "Beeping Busy Beaver" problem will almost certainly be halt-free programs.

For n > 1, a(n) is the absolute value of the determinant of a Hadamard matrix of size 4(n-1). This is apparent from the fact that HH^T = nI_n implies det(H)^2 = det(nI_n) = n^n, so det(H) = +- n^(n/2) and plugging in 4n yields a(n). - Nour Abouyoussef, Jun 25 2025