# Cyclic tag system

A **cyclic tag system** is a Turing-complete computational model in which a binary string of finite but unbounded length evolves under the action of production rules applied in cyclic order.

## Definition

A **cyclic tag system** is a finite list of finite binary strings (called *productions*), *P*_{0},*P*_{1},...,*P*_{n-1}, together with a finite binary data-string *D*. The data-string evolves from a specified initial string by iterating the following transformation, halting when *D* is empty:

(i,dX) → (i+1 modn,XP)_{i}^{d}

where *i* is a pointer (initially 0) to the current production, *dX* denotes the data-string *D* with leftmost symbol *d* (0 or 1). Here P_{i}^{0} denotes the empty string, and P_{i}^{1} = P_{i}.

In other words, the productions are considered one at a time in cyclic order, appending the current production to the data-string if the latter begins with 1, then deleting that first symbol (each time in any case).

## Example

Productions: (011, 10, 101)

Initial data-string: 1

System evolution:

Production | Data-string |
---|---|

011 10 101 011 10 101 011 ... |
1 011 11 1101 101011 0101110 101110 ... |

## History

The cyclic tag system model is a modified form of tag system, designed to allow control of the order of application of the production rules. By encoding a tag system's alphabet as equal-length binary strings, a cyclic tag system can be designed to emulate any tag system -- thus showing the latter to be Turing-complete (since the set of tag systems is Turing-complete). Matthew Cook relied on cyclic tag systems to prove the Turing completeness of Stephen Wolfram's Rule 110 cellular automaton.

## Computational class

Cyclic tag systems are Turing-complete. As noted above, this was first proved via tag systems.

If you like Fractran, you may find this reduction via Collatz functions simpler, not to mention easier to track down.

## Related articles

- Tag system
- Sequential tag system
- Bitwise Cyclic Tag -- a Turing tarpit derived from cyclic tag.