# 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), P0,P1,...,Pn-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 mod n, XPid)
```

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 Pi0 denotes the empty string, and Pi1 = Pi.

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.