Cyclic tag system

From Esolang

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.

1 Definition
2 Example
3 History
4 Related articles

[edit] Definition

A cyclic tag system is a finite list of finite binary strings (called productions), P₀,P₁,...,P_n-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, XP_i^d)

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 P_i⁰ denotes the empty string, and P_i¹ = P_i.

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).

[edit] Example

Cyclic tag system

  Productions: (011, 10, 101) 
  Initial data-string: 1

  System evolution:

  Production  Data-string 
  ----------  -------------
    011       1
     10        011
    101         11
    011          1101
     10           101011
    101            0101110
    011             101110
    ...              ...

[edit] 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.