# Cyclic Tag System : 1 Line of Turing-Complete Code

The following line of python code is able to simulate a Universal Turing Machine:

while len(word) > S : pIndex, word = (pIndex + 1) % len(C), word[1:] + C[pIndex] if (word[0] == "1") else word[1:] |

It is 114 characters long and can probably reduced further using some clever python tricks. It implements one of the most extraordinarily simple Turing-Complete models: a Cyclic Tag System or CTS. The CTS was first introduced by Mathew Cook in 2004 when he published his paper on the universality of Elementary Cellular Automata and specifically Rule 110. This rule, simple on its own right but out of scope for this post, was long suspected to be able to simulate a Universal Turing Machine (and thus Turing-Complete). It was Cook who proved this conjecture while working for Steven Wolfram at Wolfram Research.

For those willing to read the whole thing, I have included a bonus : how the Collatz Conjecture can be simulated using CTS.

# How does a Cyclic Tag System work?

If you think of a cyclic tag system as your CPU then you would have your code as an array of binary words, lets call it \( C = {\alpha}_0{\alpha}_1..{\alpha}_{p-1} \) (same in code above). By binary words I mean a string of 0′s and 1′s. This is your Assembly code, machine language if you like. The \( \alpha_i\)‘s are called appendants. Your data, the input parameter is a binary word, lets call it \( W = {w}_{0}{w}_{1}..{w}_{n} \) (it is the variable ‘word’ in the code above). \( C \) never changes during execution, but we do keep track of which part of the program we are executing with a pointer, lets call it \( k \) (pIndex in code above). The executer of our program cycles through the program in a never ending mannar. Execution halts when the word, \( W\), which is being manipulated during execution (bear with me) is shorter or equal than \( S\), some integer. Each execution step consists of the following actions:

- while |w| > S
- if \( w_0\) = 1
- then \( W = {w}_{1}{w}_{2}..{w}_{n} + {\alpha}_{k} \)
- else \( W = {w}_{1}{w}_{2}..{w}_{n} \)

- \( k = (k + 1) \mod p\)

- if \( w_0\) = 1

**Example 1:**

\( C = 0, 1\) , \( W = 001 \) , \( S = 1 \)

Step # k W 1 0 001 2 1 01 3 0 1

The execution halts when the length of the word is 1.

**Example 2: **

\( C = 10, 101 \), \( W = 10 \) , \( S = 1 \)

Step # k W 1 0 10 2 1 010 3 0 10 ...

Here, in every odd state the first appendant is used and in every even state the second is ignored and we have an endless loop which never halts.

# Turing Completeness

In order to prove that something is Turing-Complete one should show that it can emulate a Universal Turing Machine (UTM). If it can, it can do anything a UTM does and thus universal, this is the Church-Turing Thesis. Intuitively it will be as general purpose as your Desktop, iPhone, and favorite programming language. Now, you can directly show that something can emulate UTM, but it is sometimes more convenient to show that a model can emulate another Turing-Complete model. Computational capacity is a transitive relation. If A emulate a UTM and B emulates A so B emulates a UTM.

Cook showed that Rule 110 can emulate an UTM by going through 2 steps. He first showed that a construction by Emil Post called a 2-tag system can be emulated by a CTS and then he showed that Rule 110 can emulate a CTS; thus proving the claim. There is actually another proof of CTS universality published by Neary and Woods in 2006, 2 years after Cook’s first proof. They use a novel model, a Clockwise Turing Machine which is Turing-Complete instead of a 2-tag system. Cook’s original proof has an exponential time scale up. Using a Clockwise Turing Machine only a polynomial scale up was achieved which is quite remarkable. The proof by Neary and Woods is quite complex and the eager reader is referred to their paper. I will review Cook’s very intuitive and short proof.

## 2-Tag System

A 2-tag system has an alphabet \( A \) and a set of Production Rules \( P:A\rightarrow A^* \). The computation is very similar to the circular tag system. We have an initial word \( W={w}_{0}{w}_{1}{w}_{2}..{w_n} \). At each step we check if the word is 2 symbols or more in length. If it is we delete 2 letters from the left side of the word \( {w}_{0}{w}_{1} \) and append \( P({w}_{0}) \) to the right side of the word, otherwise we halt.

**Example 1:**

\( A = {a, b}\) , \( P(a) = {}’{bb}{}’\) , \( P(b) = ”\) with \( W = {}’{aaa}{}’\)

Step # W 0 aaa 1 abb 2 bbb 3 b

**Example 2:**

\( A = {a, b}\) , \( P(a) = {}’ab’\) , \( P(b) = ”\) with \( W = {}’ab{}’\)

Step # W 0 ab 1 ab ...

just like in the second example of CTS, the execution here never halts and the state of the system always cycles.

Python code of the first example:

P = {'a' : 'bb', 'b' : ''} word = 'aaa' S = 1 while len(word) > S: word = word[2:] + P[word[0]] |

the implemetation here is even simpler than the CTS’.

## Cyclic Tag System Can Emulate 2-Tag System

