In thetheory of computation, atag system is a deterministicmodel of computation published byEmil Leon Post in 1943 as a simple form of aPost canonical system.^[1] A tag system may also be viewed as an abstract machine, called aPost tag machine (not to be confused withPost–Turing machines)—briefly, afinite-state machine whose only tape is aFIFOqueue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition.

Because all of the indicated operations are performed in a single transition, a tag machine strictly has only one state.

Atag system is a triplet (m,A,P), where

• m is a positive integer, called thedeletion number.
• A is a finite alphabet of symbols, one of which can be a specialhalting symbol. All finite (possibly empty) strings onA are calledwords.
• P is a set ofproduction rules, assigning a wordP(x) (called aproduction) to each symbolx inA. The production (sayP(H)) assigned to the halting symbol is seen below to play no role in computations, but for convenience is taken to beP(H) ='H'.

Ahalting word is a word that either begins with the halting symbol or whose length is less thanm.

A transformationt (called thetag operation) is defined on the set of non-halting words, such that ifx denotes the leftmost symbol of a wordS, thent(S) is the result of deleting the leftmostm symbols ofS and appending the wordP(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.

Acomputation by a tag system is a finite sequence of words produced by iterating the transformationt, 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 termm-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.^[2]

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 thanm as halting words. Another definition is the original one used byPost (1943) (described in the historical note below), in which the only halting word is the empty string.

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  -->  ccComputation    Initial word: baa                    acca                      caccbaH                        ccbaHcc                          baHcccc                            Hcccccca (halt).

This simple 2-tag system is adapted fromDe Mol (2008). It uses no halting symbol, but halts on any word of length less than 2, and computes a slightly modified version of theCollatz sequence.

In the original Collatz sequence, the successor ofn 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 ofn is⁠3n + 1/2⁠ for odd n.

In this tag system, a positive integern is represented by the word aa...a withn a's.

2-tag system     Alphabet: {a,b,c}     Production rules:         a  -->  bc         b  -->  a         c  -->  aaaComputation    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)

For eachm > 1, the set ofm-tag systems isTuring-complete; i.e., for eachm > 1, it is the case that for any givenTuring machineT, there is anm-tag system thatemulatesT. In particular, a 2-tag system can be constructed to emulate aUniversal Turing machine, as was done byWang (1963) and byCocke & 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 ofm-tag systems. For example,Rogozhin (1996) proved the universality of the class of 2-tag systems with alphabet {a₁, ...,a_n,H} and corresponding productions {a_na_nW₁, ...,a_na_nW_n-1,a_na_n,H}, where theW_k 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${\displaystyle O(t^4{\ln }^{2}t)}$ time. That is, if${\displaystyle M}$ is a deterministic single-tape Turing machine that runs in time${\displaystyle t}$, then there is a 2-tag system that simulates it in${\displaystyle O(t^4{\ln }^{2}t)}$ time.^[3]

This version of thehalting problem is among the simplest, most-easily describedundecidabledecision problems:

Given an arbitrary positive integern and a list ofn+1 arbitrary wordsP₁,P₂,...,P_n,Q on the alphabet {1,2,...,n}, does repeated application of the tag operationt:ijX →XP_i eventually convertQ into a word of length less than 2? That is, does the sequenceQ,t¹(Q),t²(Q),t³(Q), ... terminate?

The above definition differs from that ofPost (1943), whose tag systems use no halting symbol, but rather halt only on the empty word, with the tag operationt being defined as follows:

• Ifx denotes the leftmost symbol of a nonempty wordS, thent(S) is the operation consisting offirst appending the wordP(x) to the right end ofS, andthen deleting the leftmostm symbols of the result —deleting all if there be less thanm symbols.

The above remark concerning the Turing-completeness of the set ofm-tag systems, for anym > 1, applies also to these tag systems as originally defined by Post.

According to a footnote inPost (1943), B. P. Gill suggested the name for an earlier variant of the problem in which the firstm symbols are left untouched, but rather a check mark indicating the current position moves to the right bym 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'sgame of tag.

A cyclic tag system is a modification of the original tag system. The alphabet consists of only two symbols,0 and1, 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 is1, the current production is appended to the right end of the word; if the symbol is0, 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.^[4]

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 byMatthew Cook and were used in Cook's demonstration that theRule 110 cellular automaton is universal.^[5] A key part of the demonstration was that cyclic tag systems can emulate aTuring-complete class of tag systems.

Anm-tag system with alphabet {a₁, ...,a_n} and corresponding productions {P₁, ...,P_n} is emulated by a cyclic tag system withm*n productions (Q₁, ...,Q_n, -, -, ..., -), where all but the firstn productions are the empty string (denoted by '-'). TheQ_k are encodings of the respectiveP_k, 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...00a2 = 010...00...an = 000...01

That is,a_k is encoded as a binary string with a1 in the k^th position from the left, and0'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.

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.

• Queue automaton
• Conway's Game of Life

• Cocke, John;Minsky, Marvin (1964). "Universality of Tag Systems with P=2".Journal of the Association for Computing Machinery.11:15–20.doi:10.1145/321203.321206.hdl:1721.1/6107.S2CID 2799125.
• 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.
• De Mol, Liesbeth (January 2008). "Tag systems and Collatz-like functions".Theoretical Computer Science.390 (1):92–101.doi:10.1016/j.tcs.2007.10.020.hdl:1854/LU-436211.
• Minsky, Marvin L. (November 1961). "Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines".Annals of Mathematics. 2.74 (3):437–455.doi:10.2307/1970290.JSTOR 1970290.
• Minsky, Marvin L. (1967).Computation: Finite and Infinite Machines. Englewood Cliffs, N.J.:Prentice–Hall. pp. 267–273.ISBN 978-0131655638.LCCN 67-12342.
• Post, Emil (1943)."Formal reductions of the combinatorial decision problem".American Journal of Mathematics.65 (2):197–215.doi:10.2307/2371809.JSTOR 2371809. (Tag systems are introduced onp. 203ff.)
• Rogozhin, Yurii (20 November 1996). "Small Universal Turing Machines".Theoretical Computer Science.168 (2):215–240.doi:10.1016/S0304-3975(96)00077-1.
• Wang, Hao (1963). "Tag Systems and Lag Systems".Mathematische Annalen.152:65–74.doi:10.1007/BF01343730.S2CID 120383146.

• https://mathworld.wolfram.com/TagSystem.html
• https://mathworld.wolfram.com/CyclicTagSystem.html
• https://www.wolframscience.com/nks/p95/ (cyclic tag systems)
• https://www.wolframscience.com/nks/p669/ (emulation of tag systems)

• Models of computation

• Articles with short description
• Short description is different from Wikidata