A tag system is a set of rules for transforming a word over a finite alphabet. Each
step removes a fixed positive integer number
of symbols from the beginning of the
word and appends a prescribed word
determined by its first symbol. The process halts when the word
has length less than 
. For example, consider the 
tag system shown in the illustration above, in which black
represents 1 and white represents 0. Then the starting word
is "1" and the transition rules are 
and 
(Wolfram 2002, p. 93).
Post's early work on tag systems dates to 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 that 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 word length cannot increase, so the process must halt or eventually repeat a word and become cyclic. Thus, allowing additions up to any length provides the most interesting and complex behavior.
Tag systems have a Turing machine-like halting problem for deciding based on an arbitrarily given initial word
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 of universality
and recursively 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 every deletion
number 
, there is a tag system with an
unsolvable halting problem (De Mol 2007). Its
word-reachability problem is also unsolvable. This problem
asks whether, for arbitrary words 
and 
,
repeated application of the rules starting at 
ever produces 
. If reachability were decidable, halting could be decided
by checking reachability of the finitely many words of length less than 
. Halting and word reachability are
the two decision problems considered by Post (De Mol 2007).
." J. Assoc. Comput. Mach. 11, 15-20,
1964.De Mol, L. "Study of Limits of Solvability in Tag Systems."
In Proc. 5th International Conference on Machines, Computations, and Universality
(Ed. J. Durand-Lose and M. Margenstern). Berlin, Germany: Springer, pp. 170-181,
2007.