Suppose we have a 2-tag system with \( A = {a}_{1}{a}_{2}{a}_{3}..{a}_{k}\) we can encode each character in a binary manner in following way \( T({a}_{i}) \rightarrow 0..010..0 \) where the \( 1\) is in position \( i\). The program \( C = {\alpha}_0{\alpha}_1..{\alpha}_p\) will be constructed in the following manner: If \( P(a_i) = a_{i1}a_{i2}..a_{in_i}\) for each \( a_i\) we set \( \alpha_{i-1} =T(a_{i1})T(a_{i2})..T(a_{in_i}) \). We would also add \( k\) empty appendants to \( C\) and overall we have \( |C| = 2k\).

The proof: First, notice that each time the CTS starts reading a sequence of k characters from the word it will be at the beginning of \( C\) or half-way through it, at the beginning of the \( k\) additional empty appendants we added to \( C\).

If \( pIndex = 0\) thus points to the beginning of \( C\) it will encounter a single 1 while going through the word when at position \( i-1\) which corresponds to the \( i^{th}\) symbol of the 2-tag system and appends \( T(a_i)\) to the word. The CTS will go through 0′s until it reaches position \( pIndex= k-1\)

If \( pIndex= k-1\) it will delete \( k\) letters from the word and append empty strings to the word and in essence ignore the character represented by those \( k\) binary symbols in the word. It will then cycle to the beginning of \( C\) and we find ourselfs in the previous paragraph.

If we set \( S = k\) It is easy now to see that the constructed CTS emulates the 2-tag system perfectly.

The following python code is an implementation of the conversion above with the parameters from the 2-tag system and input in example 1.

#Conversion def TwoTagSymbolToBinaryWord(A, s): idx = A.index(s) return ('0' * idx) + '1' + '0' * (len(A) - idx - 1) def TwoTagWordToBinaryWord(A, w): t = '' for i in xrange(len(w)): t += TwoTagSymbolToBinaryWord(A, w[i]) return t def TwoTagToCTS(A, P): C = [] for i in xrange(len(A)): C.append('') C[i] += TwoTagWordToBinaryWord(A, P[A[i]]) for i in xrange(len(A)): C.append('') return C, len(A) #2-Tag System A = ['a', 'b'] P = {'a' : 'bb', 'b' : ''} #Input for 2-tag word = "aaa" #convert C, S = TwoTagToCTS(A, P) wordCTS = TwoTagWordToBinaryWord(A, word) print "S: " + str(S) print "C: " + str(C) print "Input: " + wordCTS print "step #\tpIndex\tword" #Run and print CTS step = 1 pIndex = 0 #CTS Step def DoCTSStep(word, C, pIndex): w0 = word[0] word = word[1:] if (w0 == '1'): word = word + C[pIndex] pIndex = (pIndex + 1) % len(C) return word, pIndex print str(step) + "\t" + str(pIndex) + "\t" + wordCTS while len(wordCTS) > S: wordCTS, pIndex = DoCTSStep(wordCTS, C, pIndex) step+=1 print str(step) + "\t" + str(pIndex) + "\t" + wordCTS |

The code outputs the following (with comments)

S: 2 C: ['0101', '', '', ''] Input: 101010 step # pIndex word 1 0 101010 =aaa 2 1 010100101 3 2 10100101 deletes the second symbol 4 3 0100101 5 0 100101 =abb 6 1 001010101 7 2 01010101 deletes the second symbol 8 3 1010101 9 0 010101 =bbb 10 1 10101 11 2 0101 deletes the second symbol 12 3 101 13 0 01 =b

As expected the code halts and simulates the 2-tag system run.

## 2-Tag System Can Emulate A Turing Machine

There are actually at least 3 different proofs for the universality of tag systems. The first was provided by Minsky in 1961 and the second by Cooke and Minsky 2 years later in 1963. The third proof was provided by Cook in his paper on the universality of Rule 110 from 2004.

The two later proofs are the simplest IMHO. The reader may follow both in the original papers, they are not long. They are too technical, however inspiring, for this scope.

# Bonus: The Collatz Conjecture with 2-Tag System

Using the correct configuration, Liesbeth De Mol, showed in her paper from 2008, how the Collatz conjecture can be reproduced in a tag system. A reminder: the conjecture asserts that the following sequence will always terminate with 1. If \( n\) is odd, the next element in the sequence is \( 3n+1\). If even the next element is \( n/2\). It has been long standing since 1937 when first proposed by Lothar Collatz.

We encode a natural number with \( n\) a’s. ‘b’, and ‘c’ will also be included in the alphabet. The production Rules are as follows: \( P(a) = {}’bc{}’\) , \( P(b) = {}’a{}’\) , \( P(c) = {}’aaa{}’\). It should terminate with ‘a’ or ’100′ in CTS jargon. Voila!

A = ['a', 'b', 'c'] P = {'a' : 'bc', 'b' : 'a', 'c' : 'aaa'} |

