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.
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).
Productions: (011, 10, 101)
Initial data-string: 1
011 10 101 011 10 101 011 ...
1 011 11 1101 101011 0101110 101110 ...
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.
Cyclic tag systems are Turing-complete. As noted above, this was first proved via tag systems.