Tag System


A tag system is set of rules that specifies a fixed number of elements (commonly denoted nu or beta) 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 nu=1 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 (1,...)->(...,1,0) and (0,...)->(...,0,1) (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 nu>=2, there is a tag system such that both forms of tag systems formulated by Post are unsolvable.

See also

Cellular Automaton, Cyclic Tag System, Lag System, Mobile Automaton, Substitution System, Turing Machine

Explore with Wolfram|Alpha


Aanderaa, S. Belsnes, D. "Decision Problems for Tag Systems." J. Symb. Logic 36, 229-239, 1971.Cocke, J. and Minsky, M. "Universality of Tag Systems with P=2." 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.

Referenced on Wolfram|Alpha

Tag System

Cite this as:

Weisstein, Eric W. "Tag System." From MathWorld--A Wolfram Web Resource.

Subject classifications