Is every busy beaver strictly monotonic asymptotically?

Question

To be specific, let me first define the busy beaver function BB(n)= maximum number of 1's that can be printed on the tape (i.e., the maximum score) by a standard n-state, 2-symbol (0 and 1) Turing machine before halt, starting with an all-zero tape.

My first question maybe trivial: is it true that BB(n+1)>BB(n) for all n?

The claim is true if we define the busy beaver by BB'(n)= maximum number of shifts made by the machine before halt. (This is because we can always keep everything else the same, and change the last shift made by BB'(n), say $\{ 0{q}_{i}1RH\}$, to $\{ 0{q}_{i}1R{q}_{n+1}\}$ and $\{1{q}_{n+1}1RH\}$ to arrive at an (n+1)-state turing machine which has exactly one more shift than BB'(n) before halt.)

Can we show that the strict inequality holds too if we measure by scores?

---

What about the general case? Is every busy beaver strictly monotonic, for large enough n?

Answer 1

Take an $n$-state Turing machine $M$ which outputs $k$ one symbols. Define the new Turing machine $M'$ with $n+1$ states as follows. Every transition in $M$ to the ACCEPT state instead goes into a new state $q'$. The state $q'$ has the following behavior. If the head currently contains a ZERO, we overwrite with a ONE and ACCEPT. If the head currently contains a ONE, we shift to the right and remain in state $q'$.

As machine $M$ halts, so does machine $M'$. Furthermore, machine $M'$ always puts one $k+1$ ONES onto the tape.

So $BB(n+1) \geq k+1 > k = BB(n)$