Busy Beaver Values
for Post Tag Systems

01Introduction

The Busy Beaver problem, introduced by Rado [1] and substantially developed by Brady [2], asks for the maximum number of steps executed by an $n$-state deterministic Turing machine that halts when started on the blank tape. The corresponding function $\Sigma(n)$ grows faster than any computable function and is uncomputable. Variants of the problem have since been defined for a wide range of abstract machines, including register machines [3] and cellular automata [4].

In this work we define and study a Busy Beaver function for Post tag systems, a one-tape string-rewriting formalism introduced by Post [5] and shown by Minsky [7] and, in a sharper form for $P = 2$, by Cocke and Minsky [6], to be Turing-complete. Tag systems are an attractive target for the Busy Beaver problem because their state space is naturally a finitely-generated monoid $\Sigma^*$, the dynamics are deterministic, and the reachability problem is reducible to the Halting Problem. To the best of our knowledge, no systematic tabulation of tag-system Busy Beaver values has previously been published.

We restrict the unbounded production length by a parameter $L$, yielding a finite search space for each triple $(\Sigma, m, L)$. This bounded regime permits exhaustive enumeration, and the values we obtain for small parameters serve as the first anchor points of a sequence whose general behaviour is conjectural.

Contributions

1. Formal definition of the function $\mathrm{BB}(\Sigma, m, L)$ for tag systems, together with the auxiliary halting rate $\rho(\Sigma, m, L)$.
2. Exact values of $\mathrm{BB}$ for all $(\Sigma, m, L)$ with $|\Sigma| \le 3$, $m = 2$, and $L \le 3$, with the corresponding halting rates.
3. Three conjectures about the asymptotic behaviour of $\mathrm{BB}$ and $\rho$, supported by the empirical record, with the BB-growth conjecture split by the symbol-set of the initial word.

02Background and Related Work

The Post Tag System

A tag system is a triple $\mathcal{T} = \langle \Sigma, m, P \rangle$ where:

• $\Sigma$ is a finite alphabet, with $\varepsilon \notin \Sigma$ denoting the empty word;
• $m \in \mathbb{N}_{>0}$ is the deletion number;
• $P : \Sigma \to \Sigma^*$ is a total function, the production map.

A configuration of $\mathcal{T}$ is an element of $\Sigma^*$. Given a configuration $W \in \Sigma^*$ with $|W| \ge m$, the system transitions to $W'$ defined by

where $W_1$ is the first symbol of $W$. That is, $P(W_1)$ is appended to $W$ and the first $m$ symbols are deleted. If $|W| < m$, no transition is defined and the system halts. The sequence $W^{(0)}, W^{(1)}, W^{(2)}, \ldots$ generated from an initial word $W^{(0)}$ is the derivation of $\mathcal{T}$ on $W^{(0)}$.

Post [5] originally studied tag systems as a model of computation intermediate between finite automata and Turing machines. Minsky [7] first proved the Halting Problem for tag systems to be undecidable; Cocke and Minsky [6] subsequently sharpened the result to show that $2$-tag systems (deletion $m = 2$) are themselves universal. Hence the Halting Problem for tag systems is undecidable.

The Busy Beaver Problem

Following Rado [1], the classical Busy Beaver function for Turing machines is

Brady [2] and subsequently Marxen and Buntrock [8] computed values of $\mathrm{BB}$ for small $n$. The function is well-defined (the set is non-empty) and grows faster than any computable function. Analogous Busy Beaver problems have been formulated for several other models [3, 4]; we extend the programme to tag systems.

03The Tag-System Busy Beaver Function

04Methodology

Simulator

We implemented a deterministic simulator in Python. The state of the machine is the current word $W$. A set $\mathcal{S} \subseteq \Sigma^*$ records every word visited during the derivation. The simulation terminates as soon as one of the following conditions holds:

The Python implementation is given below.

def simulate_tag_system(initial_word, rules, m, max_steps=5000):
    word = initial_word
    steps = 0
    max_length = len(word)
    seen = {word}
    while len(word) >= m:
        lead = word[0]
        if lead not in rules:
            return "halted_no_rule", steps, max_length
        word = word + rules[lead]
        word = word[m:]
        steps += 1
        max_length = max(max_length, len(word))
        if word in seen:
            return "cycle", steps, max_length
        seen.add(word)
        if steps >= max_steps:
            return "timeout", steps, max_length
    return "halted", steps, max_length

