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

  • $\begingroup$ How many values do you know for sure? $\endgroup$
    – Ville Salo
    Mar 26 at 6:04
  • $\begingroup$ @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. $\endgroup$
    – user76284
    Mar 26 at 22:42
  • $\begingroup$ Ok, they are correct for $n \leq 3$ at least. $\endgroup$
    – Ville Salo
    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<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.


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.