Cyclic Tag System : 1 Line of Turing-Complete Code
2The 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.
Rule 110 in action (from Cook’s paper)
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 
- while |w| > S
- if
= 1
- then
- else
- then
- if
Example 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:
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 
Example 1:
Step # W 0 aaa 1 abb 2 bbb 3 b
Example 2:
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 
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
If 
If 
If we set 
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 Cojecture 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 
XKCD on the Collatz Conjecture
We encode a natural number with
a’s. ‘b’, and ‘c’ will also be included in the alphabet. The production Rules are as follows: 
, 
, 
. 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.
Working with Bitfields in C#
0Bitfields are a great way to maintain an arbitrary collection of bit flags using a single numeric value (usually an integer). For example, when using a System.Thread object in .NET you may want to use the ThreadState property. The property is of the type System.Threading.ThreadState which is an enum decorated with FlagsAttribute. The integer values of the enum are powers of 2 because we want to use the actual bits of the integer to mark different states (see previous post on .NET Integer Representation). Note that the in ThreadState states are not mutually exclusive so you can different states flagged at the same time.
[Flags] public enum ThreadState { Running = 0, StopRequested = 1, SuspendRequested = 2, Background = 4, Unstarted = 8, Stopped = 16, WaitSleepJoin = 32, Suspended = 64, AbortRequested = 128, Aborted = 256 } |
With Int32 we have 32 bits that we can used. An integer indicating that the state is both WaitSleepJoin and AbortRequested (it can happen) will look like that:
Working with bitfields is all about bitwise operations. In order to assert whether the thread is in these two states and exacltly and these two states we can use the following:
t.ThreadState == (ThreadState.AbortRequested | ThreadState.WaitSleepJoin) |
Checking if a bit is on:
(t.ThreadState & ThreadState.AbortRequested) == ThreadState.AbortRequested |
Turning on a bit:
t.ThreadState |= ThreadState.AbortRequested |
What happens if the FlagsAttribute is not used? Consider the following:
enum ColorsEnum { None = 0, Red = 1, Green = 2, Blue = 4, } [Flags] public enum ColorsFlaggedEnum { None = 0, Red = 1, Green = 2, Blue = 4, } |
We have two enums with the same values and same names for the strings but one marked with the flags attribute and the other is not.
Console.WriteLine("Without Flags:"); for (int i = 0; i <= 8; i++) { Console.WriteLine("{0,3}: {1}", i, ((ColorsEnum)i).ToString()); } Console.WriteLine("With Flags:"); for (int i = 0; i <= 8; i++) { Console.WriteLine("{0,3}: {1}", i, ((ColorsFlaggedEnum)i).ToString()); } |
Running the code above will produce the following output:
Without Flags: 0: None 1: Red 2: Green 3: 3 4: Blue 5: 5 6: 6 7: 7 8: 8
With Flags: 0: None 1: Red 2: Green 3: Red, Green 4: Blue 5: Red, Blue 6: Green, Blue 7: Red, Green, Blue 8: 8
Seems that the FlagsAttribute does have some effect. But is it really necessary?
ColorsEnum y = ColorsEnum.Blue | ColorsEnum.Green; Console.WriteLine(y.ToString()); |
Running this code will result in “6″ written on the console. Using dotPeek we have the following for Enum.ToString():
public override string ToString() { return Enum.InternalFormat((RuntimeType) this.GetType(), this.GetValue()); } private static string InternalFormat(RuntimeType eT, object value) { if (!eT.IsDefined(typeof (FlagsAttribute), false)) return Enum.GetName((Type) eT, value) ?? value.ToString(); else return Enum.InternalFlagsFormat(eT, value); } private static string InternalFormat(RuntimeType eT, object value) { if (!eT.IsDefined(typeof (FlagsAttribute), false)) return Enum.GetName((Type) eT, value) ?? value.ToString(); else return Enum.InternalFlagsFormat(eT, value); } private static string InternalFlagsFormat(RuntimeType eT, object value) { ulong num1 = Enum.ToUInt64(value); Enum.HashEntry hashEntry = Enum.GetHashEntry(eT); string[] strArray = hashEntry.names; ulong[] numArray = hashEntry.values; int index = numArray.Length - 1; StringBuilder stringBuilder = new StringBuilder(); bool flag = true; ulong num2 = num1; for (; index >= 0 && (index != 0 || (long) numArray[index] != 0L); --index) { if (((long) num1 & (long) numArray[index]) == (long) numArray[index]) { num1 -= numArray[index]; if (!flag) stringBuilder.Insert(0, ", "); stringBuilder.Insert(0, strArray[index]); flag = false; } } if ((long) num1 != 0L) return value.ToString(); if ((long) num2 != 0L) return ((object) stringBuilder).ToString(); if (numArray.Length > 0 && (long) numArray[0] == 0L) return strArray[0]; else return "0"; } |
This is the route that a Flags decorated enum goes through when ToString is invoked. So the ToString implementation is sugar only, no actual meat involved. In fact one can use simple integers. The enum keyword is only sugar.
Types of Enums
An enum is not nesaccerally an integer, we can have any of the C# integral types except char. From the c# documentation:
The approved types for an enum are byte, sbyte, short, ushort, int, uint, long, or ulong.
http://msdn.microsoft.com/en-us/library/sbbt4032(v=vs.110).aspx
There is absolutely no need to use a signed integer, but it doesn’t hurt either if you work with bitwise operations. You should use only the number of bits required for your state. Use byte if you need 7 states or less. Use Int16 if you need 8-15 states and so on. The all-bits-off state is used for “None” state or something similar.
Performance
The best thing about bitfields is the performance gain compared with other naïve methods (several booleans, dictionary etc.). The increase in performance is twofold. First, memory access. If you use Booleans to store information about an object or any other information you will most likely want to assert the value of these bits in conjunction. An often overlooked optimization is the CPU cache. Assembly:
if (flag1 && flag2 && flag3)
0000011d cmp dword ptr [ebp-0Ch],0
00000121 je 0000013A
00000123 cmp dword ptr [ebp-10h],0
00000127 je 0000013A
00000129 cmp dword ptr [ebp-14h],0
0000012d je 0000013A
{
Console.WriteLine("true");
0000012f mov ecx,dword ptr ds:[03662088h]
00000135 call 049BD3E4
}
Console.ReadLine();
0000013a call 04F84F64 |
When the CPU does a cmp operation, it will try to get it from the CPU cache and if it isn’t there it will go to machine memory and fetch it. When the data is not in the cache we experience a cache-miss. Thumb rule is 10 cycles for using data in the cache and 100 cycles from memory. If you are lucky (or extremely careful) all your bits will be in the same cache line. A cache line is the block the data is fetched in from the memory into the CPU cache. In the above example you might experience 3 cache-misses. If you are using a byte for example as your bit field, the entire state will be loaded into the cache and will require only one memory access. Modern CPUs have 32-64 byte cache lines. Assembly:
if (myColor == (ColorsEnum.Blue | ColorsEnum.Green))
000000f3 cmp dword ptr [ebp-0Ch],6
000000f7 jne 00000104
{
Console.WriteLine("true");
000000f9 mov ecx,dword ptr ds:[032F2088h]
000000ff call 0485D3E4
}
Console.ReadLine();
00000104 call 04E24F64 |
Not only we have 2 instructions instead of 6, we do only one memory access. These numbers will hold for any number of bits and any combination of states the enum is in. ‘Nough said, bitfields rock.
Syntactic
0Syntactic is a visualization project by Omer Shapira and I. Syntactic helps to gather insights on the internal workings of a classification algorithm proposed by Alexander Clark. The algorithm is used in classifying lexical categories such as inflections of to be, place names and verbs with similar syntactic use. It is completely unsupervised and achieves very good results. The input for the algorithm is a very large sentence corpus from which 3-grams are produced. Just like k-means, the amount of clusters is predefined. In the first stage it takes the k most common words and assigns a cluster for each of them. After that it plays a what-if game: for each of the unsorted words (on the left in the visualization) it calculates the distance using a mutual entropy “metric” and then assigns some words to their appropriate clusters. The general idea is that two words belong to the same cluster if their left and right contexts are similar enough – hence the 3-grams. The algorithm is iterative and the number of iterations is not deterministic. It will run until all the words are sorted. The algorithm was implement by Omer in Roni Katzir’s seminar on linguistic learnability we both attended in Tel-Aviv University. Implementation in java and further information is avaliable here.
The visualization of the context distributions is the main issue. We used a canvas where each of the contexts (there are (k+1)^2) is represented by a square which it lit with respect to the metric. We have tested the results and found it unsatisfactory since the data was too sparse, linear luminosity was too dark. First we normalized the data so a minimum value is considered as 0 – that is most of the data. We divided all the values by the maximum value so we will have an array of values ranging from 0 to 1. This was the linear part. We calculated the median value 
Omer designed the visualization and did a great job. I especially liked the help feature, it is extremely intuitive and I have never seen a similar solution. When you click on the question mark, this is what you get:
Working with Omer was a great fun, thank you Omer, live long and prosper.
dotPeek – JetBrains’ free alternative for Red Gate’s .NET Reflector
1dotPeek has many of the basic features of .NET Reflector. When you fire it up for the first time it might take a few minutes until it warms up. It will load with the main assemblies of .NET.
Code View
The System.IO.Stream class:
On the left is the list of classes and other .NET objects group by Assemblies and then by like in Reflector. On the right you will find the disassembled code. I really like the tabbed view, it is really nice when you drill down or compare different classes.
Download Symbols
With dotPeek you can download symbols from Microsoft’s symbol server:
Find Usages
dotPeek, like .NET Reflector has a “Find Usages” feature:
At this point .NET reflector is better, it groups the results based on the type of usage which is often the what we actually want from this view while dotPeek is more dependency oriented. That one I didn’t like. This view in .NET Reflector was one of the best features and I think dotPeek did it the wrong way.
Loading Assemblies
You can choose to load assemblies by browsing or loading it from GAC: 
You can also see the file structure view on the right. I think it is a great bonus. The file structure shows the same data as in the tree on the left but it is much easier to use and it’s also automatically refreshes when you go through tabs. Nice!
Summary
One other thing dotPeek is missing is a plugin framework. .NET Reflector had some great plugins and that it is a something I definitely want to see in the future.
All in all I am very pleased with the new dotPeek and JetBrains. This is a great example for a supply and demand situation, JetBrains will definitely earn some points for that.
Keep in mind that this is an early access version and much will change and improve on the final version.