6
$\begingroup$

The Busy Beaver problem is to find the largest number of non-blank characters that are printed by a terminating Turing machine of no more than a given size on the blank input.

The usual Busy Beaver machines run on a blank tape that is infinite in both directions.

Is there any research (and/or experiments) on Busy Beavers machines that run on a semi-infinite tape? (the Turing machine's head is initially positioned on the first cell of the tape)

With a semi-infinite tape we must also consider what happens if the head tries to cross the boundary at the beginning of the tape; the two approaches:

  • the computation halts
  • the head "bounces" to cell 2

probably lead to different results.

$\endgroup$
3
$\begingroup$

We look to the first approach in this answer.

Let us denote this new function by $\Sigma_{\mathrm{semi}}(n)$.

Also, call the function of the second approach $\Sigma_{\mathrm{bounce}}(n)$.

Also, denote the original Busy Beaver function by $\Sigma(n)$.

First note that $\Sigma(n) \geq \Sigma_{\mathrm{semi}}(n)$ and $\Sigma_{\mathrm{bounce}}(n) \geq \Sigma_{\mathrm{semi}}(n)$, since every program that works for semi also works for bounce and the original version.

Uncomputability of $\Sigma_{\mathrm{semi}}(n)$

In this part of the answer, I'll prove that $\Sigma_{\mathrm{semi}}(14n+3)>\Sigma(n)$, therefore it is uncomputable. (If it were computable, then $\Sigma(n)$ would be upper-bounded by a computable function, contradiction.)

This implies that $\Sigma_{\mathrm{bounce}}(n)$ is also uncomputable.

Definitions

Number all cells on the tape, starting with 1 for the first cell.

We call the number of the cell the index.

Group every pair of consecutive cells such that the first cell in the pair has an on the tape into one macro cell, so the tape looks like

(1,2)(3,4)(5,6)(7,8)....

Constructing a new machine

Consider the Busy Beaver with $n$ states that leaves $\Sigma(n)$ ones on the tape with states $B_1, B_2, B_3, \cdots B_n$. We leave the new symbol and direction intact, but instead of going to a new state $B_i$, we go to $B_{i,\mathrm{left}}$ if the direction is left, and to $B_{i,\mathrm{right}}$ if the direction is right. (Exception: If the new state is $\mathrm{HALT}$, then it remains $\mathrm{HALT}$.) We construct a machine that needs additional states for each state $B_k$.

The idea of this machine is that all cells with odd index contain exactly two ones: One that is further to the right than any one in a cell with an even index, and one that is at the cell with index 1. If we read the leftmost one, we know that we are on the edge of the tape and then we move the whole tape with even index two indices to the right. Because of the rightmost one we know up to where we should move the tape. So every cell with an even index will be used for executing a normal Turing machine. The cells with odd index will be used to ensure the Turing Machine doesn't run of the tape.

Anyway, here are the states:

  • $B_{k,\mathrm{right}}$ (odd index): This has the following ruleset:

    • If it reads a zero, then we go to the right, keep the symbol a zero and go to state $B_k$.
    • If it reads a one, then we go to the right, make the symbol a zero and go to state $B_{k,1}$.
  • $B_{k,1}$ (even index): This has the following ruleset:

    • It doesn't change the symbol it reads and goes to the right and to state $B_{k,2}$.
  • $B_{k,2}$ (odd index): This has the following ruleset:

    • If it reads a zero, it changes this into an one and goes to the left and to state $B_{k}$.
    • It is not possible to read a one in this state. When the machine enters this state, it is on a cell with an odd index. However, we removed a one in state $B_{k,\mathrm{right}}$ two steps before this, so only the leftmost one remains and we are certainly more to the right than that one.
  • $B_{k,\mathrm{left}}$ (odd index): This has the following ruleset:

    • If it reads a zero, then we go to the left, keep the symbol a zero and go to state $B_k$.
    • If it reads a one, then we go to the right, keep the symbol a one and go to state $B_{k,3}$.
  • $B_{k,3}$ (even index): This has the following ruleset:

    • If it reads a zero, it writes a zero and goes to the right and to state $B_{k,4}$
    • If it reads a one, it writes a zero and goes to the right and to state $B_{k,7}$
  • $B_{k,4}$ (odd index): This has the following ruleset:

    • If it reads a zero, it writes a zero and goes to the right and to state $B_{k,3}$
    • If it reads a one, it writes a zero and goes to the right and to state $B_{k,5}$
  • $B_{k,5}$ (even index): This has the following ruleset:

    • If it reads a zero, it writes a zero and goes to the right and to state $B_{k,9}$
    • It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.
  • $B_{k,6}$ (even index): This has the following ruleset:

    • If it reads a zero, it writes an one and goes to the right and to state $B_{k,4}$
    • If it reads a one, it writes an one and goes to the right and to state $B_{k,7}$
  • $B_{k,7}$ (odd index): This has the following ruleset:

    • If it reads a zero, it writes a zero and goes to the right and to state $B_{k,6}$
    • If it reads a one, it writes a zero and goes to the right and to state $B_{k,8}$
  • $B_{k,8}$ (even index): This has the following ruleset:

    • If it reads a zero, it writes a one and goes to the right and to state $B_{k,9}$
    • It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.
  • $B_{k,9}$ (odd index): This has the following ruleset:

    • If it reads a zero, it writes a one and goes to the left and to state $B_{k,10}$
    • It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.
  • $B_{k,10}$ (even index): This has the following ruleset:

    • It doesn't change the symbol it reads and goes to the left and to state $B_{k,11}$.
  • $B_{k,11}$ (odd index): This has the following ruleset:
    • If it reads a zero, it leaves a zero, goes to the left and to state $B_{k,10}$.
    • If it reads a one, than this is the leftmost one. It leaves this one unchanged, moves to the right and to state $B_k$.

If this helps, here are informal explanations of what the states $B_{k,\mathrm{something}}$ do:

  • $B_{k,\mathrm{right}}$: Bring the head to the cell with the even index and notice that the rightmost one on the odd index needs to be moved.
  • $B_{k,1}$: Bring the head to the cell with the odd index.
  • $B_{k,2}$: Write the new rightmost one.
  • $B_{k,\mathrm{left}}$: Bring the head to the cell with the even index and notice that the tape needs to be moved.
  • $B_{k,3}$: Write moved zeroes on cells with even index.
  • $B_{k,4}$: Move the head to even index and notice the rightmost one.
  • $B_{k,5}$: Write moved zeroes on cells with even index after the rightmost one was noticed.
  • $B_{k,6}$: Write moved ones on cells with even index.
  • $B_{k,7}$: Move the head to even index and notice the rightmost one.
  • $B_{k,8}$: Write moved one on cells with even index after the rightmost one was noticed.
  • $B_{k,9}$: Write a new rightmost one.
  • $B_{k,10}$: Move to the position the head should be.
  • $B_{k,11}$: Move to the position the head should be and notice the leftmost one. Note that the original position where the head should have gone is one to the left of the end of the tape, so it is not one to the right of the tape.

Initial setup for the new machine

Before we will run this machine, we will put an 1 in cell 1 and cell 3, and move the head of the machine to cell 2. So the tape looks like

(1,_)(1,_)(_,_)(_,_)....

This can be done using three states:

  • State 1: It reads a zero. It writes an one. It goes to the right. It goes to state 2.
  • State 2: It reads a zero. It writes a zero. It goes to the right. It goes to state 3.
  • State 3: It reads a zero. It writes an one. It goes to the left. It goes to state $B_1$, as defined above.

Conclusion

We created a new machine with 14 states per original state and 3 states for the initial setup that simulates $\Sigma(n)$ on a semi-infinite tape. Therefore $$\Sigma_{\mathrm{semi}}(14n+3) > \Sigma(n)$$

Note that I didn't necessarily tried to optimize those constants, since I just wanted to show uncomputability.

$\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.