<p>Take an $n$-state Turing machine $M$ which outputs $k$ one symbols. Define the new Turing machine $M&#39;$ with $n+1$ states as follows. Every transition in $M$ to the ACCEPT state instead goes into a new state $q&#39;$. The state $q&#39;$ 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&#39;$.</p>

<p>As machine $M$ halts, so does machine $M&#39;$. Furthermore, machine $M&#39;$ always puts one $k+1$ ONES onto the tape.</p>

<p>So $BB(n+1) \geq k+1 &gt; k = BB(n)$</p>

CC BY-SA 3.0
2012-01-07T17:21:28.027Z
2012-01-07T17:21:28.027Z
David Harris
<p>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 <strong>score</strong>) by a standard n-state, 2-symbol (0 and 1) Turing machine before halt, starting with an all-zero tape. </p>

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

<p>The claim is true if we define the busy beaver by BB'(n)= maximum number of <strong>shifts</strong> 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.) </p>

<p>Can we show that the strict inequality holds too if we measure by <strong>scores</strong>? </p>

<hr>

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

<computability><turing-machines>
Is every busy beaver strictly monotonic asymptotically?
user7862
# Is every busy beaver strictly monotonic asymptotically?

(Asked by: username_0 on 2012-01-07)

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?

**Tags:** computability, turing-machines

---

## 1 answers

### Answer by username_1 on 2012-01-07. Score: 16 | Accepted answer

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)$


---