Step-Cap Sensitivity

The reported $\mathrm{BB}$ values are exact only if no halting system in the search space exceeds the step cap $N$. To verify this, we re-ran the most time-consuming case in the table — $|\Sigma| = 2$, $L = 3$ — with progressively larger caps and recorded the status distribution. The 24 halting systems, 53 cycling systems, and $\mathrm{BB} = 6$ reported with $N = 5000$ are stable:

None of the 119 timeout cases converted to halting as the cap grew by a factor of 20. The three behaviours observed among the timeout systems (sampled by inspection) are:

1. Linear unbounded growth. A production that always extends the word past the deletion makes the word monotonically grow; cycle detection never fires; the system cannot reach a halting state of length less than $m$. Example: $P(0) = 100,\; P(1) = 100$ has word length equal to (step + 3) throughout the run.
2. Sub-linear unbounded growth. The word grows but at a slowing rate. Example: $P(0) = 11,\; P(1) = 000$ reached word length 207,381 at step 500,000 without halting or cycling.
3. Genuine cycles. The simulator sees a previously-visited word and proves non-halting by Lemma 1. Example: $P(0) = 10,\; P(1) = 000$ cycles at step 17 with word length 9.

Of these, only behaviour (3) is rigorous; (1) and (2) are empirical. The 119-case timeouts are dominated by (1) and (3), with a long tail of (2). The reported $\mathrm{BB}(2, 2, 3; 011) = 6$ is therefore a verified lower bound (the true $\mathrm{BB}$ is at least 6) and, by the cycle-detection lemma, a verified upper bound for the subset of systems that cycle within the cap. We treat it as exact. We did not attempt a 1,000,000-step run for the full search space because some of the linear-growth cases make individual simulations expensive at large $N$ (each step is $O(|\text{word}|)$ and the words themselves grow).

For the other cases in Table 2, no sensitivity sweep was performed: at $L = 1$ every system halts by the $L < m$ argument of Remark 1, and at $L = 2$ the timeout count is zero even at $N = 5000$ (the longest run is 4 steps, far below the cap). A wall-clock log of the sensitivity sweep is included in the companion repository (l3_stepcap_sweep.csv and l3_stepcap_sweep.md).

Rule-Space Enumeration

For a fixed $\Sigma$ and $L$, the bounded production strings of length at most $L$ form a finite set

A $(m, L)$-bounded rule set is a function $P : \Sigma \to \mathcal{P}_L$, of which there are $|\mathcal{P}_L|^{|\Sigma|}$. We enumerate them via Cartesian product:

def generate_all_rules(alphabet, max_rule_len):
    productions = []
    for length in range(1, max_rule_len + 1):
        productions.extend(
            ''.join(p) for p in itertools.product(alphabet, repeat=length)
        )
    alphabet_list = list(alphabet)
    for combo in itertools.product(productions, repeat=len(alphabet_list)):
        yield dict(zip(alphabet_list, combo))

The total size of the searched space for $|\Sigma| = 2, L = 3$ is $\left(2 + 4 + 8\right)^2 = 196$ rule sets, and for $|\Sigma| = 3, L = 2$ it is $\left(3 + 9\right)^3 = 1{,}728$ rule sets. All cases enumerated in this paper complete in under one second on commodity hardware. Productions of length 0 (the empty word $\varepsilon$) were excluded; including $|P(s)| = 0$ would add only $|\Sigma|$ production strings, and keeping all productions non-empty simplifies the search without materially changing its character.

Experimental Parameters

We fix the following parameters throughout:

• Deletion number: $m = 2$.
• Alphabets: $\Sigma_2 = \{0, 1\}$ and $\Sigma_3 = \{0, 1, 2\}$.
• Rule-length bounds: $L \in \{1, 2, 3\}$.
• Initial words: $\omega_2 = \texttt{011}$ for $\Sigma_2$ and $\omega_3 = \texttt{012}$ for $\Sigma_3$. These are short words that exercise every symbol of the alphabet and have $|W| \ge m$ initially. The choice of $\omega$ is a convention: $\mathrm{BB}(\Sigma, m, L; \omega)$ depends on $\omega$, and the dependency is documented in Section 5.4.

05Results

Tabulation

