Post Tag System

A Post Tag System is a Turing-complete formal system invented by Emil Post in 1920 (but not published until 1943). Post explored tag systems before Turing machines were invented and thus before the solution to the Entscheidungsproblem, the Church-Turing thesis and the undecidability of the Halting problem were known. According to Wolfram, Post studied systems where no more than 2 symbols were ever deleted or added and found none produced complicated behavior, but that a rule with up to 3 symbols deleted or added could produce chaotic and seemingly intractable behavior. Tag systems were proven to be Turing-complete by Marvin Minsky in 1961.

Tag System

A tag system is defined by:

• A positive integer v, called the deletion number
• A finite alphabet of symbols: A
• One "production rules" for each symbol: $w_a\in A^{*}$ (for each $a\in A$)

We will often write a v-tag system to specify that it is a tag system with deletion number v (ex: a 2-tag system).

A tag system operates on a tape (a possibly empty sequence of symbols). At each step:

• If the tape is shorter than v, it halts.
• Otherwise, it reads the first symbol (a), deletes the first v symbols from the tape and appends $w_a$

It repeats this process until it halts.

1-tag systems are decidable, but v-tag systems for any v ≥ 2 are undecidable and (in fact) Turing complete.

BB_PT

Let us define the size of a tag system to be the $S=|A|+\sum _{a\in A}|w_a|=\sum _{a\in A}(|w_a|+1)$.

Let BB_PT(v, S) = max steps across all v-tag systems of size S which halt when started on tape $0^v$. We default to BB_PT(S) = BB_PT(2,S) since 2-tags is Turing complete.

Starting with tape $0^v$ means that after the first step the tape is $w_0$.

Champions

2-tag 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

Cryptids

realsheepthe constructed a size 11 Cryptid (originally mislabeled as a near-Cryptid) 0 —> 11111, 1 —> 20, 2 —> 1 which simulates the Collatz-like iteration:

S(n) = 1^n
S(0) —(0)->  (halt)
S(1) —(0)-> 1 (halt)
S(2k + 2) -(2k + 2)-> S(k + 1)
S(2k + 3) -(2k + 4)-> S(5k + 9)

00 -(1)-> S(5)
-(6)-> S(14)
-(14)-> S(7)
-(8)-> S(19)
-(20)-> S(49)
-(50)-> S(124)
...

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)