Tag system

<h2 id="definitions">Definitions</h2>
A tag system is a triplet (m, A, P), where

<ul><li>m is a positive integer, called the deletion number.</li>
<li>A is a finite alphabet of symbols, one of which can be a special halting symbol. All finite (possibly empty) strings on A are called words.</li>
<li>P is a set of production rules, assigning a word P(x) (called a production) to each symbol x in A. The production (say P(H)) assigned to the halting symbol is seen below to play no role in computations, but for convenience is taken to be P(H) = 'H'.</li></ul>
A halting word is a word that either begins with the halting symbol or whose length is less than m.
A transformation t (called the tag operation) is defined on the set of non-halting words, such that if x denotes the leftmost symbol of a word S, then t(S) is the result of deleting the leftmost m symbols of S and appending the word P(x) on the right. Thus, the system processes the m-symbol head into a tail of variable length, but the generated tail depends solely on the first symbol of the head.
A computation by a tag system is a finite sequence of words produced by iterating the transformation t, starting with an initially given word and halting when a halting word is produced. (By this definition, a computation is not considered to exist unless a halting word is produced in finitely-many iterations. Alternative definitions allow nonhalting computations, for example by using a special subset of the alphabet to identify words that encode output.)
The term m-tag system is often used to emphasise the deletion number. Definitions vary somewhat in the literature (cf. References), the one presented here being that of Rogozhin.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
The use of a halting symbol in the above definition allows the output of a computation to be encoded in the final word alone, whereas otherwise the output would be encoded in the entire sequence of words produced by iterating the tag operation.
A common alternative definition uses no halting symbol and treats all words of length less than m as halting words. Another definition is the original one used by Post (1943) (described in the historical note below), in which the only halting word is the empty string.

<h3>Example: A simple 2-tag illustration</h3>
This is merely to illustrate a simple 2-tag system that uses a halting symbol.

2-tag system 
 Alphabet: {a,b,c,H} 
 Production rules:
 a --> ccbaH
 b --> cca
 c --> cc

Computation
    Initial word: baa
                    acca
                      caccbaH
                        ccbaHcc
                          baHcccc
                            Hcccccca (halt).

<h3>Example: Computation of Collatz sequences</h3>
This simple 2-tag system is adapted from De Mol (2008). It uses no halting symbol, but halts on any word of length less than 2, and computes a slightly modified version of the <a href="/facts/Collatz_conjecture/nr3K8p4n">Collatz sequence</a>.
In the original Collatz sequence, the successor of n is either ⁠n/2⁠ (for even n) or 3n + 1 (for odd n). The value 3n + 1 is clearly even for odd n, hence the next term after 3n + 1 is surely ⁠3n + 1/2⁠. In the sequence computed by the tag system below we skip this intermediate step, hence the successor of n is ⁠3n + 1/2⁠ for odd n.
In this tag system, a positive integer n is represented by the word aa...a with n a's.

2-tag system 
 Alphabet: {a,b,c} 
 Production rules:
 a --> bc
 b --> a
 c --> aaa

Computation
 Initial word: aaa <--> n=3
 abc 
 cbc
 caaa
 aaaaa <--> 5
 aaabc
 abcbc
 cbcbc
 cbcaaa
 caaaaaa
 aaaaaaaa <--> 8
 aaaaaabc
 aaaabcbc
 aabcbcbc
 bcbcbcbc
 bcbcbca
 bcbcaa
 bcaaa
 aaaa <--> 4
 aabc
 bcbc
 bca
 aa <--> 2
 bc
 a <--> 1
 (halt)