S: 3 C: ['010001', '100', '100100100', '', '', ''] Input: 100100100 step # pIndex word 1 0 100100100 2 1 00100100010001 3 2 0100100010001 4 3 100100010001 5 4 00100010001 6 5 0100010001 7 0 100010001 8 1 00010001010001 9 2 0010001010001 10 3 010001010001 11 4 10001010001 12 5 0001010001 13 0 001010001 14 1 01010001 15 2 1010001 16 3 010001100100100 17 4 10001100100100 18 5 0001100100100 19 0 001100100100 20 1 01100100100 21 2 1100100100 22 3 100100100100100100 23 4 00100100100100100 24 5 0100100100100100 25 0 100100100100100 26 1 00100100100100010001 27 2 0100100100100010001 28 3 100100100100010001 29 4 00100100100010001 30 5 0100100100010001 31 0 100100100010001 32 1 00100100010001010001 33 2 0100100010001010001 34 3 100100010001010001 35 4 00100010001010001 36 5 0100010001010001 37 0 100010001010001 38 1 00010001010001010001 39 2 0010001010001010001 40 3 010001010001010001 41 4 10001010001010001 42 5 0001010001010001 43 0 001010001010001 44 1 01010001010001 45 2 1010001010001 46 3 010001010001100100100 47 4 10001010001100100100 48 5 0001010001100100100 49 0 001010001100100100 50 1 01010001100100100 51 2 1010001100100100 52 3 010001100100100100100100 53 4 10001100100100100100100 54 5 0001100100100100100100 55 0 001100100100100100100 56 1 01100100100100100100 57 2 1100100100100100100 58 3 100100100100100100100100100 59 4 00100100100100100100100100 60 5 0100100100100100100100100 61 0 100100100100100100100100 62 1 00100100100100100100100010001 63 2 0100100100100100100100010001 64 3 100100100100100100100010001 65 4 00100100100100100100010001 66 5 0100100100100100100010001 67 0 100100100100100100010001 68 1 00100100100100100010001010001 69 2 0100100100100100010001010001 70 3 100100100100100010001010001 71 4 00100100100100010001010001 72 5 0100100100100010001010001 73 0 100100100100010001010001 74 1 00100100100010001010001010001 75 2 0100100100010001010001010001 76 3 100100100010001010001010001 77 4 00100100010001010001010001 78 5 0100100010001010001010001 79 0 100100010001010001010001 80 1 00100010001010001010001010001 81 2 0100010001010001010001010001 82 3 100010001010001010001010001 83 4 00010001010001010001010001 84 5 0010001010001010001010001 85 0 010001010001010001010001 86 1 10001010001010001010001 87 2 0001010001010001010001100 88 3 001010001010001010001100 89 4 01010001010001010001100 90 5 1010001010001010001100 91 0 010001010001010001100 92 1 10001010001010001100 93 2 0001010001010001100100 94 3 001010001010001100100 95 4 01010001010001100100 96 5 1010001010001100100 97 0 010001010001100100 98 1 10001010001100100 99 2 0001010001100100100 100 3 001010001100100100 101 4 01010001100100100 102 5 1010001100100100 103 0 010001100100100 104 1 10001100100100 105 2 0001100100100100 106 3 001100100100100 107 4 01100100100100 108 5 1100100100100 109 0 100100100100 110 1 00100100100010001 111 2 0100100100010001 112 3 100100100010001 113 4 00100100010001 114 5 0100100010001 115 0 100100010001 116 1 00100010001010001 117 2 0100010001010001 118 3 100010001010001 119 4 00010001010001 120 5 0010001010001 121 0 010001010001 122 1 10001010001 123 2 0001010001100 124 3 001010001100 125 4 01010001100 126 5 1010001100 127 0 010001100 128 1 10001100 129 2 0001100100 130 3 001100100 131 4 01100100 132 5 1100100 133 0 100100 134 1 00100010001 135 2 0100010001 136 3 100010001 137 4 00010001 138 5 0010001 139 0 010001 140 1 10001 141 2 0001100 142 3 001100 143 4 01100 144 5 1100 145 0 100

**References**

M. Minsky, “Recursive Unsolvability of Post’s Problem of ‘Tag’ and Other Topics of Turing Machines”, 74, no. 3, pp. 437-455; November 1961.

J. Cooke and M. Minksy, “Universality of TAG Systems with P=2″, AI Memos 52, MIT, MA; 1963.

M. Cook, “Universality in Elementary Cellular Automata”, Complex Systems, vol 15 pp. 1-40; 2004.

T. Neary, D. Woods, “P-completeness of cellular automaton Rule 110″, Proceesings of ICALP 2006, Lecture Notes in Computer Science, pp.132-143, vol 4051, Springer, Berlin; 2006.

L. De Mol, “Tag Systems and Collatz-Like Functions”, Theoretical Computer Science, vol. 390, issue 1, pp.92-101, January 2008.

This entry was posted by Bar Vinograd on November 24, 2012 at 3:20 pm, and is filed under . Follow any responses to this post through RSS 2.0.You can leave a response or trackback from your own site.

Didn't find any related posts :(

Memming2 years agoTypo: Curch -> Church