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.

Related articles