Expanded definition from Daniel Forgues: Busy Beaver sequence, or Rado's Sigma function: maximum number of 1s that an nstate, 2symbol, d+ in {LEFT, RIGHT}, 5tuple (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 twoway 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 5state 2symbol halting Turing machines can compute Collatzlike 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 0506 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 nonblank 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 2symbol BBclass Turing machine is assumed.
For all n, S(n, k) >= Sigma(n, k), k >= 2. (End)
