Post Tag System
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). 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.
"eps" is the empty string
Starting with tape 0^v basically just means that the first step sets tape to w_0
| BB_PT(n) | Value | Champion |
|---|---|---|
| 1 | 1 | 0 -> eps
|
| 2 | 1 | 0 -> 0
|
| 3 | > 1 | 0 -> 0, 1 -> eps
|
| 4 | > 2 | 0 -> 11, 1 -> eps
|
| 5 | > 4 | 0 -> 011, 1 -> eps
|
| 6 | > 5 | 0 -> 011, 1 -> 1
|
| 7 | > 10 | 0 -> 0111, 1 -> 1
|
| 8 | > 19 | 0 -> 111, 1 -> 20, 2 -> eps
|
| 9 | > 49 | 0 -> 11, 1 -> 021, 2 -> 2
|
| 10 | > 779 | 0 -> 112, 1 -> 1, 2 -> 002
|
| 11 | > 196,841 | 0 -> 120221, 1 -> 0, 2 -> 2
|