|
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 (1s) 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 1s and needs 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.
[Daniel Forgues, June 5-6 2011] (Start)
H in H_(n, k) is a halting* Turing machine with n states and k symbols;
* (on a blank tape (all 0s) 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)
| 