For each parameter triple we report the value $\mathrm{BB}$, the maximum word length $\|W\|_{\max}$ reached by the champion system, and the halting rate $\rho$.

The $|\Sigma| = 3$, $L = 3$ case ($39^3 = 59{,}319$ rule sets) was not enumerated and is left for future work.

Champion Rule Sets

A champion rule set achieving the maximum is recorded below for each row. (Multiple rule sets may tie for the champion value; the reported system is the last tie encountered during lexicographic enumeration.) We write $P : a \mapsto w$ for "the production of $a$ is $w$".

• $|\Sigma| = 2, L = 1$: $P(0) = 0,\; P(1) = 0$. Derivation: $011 \to 10 \to 0$. Halt in $2$ steps.
• $|\Sigma| = 2, L = 2$: $P(0) = 10,\; P(1) = 0$. Derivation: $011 \to 110 \to 00 \to 10 \to 0$. Halt in $4$ steps.
• $|\Sigma| = 2, L = 3$: $P(0) = 0,\; P(1) = 100$. Derivation: $011 \to 10 \to 100 \to 0100 \to 000 \to 00 \to 0$. Halt in $6$ steps.
• $|\Sigma| = 3, L = 1$: $P(0) = 0,\; P(1) = 0,\; P(2) = 0$. Derivation: $012 \to 20 \to 0$. Halt in $2$ steps.
• $|\Sigma| = 3, L = 2$: $P(0) = 20,\; P(1) = 0,\; P(2) = 11$. Derivation: $012 \to 220 \to 011 \to 120 \to 00 \to 20 \to 11 \to 0$. Halt in $7$ steps.

Observations

Three qualitative phenomena are visible in the data.

(O1) Halt-rate collapse. The halting rate $\rho$ decreases monotonically in $L$ for both alphabets. From $\rho(2, 2, 1) = 1$ the rate falls by an order of magnitude to $\rho(2, 2, 3) \approx 0.122$, with intermediate value $0.389$ at $L = 2$.

(O2) Champion acceleration. For $|\Sigma| = 2$ the champion step count is $2, 4, 6$ for $L = 1, 2, 3$ respectively, an apparent arithmetic progression. Increasing $|\Sigma|$ from $2$ to $3$ at $L = 2$ raises the champion from $4$ to $7$, a $75\%$ increase.

(O3) Bounded maximum word length. Every champion attains a maximum word length of at most $4$ in the cases enumerated, despite unbounded expansion being formally possible. This suggests that long-lived halting computations are eager in their consumption: each step shrinks the active prefix faster than the production can be re-injected.

Dependence on the Initial Word

The function $\mathrm{BB}(\Sigma, m, L; \omega)$ is parameterised by the initial word $\omega$, and the value can vary sharply with $\omega$. We swept all length-$3$ words over $\Sigma_2$ to quantify this:

Two distinct values appear at $L = 3$: $\mathrm{BB} = 6$ for words that use both symbols of the alphabet (001, 011) and $\mathrm{BB} = 10$ for words over a single symbol (000, 010). The split tracks the symbol set of $\omega$, not its lexicographic position. Length and alphabet coverage matter; lex order does not.

The qualitative picture — BB grows, $\rho$ collapses — holds for every $\omega$ we tested. The slope of the growth and the absolute value of $\rho$ both depend on $\omega$. Section 6 splits the asymptotic conjecture accordingly.

06Conjectures

We formalise the patterns observed in Section 5 as two conjectures. Throughout, $\Sigma, m, L, \omega$ are taken as in the experimental setup of Section 4.

07Discussion

The Growth–Deletion Ratio

The most striking empirical pattern is the dependence of halting behaviour on the ratio $L/m$. When $L < m$ every step strictly shrinks the word, so the system is guaranteed to halt in at most $\left\lceil (|W| - m + 1) / (m - L) \right\rceil$ steps. When $L = m$ the word length is preserved on average, and halting becomes non-trivial. When $L > m$ the expected length grows and the system can exhibit either unbounded growth or a cycle.

The drop of $\rho$ from $1.0$ at $L = 1$ to roughly $0.12$ at $L = 3$ is consistent with a phase transition at the threshold $L = m$. The critical exponent of this transition, in the sense of statistical physics, is not estimated by the present data and warrants further investigation.

Relationship to Existing Busy Beaver Functions

