Busy beaver sequence for a simple tag-like system

Question

This question arose in the context of tag-like systems, specifically Bitwise Cyclic Tag (BCT). Consider the following discrete dynamical system:

Let $\mathbb{B} = \{\mathtt{0}, \mathtt{1}\}$. Let our phase space be $(\mathbb{B}^*)^2$, i.e. the set of all pairs of binary strings. The first string is called the program. The second string is called the memory.

Let our evolution function be $f : (\mathbb{B}^+)^2 \rightarrow (\mathbb{B}^*)^2$ where

$$ f(\mathsf{a} x, \mathsf{b} y) = \begin{cases} (x \mathsf{a}, y) & \mathsf{a} = \mathsf{b} \\ (x \mathsf{a}, \mathsf{b} y \mathsf{b}) & \text{otherwise} \end{cases} $$

That is: If the program-bit matches the memory-bit, we pop the latter. Otherwise, we append the latter to the back of the memory. In either case, we cycle the program. Note that both strings must be nonempty.

Let $T : (\mathbb{B}^*)^2 \rightarrow \mathbb{N} \cup \{\infty\}$ yield the runtime of a configuration, i.e.

$$T(\omega) = \inf \{t \in \mathbb{N} \mid f^t(\omega) \not\in \operatorname{dom} f\}$$

In analogue with the busy beaver function for Turing machines, let $B : \mathbb{N} \rightarrow \mathbb{N}$ yield the busy beaver number for a given program length, i.e.

$$ B(n) = \max (\{ T(x, \mathtt{01}) \mid x \in \mathbb{B}^n \} \cap \mathbb{N}) $$

where we initialize the memory with $\mathtt{01}$. The first 20 busy beaver numbers (with a 1000-step runtime limit) are as follows:

    0    0
    1    0
    2    4
    3    2
    4   12
    5    6
    6   18
    7   24
    8   34
    9   32
   10   72
   11   40
   12  122
   13   60
   14  184
   15   96
   16  276
   17  126
   18  468
   19  144

Is there a recursive upper bound on $B$? That is, can we bound the runtime of a program based on its length? If so, what can we say about the asymptotics (or other interesting properties) of $B$?

Answer 1

There is a recursive and even polynomial upper bound.

In the following I will denote the program string by $p$ and its length by $n$.

First notice that the memory will always be of the form $0^i$, $0^i 1^j$ or $0^i 1^j 0^k$ (or symmetrically $1^i$, $1^i 0^j$ or $1^i 0^j 1^k$) for some $i,j,k>0$. This is a simple induction from the base case $01$, because as long as the evolution function sees a bit $0$ in the memory, it can only add copies of $0$ to the end or remove copies of $0$ from the beginning (and similarly for the bit $1$).

Next notice that if the memory ever becomes of the form $0^i$ or $1^i$, then after running the program for $n$ more steps we see whether the memory string starts decreasing or increasing.

Finally we claim that before the memory possibly becomes $0^i$ or $1^i$, if the memory string ever contains $n$ or more consecutive zeroes or ones, the system necessarily runs forever. To see this, assume without loss of generality that at some point the memory contains at least $n$ consecutive zeroes (together with some ones). Therefore at some point the memory is of the form $0^i 1^j$ with $i<n$, and after reading the $i$ zeroes in the beginning at least $n$ zeroes will have been appended to the end.

If $p$ contains less that $n/2$ ones (and therefore more than $n/2$ zeroes), then all the $i<n$ zeroes will be removed from the beginning before $p$ cycles two full rounds. These two rounds of $p$ contain less than $n$ ones, so less than $n$ zeroes get appended to the end, a contradiction. Therefore $p$ necessarily contains at least $n/2$ ones. Now, whenever we reach $n$ consecutive zeroes, to remove all of them we need to cycle $p$ at least two full rounds because $p$ contains at most $n/2$ zeroes. During these two rounds at least $n$ new zeroes are appended to the end because $p$ contains at least $n/2$ ones, and the system never stops.

In a halting system the number of possible memory contents is $\mathcal{O}(n^3)$ and the program can cycle to $n$ different strings, so the system halts in $\mathcal{O}(n^4)$ steps.