Post Tag System
Tag System
TODO
BB_PT
Let BB_PT(v,S) = max steps across all halting v-tag systems (deletion number v) of size S where size is computed as #symbols + sum of rule lengths. We default to BB_PT(S) = BB_PT(2,S) since 2-tags is Turing complete. The tag systems (TS) start with tape 0^v. Each step they delete the first v symbols of the tape and append w_k (rule k, where k was the first symbol deleted). They halt if tape size < v.
Starting with tape 0^v basically just means that the first step sets tape to w_0
Champions
| Size | BB_PT(n) | Champion | Holdouts |
|---|---|---|---|
| 1 | = 1 | 0 -> eps
|
0 |
| 2 | = 1 | 0 -> 0
|
0 |
| 3 | = 1 | 0 -> 0, 1 -> eps
|
0 |
| 4 | = 2 | 0 -> 11, 1 -> eps
|
0 |
| 5 | = 4 | 0 -> 011, 1 -> eps
|
0 |
| 6 | = 5 | 0 -> 011, 1 -> 1
|
0 |
| 7 | ≥ 10 | 0 -> 0111, 1 -> 1
|
1 |
| 8 | ≥ 19 | 0 -> 111, 1 -> 20, 2 -> eps
|
8 |
| 9 | ≥ 49 | 0 -> 11, 1 -> 021, 2 -> 2
|
326 |
| 10 | ≥ 779 | 0 -> 112, 1 -> 1, 2 -> 002
|
2,491 |
| 11 | ≥ 196,841 | 0 -> 120221, 1 -> 0, 2 -> 2
|
14,972 |
"eps" is the empty string
Analysis
BB_PT(7) champion analysis:
0 -> 0111, 1 -> 1
S(n) = 1^n 0 111
S(2k) —(k + 1)—> S(k + 2)
S(2k + 1) —(2k + 4)—> 1 (halt)
00 —(1)—> S(0)
—(1)—> S(2)
—(2)—> S(3)
—(6)—> 1 (halt)BB_PT(8) champion analysis:
0 -> 111, 1 -> 20, 2 ->
S(n) = 1^(n + 2)
S(2k) —(2k + 2)—> (halt)
S(2k + 1) —(2k + 4)—> S(3k + 3)
00 —(1)—> S(1)
—(4)—> S(3)
—(6)—> S(6)
—(8)—> (halt)