Cyclic Tag System

A tag system in which a list of n tag rules (each of a special form) is applied to a system in sequential order and then starting again from the first rule. In a cyclic tag system, each set of tag rules has the special structure that a pattern is appended if (and only if) the first element of the current pattern is a 1 and that independent of whether the first element is 0 or 1, the first element is then deleted.


For example, consider a state consisting of white and black cells, labeled 0 and 1, respectively, and the cyclic tag system {(1,...)->(...,1,1),(0,...)->(...)} and {(1,...)->(...,1,0),(0,...)->(...)} with initial state (1), illustrated above. As required, this system always removes the first element and appends specific patterns iff the first cell is black.

1. At the first step, the leftmost element is 1, so applying the first rule gives (1,1), since (1,1) is appended, and the initial (1) is then deleted.

2. Applying the second rule adds (1,0) at the end and removes the first element, yielding (1,1,0).

3. Again applying the first rule adds (1,1) at the end and (as always) removes the first element, yielding (1,0,1,1).

4. Again applying the second rule gives (0,1,1,1,0), and so on (Wolfram 2002, p. 95).

It is possible to construct a cyclic tag system that can emulate any Turing machine, hence universal cyclic tag systems are possible (Wolfram 2002, p. 678).

See also

String Rewriting System, Substitution System, Tag System

Related Wolfram sites

Portions of this entry contributed by Todd Rowland

Explore with Wolfram|Alpha


Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 95-96 and 895, 2002.

Referenced on Wolfram|Alpha

Cyclic Tag System

Cite this as:

Rowland, Todd and Weisstein, Eric W. "Cyclic Tag System." From MathWorld--A Wolfram Web Resource.

Subject classifications