A tag system is set of rules that specifies a fixed number of elements (commonly denoted
or ) be removed from the beginning of
a sequence and a set of elements to be appended ("tagged" onto the end)
based on the elements that were removed from the beginning. For example, consider
the tag system shown in the illustration
above, in which black represents 1 and white represents 0. Then the starting pattern
is "1" and the transition rules are and (Wolfram 2002, p. 93).

Tag systems were first considered by Post in 1920 (Wolfram 2002, p. 894), although these results did not become widely known until published much later (Post
1943). Post apparently studied all of a certain type of tag system that involve removal
and addition of no more than two elements at each step and concluded that none of
them produced complicated behavior. However, looking at rules that remove three elements
at each step, he discovered a particular rule varies greatly with the initial conditions
(Wolfram 2002, pp. 894-895).
In general, if the number being added is never greater than the number of those deleted,
the resulting behavior will be at most cyclic. Thus, allowing additions up to any
length provide the most interesting and complex behavior.

Tag systems have a Turing machine-like halting problem for deciding based on an arbitrarily given initial sequence whether repeated
application of the rules leads to a word of length smaller than the number of elements
removed from the beginning. By proving that any Turing
machine may be represented as a tag system, Minsky (1961) proved the existence
universality and undecidable halting in tag systems, a result which was subsequently
improved by Cocke and Minsky (1964) and Wang (1963; Wolfram 2002, p. 1120).
Wang (1963) also considered a sort of opposite to a tag system that he dubbed a lag system. Maslov (1964) showed that for any , there is a tag system such that both forms of tag
systems formulated by Post are unsolvable.

Aanderaa, S. Belsnes, D. "Decision Problems for Tag Systems." J. Symb. Logic36, 229-239, 1971.Cocke,
J. and Minsky, M. "Universality of Tag Systems with ." J. Assoc. Comput. Mach.11, 15-20,
1964.Maslov, S. Ju. "On E. L. Post's 'Tag Problem.'
" Trudy Mat. Inst. Steklov.72, 57-68, 1964.Minsky,
M. L. "Recursive Unsolvability of Post's Problem of 'tag' and Other Topics
in Theory of Turing Machines." Ann. of Math.74, 437-455, 1961.Post,
E. L. "Formal Reductions of the General Combinatorial Decision Problem."
Amer. J. Math.65, 197-215, 1943.Wang, H. "Tag Systems
and Lag Systems." Math. Ann.152, 65-74, 1963.Wolfram,
S. A
New Kind of Science. Champaign, IL: Wolfram Media, pp. 93-96,
894-895, and
1120, 2002.