<h2 id="turing-completeness-of-m-tag-systems">Turing-completeness of m-tag systems</h2>
For each m > 1, the set of m-tag systems is <a href="/facts/Turing_completeness/73goop44">Turing-complete</a>; i.e., for each m > 1, it is the case that for any given <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> T, there is an m-tag system that <a href="/facts/Surrogate_model/6uNjvd8B">emulates</a> T. In particular, a 2-tag system can be constructed to emulate a <a href="/facts/Universal_Turing_machine/2klpb1qQ">Universal Turing machine</a>, as was done by Wang (1963) and by Cocke & Minsky (1964).
Conversely, a Turing machine can be shown to be a Universal Turing Machine by proving that it can emulate a Turing-complete class of m-tag systems. For example, Rogozhin (1996) proved the universality of the class of 2-tag systems with alphabet {a1, ..., an, H} and corresponding productions {ananW1, ..., ananWn-1, anan, H}, where the Wk are nonempty words; he then proved the universality of a very small (4-state, 6-symbol) Turing machine by showing that it can simulate this class of tag systems.
The 2-tag system is an efficient simulator of universal Turing machines, in 
 
 
 
 O
 (
 
 t
 
 4
 
 
 
 ln
 
 2
 
 
 ⁡
 t
 )
 
 
 {\displaystyle O(t^{4}\ln ^{2}t)}
 
 time. That is, if 
 
 
 
 M
 
 
 {\displaystyle M}
 
 is a deterministic single-tape Turing machine that runs in time 
 
 
 
 t
 
 
 {\displaystyle t}
 
, then there is a 2-tag system that simulates it in 
 
 
 
 O
 (
 
 t
 
 4
 
 
 
 ln
 
 2
 
 
 ⁡
 t
 )
 
 
 {\displaystyle O(t^{4}\ln ^{2}t)}
 
 time.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="the-2-tag-halting-problem">The 2-tag halting problem</h2>
This version of the <a href="/facts/Halting_problem/Xz1bac40">halting problem</a> is among the simplest, most-easily described <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable</a> <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a>:
Given an arbitrary positive integer n and a list of n+1 arbitrary words P1,P2,...,Pn,Q on the alphabet {1,2,...,n}, does repeated application of the tag operation t: ijX → XPi eventually convert Q into a word of length less than 2? That is, does the sequence Q, t1(Q), t2(Q), t3(Q), ... terminate?

<h2 id="historical-note-on-the-definition-of-tag-system">Historical note on the definition of tag system</h2>
The above definition differs from that of Post (1943), whose tag systems use no halting symbol, but rather halt only on the empty word, with the tag operation t being defined as follows:

<ul><li>If x denotes the leftmost symbol of a nonempty word S, then t(S) is the operation consisting of first appending the word P(x) to the right end of S, and then deleting the leftmost m symbols of the result — deleting all if there be less than m symbols.</li></ul>
The above remark concerning the Turing-completeness of the set of m-tag systems, for any m > 1, applies also to these tag systems as originally defined by Post.

<h3>Origin of the name "tag"</h3>
According to a footnote in Post (1943), B. P. Gill suggested the name for an earlier variant of the problem in which the first m symbols are left untouched, but rather a check mark indicating the current position moves to the right by m symbols every step. The name for the problem of determining whether or not the check mark ever touches the end of the sequence was then dubbed the "problem of tag", referring to the children's <a href="/facts/Tag_(game)/lNgXc04t">game of tag</a>.

<h2 id="cyclic-tag-systems">Cyclic tag systems</h2>
A cyclic tag system is a modification of the original tag system. The alphabet consists of only two symbols, 0 and 1, and the production rules comprise a list of productions considered sequentially, cycling back to the beginning of the list after considering the "last" production on the list. For each production, the leftmost symbol of the word is examined—if the symbol is 1, the current production is appended to the right end of the word; if the symbol is 0, no characters are appended to the word; in either case, the leftmost symbol is then deleted. The system halts if and when the word becomes empty.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h3>Example</h3>
Cyclic Tag System
 Productions: (010, 000, 1111)

Computation
 Initial Word: 11001
    Production         Word
    ----------         --------------
       010             11001
       000              1001010
       1111              001010000
       010                01010000
       000                 1010000
       1111                 010000000
       010                   10000000
        .                      .
        .                      .

Cyclic tag systems were created by <a href="/facts/Matthew_Cook/JtMY9JLs">Matthew Cook</a> and were used in Cook's demonstration that the <a href="/facts/Rule_110/5LzC7FUK">Rule 110 cellular automaton</a> is universal.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> A key part of the demonstration was that cyclic tag systems can emulate a <a href="/facts/Turing-complete/73goop44">Turing-complete</a> class of tag systems.

