Binary tag

Not to be confused with 2-tag or bi-tag.

Binary tag refers to specific tag systems where there are only two symbols.

Neary proved binary tag Turing complete assuming the deletion number can be arbitrarily large. Neary's proof reduces cyclic tag systems into binary tag. Systems produced by this reduction have one symbol simply moving itself to the end, with the other appending the entire encoding of the input program $u$:

b → b

c → u

The algorithm takes in a cyclic tag system with $3k+2$ productions, then repeats its program $q$ times to produce a longer but semantically identical program. The amount of repetitions is chosen so that $q(3k+2)=3x-2$ with $x$ being even, and $x>2(r+7)$ where $r$ is the length of the longest production. The deletion number for the system is then determined to be $\beta =(3x^{2}+x)(3x-2)=9x^{3}-3x^{2}-2x$. Since $x\propto r$, the deletion number in this scheme is $O(r^{3})$.

If we take a naive compilation of UT19 into cyclic tag according to Cook's scheme, we result in a tag system where all productions are a multiple of 19. Since the longest production in UT19 is 4 symbols, the cyclic compilation will have its longest rule be 76 bits. A minimal estimate for $x$ is therefore 166, with the deletion number being well over 40 million.