# Busy beaver sequence for a simple tag-like system

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

• How many values do you know for sure? Mar 26 at 6:04
• @VilleSalo I only have the lower bounds given by the runtime-bounded results. I could increase the runtime-bound to see if any of them increase, though they currently seem to be relatively far from the runtime-bound. Exact determination would, of course, require an exhaustive case-by-case analysis of the nonterminating programs. Mar 26 at 22:42
• Ok, they are correct for $n \leq 3$ at least. Mar 27 at 4:29

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, 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 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.