Busy Beaver machines on semi-infinite tape

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.

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 t

StackExchange Computer Science Q#57333, answer score: 3