BB(n,1)
BB(n,1) is the Busy Beaver problem for n-state, 1-symbol TMs. It is trivial that Σ(n,1) = 0, as 1-symbol TMs cannot print any non-zero symbols. As any transition back to an already visited state will put the machine in an infinite loop, the most effective halting strategy is to pass through the states one by one, halting only in the final state, thus making BB(n,1) = n.
Champions
By translating state names into numbers (such that A=1, B=2, etc.), the 1-symbol champions can be defined in the following way:
- 0R[1,a] = 0RZ
- 0R[n,a] = 0Ra_0R[n-1,a+1] for n>1
For the n-state champion, start with 0R[n,2].