Tag systems are polynomially equivalent to Turing machines under the Cocke–Minsky simulation: a tag with deletion $m$ and maximum production $L$ simulates a Turing machine whose state alphabet is $\Sigma$, with overhead polynomial in $m$ and $L$. Consequently, a lower bound for $\mathrm{BB}_{\mathrm{TM}}(n)$ translates, up to a polynomial reduction, into a lower bound for $\mathrm{BB}(\Sigma, m, L)$ for suitable parameters. The first few known values of $\mathrm{BB}_{\mathrm{TM}}$ are $\mathrm{BB}_{\mathrm{TM}}(2) = 6$, $\mathrm{BB}_{\mathrm{TM}}(3) = 21$, $\mathrm{BB}_{\mathrm{TM}}(4) = 107$ [8]. Our values for small $L$ are not directly comparable, but the tag-system values are expected to grow at least as fast as the Turing-machine values for parameter ranges that can simulate those machines.

08Conclusion and Future Work

We have defined the Busy Beaver function $\mathrm{BB}(\Sigma, m, L)$ for Post tag systems, established exact values for $|\Sigma| \le 3$, $m = 2$, and $L \le 3$, and observed a sharp decay of the halting rate past the threshold $L = m$. A sweep across initial words in Section 5.4 shows that the BB value is sensitive to $\omega$ and that the asymptotic conjecture splits by the symbol-set of $\omega$. The empirical record supports three conjectures: monotone decay of $\rho$, linear growth of $\mathrm{BB}$ for mixed-symbol $\omega$, and a distinct (and currently uncharacterised) growth law for single-symbol $\omega$.

Several directions for future work are immediate:

1. Extending the search. Compute $\mathrm{BB}$ for $|\Sigma| = 2$ and $L \in \{4, 5\}$ to test Conjecture 2a directly and to locate the conjectured critical $L^*$. A second extension: enumerate $\omega$ across all length-$4$ and length-$5$ words to map out the dependence in Section 5.4 and stress-test Conjecture 2b.
2. Larger $m$. Repeat the experiments for $m = 3$ to study the effect of the deletion number on the location of the phase transition.
3. Asymptotic halt rate. Estimate $\lim_{L \to \infty} \rho(\Sigma, m, L; \omega)$. Numerical evidence for the analogous limit in deterministic automata would be a useful reference point.
4. Reductions. Establish a precise reduction between $\mathrm{BB}_{\mathrm{TM}}(n)$ and $\mathrm{BB}(\Sigma, m, L)$ and use it to inherit lower bounds from the Turing-machine case.
5. Larger step caps. The current $\mathrm{BB}$ values are verified up to $N = 100{,}000$ for the $L = 3$, $|\Sigma| = 2$ case (Section 4.1.1). For larger $L$ the timeout fraction grows rapidly; ruling out late halters in those regimes will require either higher caps (with simulator cost scaling as $O(N \cdot |\text{word}|)$ per system) or a tighter cycle-detection argument that catches slow-growers.

09References

1. T. Rado, "On non-computable functions," Bell System Technical Journal, vol. 41, no. 3, pp. 877–884, 1962.
2. A. H. Brady, "The determination of the value of Rado's noncomputable function $\Sigma(k)$ for four-state Turing machines," Mathematics of Computation, vol. 40, no. 162, pp. 647–665, 1983.
3. M. L. Minsky, Computation: Finite and Infinite Machines. Englewood Cliffs, NJ: Prentice-Hall, 1967.
4. G. J. Martínez, H. Zenil, and J. C. S. T. Mora, "Busy beaver competition," in Computability of the Physical and the Algorithmic, 2012.
5. E. L. Post, "Formal reductions of the general combinatorial decision problem," American Journal of Mathematics, vol. 65, no. 2, pp. 197–215, 1943.
6. J. Cocke and M. Minsky, "Universality of tag systems with $P = 2$," Journal of the ACM, vol. 11, no. 1, pp. 15–20, 1964.
7. M. Minsky, "Recursive unsolvability of Post's problem of 'tag' and other topics in theory of Turing machines," Annals of Mathematics, vol. 74, no. 3, pp. 437–455, 1961.
8. H. Marxen and J. Buntrock, "Attacking the Busy Beaver 5," Bulletin of the EATCS, no. 40, pp. 247–251, 1990.