Busy Beaver Values for Post Tag Systems

An empirical study of the Busy Beaver function for Post tag systems, with exhaustive search results for small alphabets and a discussion of the $\omega$-dependence of the Busy Beaver value.

Authors: Sahil Ohe & OpenCode (MiniMax M3 and DeepSeek V4 Pro)

Paper

The published paper is hosted at the GitHub Pages URL for this repository: https://sahilohe.github.io/BB_TagSystems/

The same paper is also available in two other formats in this repo:

• index.html — web version (served as the GitHub Pages home)
• paper/research.md — Markdown source
• paper/research.docx — Microsoft Word (publication-ready styling)

Headline results

$(\lvert\Sigma\rvert, m, L; \omega)$	BB	Halting rate $\rho$
$(2, 2, 1; 011)$	2	1.00
$(2, 2, 2; 011)$	4	0.39
$(2, 2, 3; 011)$	6	0.12
$(2, 2, 3; 000)$	10	0.18
$(3, 2, 1; 012)$	2	1.00
$(3, 2, 2; 012)$	7	0.36

The value of BB depends sharply on the initial word $\omega$. For $\omega = 011$ over $\Sigma_2$ the growth is $\Theta(L)$ with constant $\approx 2$ (Conjecture 2a). For single-symbol $\omega$ the growth is different (Conjecture 2b, supported only by three data points).

Repository layout

tag_busy_beaver/
├── index.html               # paper — web version (GitHub Pages root)
├── README.md                # this file
├── AGENTS.md                # local agent instructions
│
├── src/                     # Python source (stdlib only, no dependencies)
│   ├── simulator.py         #   tag-system simulator (library + tiny demo)
│   ├── find_champions.py    #   exhaustive search → data/champions.json
│   └── experiment.py        #   exhaustive search → data/experiment_results.csv
│
├── data/                    # generated artifacts (re-creatable from src/)
│   ├── champions.json       #   winning rule set per (|Σ|, m, L) config
│   ├── experiment_results.csv   # BB and ρ per config
│   ├── l3_stepcap_sweep.csv #   step-cap sensitivity data (Section 4.1.1)
│   └── l3_stepcap_sweep.md  #   narrative writeup of the sweep
│
├── paper/                   # the paper itself, in three formats
│   ├── research.md          #   Markdown source (canonical)
│   └── research.docx        #   Word (publication-ready styling; one-time artifact)
│
└── docs/                    # research logs / meta
    └── NOTES.md             #   research log (newest-first)

index.html lives at the repo root because GitHub Pages serves it as the project home; all other files are grouped by role.

Reproducing the results

The pipeline is pure stdlib (Python 3.10+, no dependencies). Run from the repo root (tag_busy_beaver/):

# Verify the canonical BB values
python3 src/find_champions.py
# → writes data/champions.json

# Verify the halting rates
python3 src/experiment.py
# → writes data/experiment_results.csv

# L=3 step-cap sensitivity sweep
python3 src/l3_stepcap_sweep.py   # not yet in the repo — see docs/NOTES.md

The simulator is intentionally simple. src.simulator.simulate_tag_system(word, rules, m, max_steps) returns one of the four status strings: halted, halted_no_rule, cycle, timeout. Cycle detection is via a seen_states set; see Lemma 1 in the paper for the correctness argument.

Step cap

All reported BB values are verified at step cap $N = 5000$, with the $L = 3$ case additionally verified at $N = 10,000$ and $N = 100,000$ (see l3_stepcap_sweep.md). Values are exact when no halting system in the search space exceeds the cap, and are verified lower bounds otherwise.

License

Research artifact. Add a license here before publishing if you want explicit terms — for now, all rights reserved by the authors.