Cyclic tag system

From Esolang
Jump to: navigation, search

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