A tag system in which a list of 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 and with initial state , 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 , since is appended, and the initial is then deleted.
2. Applying the second rule adds at the end and removes the first element, yielding .
3. Again applying the first rule adds at the end and (as always) removes the first element, yielding .
4. Again applying the second rule gives , 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).