4
$\begingroup$

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?

$\endgroup$
16
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.