<h2 id="emulation-of-tag-systems-by-cyclic-tag-systems">Emulation of tag systems by cyclic tag systems</h2>
An m-tag system with alphabet {a1, ..., an} and corresponding productions {P1, ..., Pn} is emulated by a cyclic tag system with m*n productions (Q1, ..., Qn, -, -, ..., -), where all but the first n productions are the empty string (denoted by '-'). The Qk are encodings of the respective Pk, obtained by replacing each symbol of the tag system alphabet by a length-n binary string as follows (these are to be applied also to the initial word of a tag system computation):

a1 = 100...00
a2 = 010...00
.
.
.
an = 000...01

That is, ak is encoded as a binary string with a 1 in the kth position from the left, and 0's elsewhere. Successive lines of a tag system computation will then occur encoded as every (m*n)th line of its emulation by the cyclic tag system.

<h3>Example</h3>
This is a very small example to illustrate the emulation technique.

2-tag system
 Production rules: (a --> bb, b --> abH, H --> H)
 Alphabet encoding: a = 100, b = 010, H = 001 
 Production encodings: (bb = 010 010, abH = 100 010 001, H = 001)

Cyclic tag system 
    Productions: (010 010, 100 010 001, 001, -, -, -)

Tag system computation
    Initial word: ba
                    abH
                      Hbb (halt)

Cyclic tag system computation
    Initial word: 010 100 (=ba)

Production Word
 ---------- -------------------------------
 * 010 010 010 100 (=ba)
 100 010 001 10 100
 001 0 100 100 010 001
 - 100 100 010 001
 - 00 100 010 001
 - 0 100 010 001
 * 010 010 100 010 001 (=abH)
 100 010 001 00 010 001 010 010
 001 0 010 001 010 010
 - 010 001 010 010
 - 10 001 010 010
 - 0 001 010 010
 * 010 010 emulated halt --> 001 010 010 (=Hbb)
 100 010 001 01 010 010
 001 1 010 010
 - 010 010 001
 ... ...
 
