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.
Related articles
- Tag system
- Sequential tag system
- Bitwise Cyclic Tag -- a Turing tarpit derived from cyclic tag.
- BIX Queue Subset #Existing languages
External resources
- Compiler from Turing machines to cyclic tag written in Wolfram Mathematica (by User:Xylochoron)
- A cyclic tag interpreter written in Jelly and runnable online