Tag System

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.