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

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 was created by Matthew Cook as 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). 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.

A 2-tag system can be reduced to cyclic tag by:

1. Enumerating each symbol in the alphabet $\Sigma$ from 1 to $|\Sigma |$
2. Replacing each symbol numbered i with $|\Sigma |$ zeros, with the ith zero replaced with 1
3. Ordering the symbols with their productions according to the enumeration
4. Replacing the (symbol → production) pairs with just the production (resulting in a valid cyclic tag program)
5. Adding $|\Sigma |$ empty productions at the end

The first set of productions, which are derived from the original program, effectively consume the first symbol of the queue and produce the correct production. By having only a single 1 in each encoded symbol, they act as one-hot indices into the productions, meaning only one production is made per loop. The second set consumes the second symbol without producing anything.

def tag_to_cyclic(productions):
    count = len(productions)
    # construct the one hot vectors
    table = str.maketrans({
        v: "0" * i + "1" + "0" * (count - i - 1)
        for i, v in enumerate(productions.keys())
    })
    program = []
    # replace all symbols in the production with the corresponding vector
    for match, production in productions.items():
        program.append(production.translate(table))
    # fill the remaining with empty vectors
    for i in range(count):
        program.append("")
    return program

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