In the theory of computation, a tag system is a deterministic model of computation published by Emil Leon Post in 1943 as a simple form of a Post canonical system.
Because all of the indicated operations are performed in a single transition, a tag machine strictly has only one state.
(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.)
[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.
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.
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.
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.
[3] This version of the halting problem is among the simplest, most-easily described undecidable decision problems: 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?
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: 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.
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 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): That is, ak is encoded as a binary string with a 1 in the kth position from the left, and 0's elsewhere.