Every sixth line (marked by '*') produced by the cyclic tag system is the encoding of a corresponding line of the tag system computation, until the emulated halt is reached.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Queue_automaton/KNFbvylc">Queue automaton</a></li>
<li><a href="/facts/Conway%27s_Game_of_Life/ofHgJmmb">Conway's Game of Life</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/John_Cocke_(computer_scientist)/u2q0rtyw">Cocke, John</a>; <a href="/facts/Marvin_Minsky/HTU5MYLL">Minsky, Marvin</a> (1964). "Universality of Tag Systems with P=2". Journal of the Association for Computing Machinery. 11: 15–20. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321203.321206">10.1145/321203.321206</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/1721.1%2F6107">1721.1/6107</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2799125">2799125</a>.</li>
<li><a href="/facts/Matthew_Cook/JtMY9JLs">Cook, Matthew</a> (2004). <a href="https://www.complex-systems.com/abstracts/v15_i01_a01/">"Universality in Elementary Cellular Automata"</a>. Complex Systems. 15: 1–40. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.25088%2FComplexSystems.15.1.1">10.25088/ComplexSystems.15.1.1</a>. <a href="https://web.archive.org/web/20160528014857/http://www.complex-systems.com/pdf/15-1-1.pdf">Archived</a> (PDF) from the original on 28 May 2016.</li>
<li>De Mol, Liesbeth (January 2008). "Tag systems and Collatz-like functions". Theoretical Computer Science. 390 (1): 92–101. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.tcs.2007.10.020">10.1016/j.tcs.2007.10.020</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/1854%2FLU-436211">1854/LU-436211</a>.</li>
<li><a href="/facts/Marvin_Minsky/HTU5MYLL">Minsky, Marvin L.</a> (November 1961). "Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines". <a href="/facts/Annals_of_Mathematics/CUYktUqD">Annals of Mathematics</a>. 2. 74 (3): 437–455. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F1970290">10.2307/1970290</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/1970290">1970290</a>.</li>
<li><a href="/facts/Marvin_Minsky/HTU5MYLL">Minsky, Marvin L.</a> (1967). <a href="https://archive.org/details/computationfinit0000mins/page/267">Computation: Finite and Infinite Machines</a>. Englewood Cliffs, N.J.: <a href="/facts/Prentice%E2%80%93Hall/bynWAuat">Prentice–Hall</a>. pp. 267–273. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0131655638. <a href="/facts/LCCN_(identifier)/5hb5Cw2V">LCCN</a> <a href="https://lccn.loc.gov/67-12342">67-12342</a>.</li>
<li><a href="/facts/Emil_Post/Hl2CKCxw">Post, Emil</a> (1943). <a href="https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/197">"Formal reductions of the combinatorial decision problem"</a>. <a href="/facts/American_Journal_of_Mathematics/lkgftcD7">American Journal of Mathematics</a>. 65 (2): 197–215. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2371809">10.2307/2371809</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2371809">2371809</a>. (Tag systems are introduced on <a href="https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/203">p. 203ff</a>.)</li>
<li>Rogozhin, Yurii (20 November 1996). "Small Universal Turing Machines". <a href="/facts/Theoretical_Computer_Science/jSkGGuvy">Theoretical Computer Science</a>. 168 (2): 215–240. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0304-3975%2896%2900077-1">10.1016/S0304-3975(96)00077-1</a>.</li>
<li><a href="/facts/Hao_Wang_(academic)/cpTlnyMm">Wang, Hao</a> (1963). "Tag Systems and Lag Systems". <a href="/facts/Mathematische_Annalen/GPhGaonc">Mathematische Annalen</a>. 152: 65–74. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01343730">10.1007/BF01343730</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:120383146">120383146</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://mathworld.wolfram.com/TagSystem.html">https://mathworld.wolfram.com/TagSystem.html</a></li>
<li><a href="https://mathworld.wolfram.com/CyclicTagSystem.html">https://mathworld.wolfram.com/CyclicTagSystem.html</a></li>
<li><a href="https://www.wolframscience.com/nks/p95/">https://www.wolframscience.com/nks/p95/</a> (cyclic tag systems)</li>
<li><a href="https://www.wolframscience.com/nks/p669/">https://www.wolframscience.com/nks/p669/</a> (emulation of tag systems)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Post 1943. - Post, Emil (1943). "Formal reductions of the combinatorial decision problem". American Journal of Mathematics. 65 (2): 197–215. doi:10.2307/2371809. JSTOR 2371809. <a href="https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/197" target="_blank">https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/197</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Rogozhin 1996. - Rogozhin, Yurii (20 November 1996). "Small Universal Turing Machines". Theoretical Computer Science. 168 (2): 215–240. doi:10.1016/S0304-3975(96)00077-1. <a href="https://doi.org/10.1016%2FS0304-3975%2896%2900077-1" target="_blank">https://doi.org/10.1016%2FS0304-3975%2896%2900077-1</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Woods, Damien; Neary, Turlough (2009-02-17). "The complexity of small universal Turing machines: A survey" (PDF). Theoretical Computer Science. Computational Paradigms from Nature. 410 (4): 443–450. doi:10.1016/j.tcs.2008.09.051. ISSN 0304-3975. S2CID 10257004. <a href="https://authors.library.caltech.edu/103354/1/1110.2230.pdf" target="_blank">https://authors.library.caltech.edu/103354/1/1110.2230.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">In a chapter 14 titled "Very Simple Bases for Computability", Minsky (1967) presents a very readable (and exampled) subsection 14.6 The Problem of "Tag" and Monogenic Canonical Systems (pp. 267–273) (this sub-section is indexed as "tag system"). Minsky relates his frustrating experiences with the general problem: "Post found this (00, 1101) problem "intractable," and so did I, even with the help of a computer." He comments that an "effective way to decide, for any string S, whether this process will ever repeat when started with S" is unknown although a few specific cases have been proven unsolvable. In particular he mentions Cocke's Theorem and Corollary 1964. - Minsky, Marvin L. (1967). Computation: Finite and Infinite Machines. Englewood Cliffs, N.J.: Prentice–Hall. pp. 267–273. ISBN 978-0131655638. LCCN 67-12342. <a href="https://archive.org/details/computationfinit0000mins/page/267" target="_blank">https://archive.org/details/computationfinit0000mins/page/267</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Cook 2004. - Cook, Matthew (2004). "Universality in Elementary Cellular Automata". Complex Systems. 15: 1–40. doi:10.25088/ComplexSystems.15.1.1. Archived (PDF) from the original on 28 May 2016. <a href="https://www.complex-systems.com/abstracts/v15_i01_a01/" target="_blank">https://www.complex-systems.com/abstracts/v15_i01_a01/</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

Tag system open-in-new

Tag system