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 = α₁α₂…αₚ₋₁ (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 αₖ’s are called appendants. Your data, the input parameter is a binary word, lets call it W = w₀w₁…wₙ (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 manner. 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₀ = 1
then W = w₁…wₙαₖ
else W = w₁…wₙ
k = (k + 1) mod pExample 1
C = [0, 1] W = 001, S = 1
Step # k W
1 0 001
2 1 01
3 0 1The execution halts when the length of the word is 1.
Example 2
C = [10, 101], W = 001, S = 1
Step # k W
1 0 10
2 1 010
3 0 10Here, 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→A*. The computation is very similar to the circular tag system. We have an initial word W = w₀w₁…wₙ. 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₀w₁, and append P(w₀) to the right side of the word, otherwise we halt.
Example 1
A = {a, b}, P(a) = bb, P(b) = ε, W = aaa
Step # W
0 aaa
1 abb
2 bbb
3 bε being the empty word
Example 2
A = {a, b}, P(a) = ’ab’, P(b) = ε, W =
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 for 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₀a₁…aₖ we can encode each character in a binary manner in following way T(aₙ)→0..010..0 where the 1 is in position n. The program C =α₁α₂…αₚ will be constructed in the following manner: If P(aₙ) = aₙ₁aₙ₂…aₙₙ for each aₙ we set aₙ₋₁=T(aₙ₁)T(aₙ₂)…T(aₙₙ). 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=0thus points to the beginning of C it will encounter a single 1 while going through the word when at position n-1 which corresponds to the iᵗʰ symbol of the 2-tag system and appends T(aₙ) 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 ourselves 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, pIndexprint str(step) + "\t" + str(pIndex) + "\t" + wordCTSwhile 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 =bAs 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'}outputs
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 01010001100100100
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 100References
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.
