We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
Binary tag
Binary tag refers to specific tag systems where there are only two symbols.[1]
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): x is therefore 166, with the deletion number being well over 40 million.
References
- ↑ Neary, Turlough. (2013, Dec 19). Undecidability in binary tag systems and the Post correspondence problem for four pairs of words. arXiv. arXiv:1312.6700 https://doi.org/10.48550/arXiv.1312.6700