Cyclic Tag
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, read 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 has less than two symbol.
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 symbols count and production rules count.
| 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 | ≥ 209 | 11_0_0100
|
| 11 | ≥ 2,269 | 1011_1_00_
|
| 12 | ≥ 6,328 | 0111__010_0
|
| 13 | ≥ 50,906 | 0011_010_1_0
|