Cyclic Tag
(Redirected from Unary Cyclic Tag)
For the tree rewriting system based on Cyclic Tag, see Cyclic Tree Rewriting System.
Cyclic Tag System
Cyclic Tag is a Turing-complete computational model[1] where a binary string evolves under a set of rules applied in cyclic order. There are various halting conditions that one may choose. They are explicitly stated further below.
A cyclic tag system has:
- A finite string of bits.
- A code consisting of a list of production rules.
- A head pointing at one of the production rules.
Execution rules:
- The cyclic tag system starts out with string equal to "1", with the head pointing to the first rules.
- At each step of the computation, delete the first symbol of the string and append the production rules to the string if it 1.
- Move the head one rule forward or at the first rule if it is pointing to the last rule.
- The cyclic tag system halts when it reaches the empty string.
Busy Beaver Function
The function BBCT(n) is the largest number of steps that any cyclic tag systems of size n takes before halting.
The size of a cyclic tag system is the sum of the lengths of all the production rules plus the number of production rules (same as for BB_PT).
| BBCT(n) | Value | Champion |
|---|---|---|
| 1 | 1 | empty
|
| 2 | 2 | 0
|
| 3 | 3 | 00
|
| 4 | 4 | 000
|
| 5 | 7 | 010_
|
| 6 | 8 | 010_0
|
| 7 | = 13 | 0110__
|
| 8 | ≥ 28 | 101_10_
|
| 9 | ≥ 717 | 1011_00_
|
| 10 | ≥ 1,626,862 | 1001_1_00
|
| 11 | ≥ 1,859,166 | 10_10010_0
|
| 12 | ≥ 6,328 | 0111__010_0
|
| 13 | ≥ 5,217,735 | 001110_1_0_0
|
| 14 | ≥ 154,171,565 | 01011__0_0100
|
See also
Sources
GitHub repository (with documentation, deciders and holdout lists): https://github.com/AzertyWasTaken/Busy-Beaver/tree/main/Cyclic%20Tag%20System