| 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 (hierogamous(AT)lycos.com), Apr 29 2003
From Daniel Forgues, June 6 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 0s, 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)
| 