This is very cool. It's amazing how "simple" something can be and still be Turing-complete.

Also slightly shorter:

  while word[S:]: pIndex, word = (pIndex + 1) % len(C), word[1:] + C[pIndex] * (word[0] == "1")

Or, even shorter,

  while word[S:]: pIndex, word = (pIndex + 1) % len(C), word[1:] + C[pIndex] * int(word[0])

And obviously one can just use one letter variable names/remove whitespace.

Alright. I feel like someone needs to complain about this post. First of all, it's a very interesting topic and worth talking about.

This article is so lacking that I really think it harms more than it helps. A teaching article like this should be laser focused on teaching the subject, not putting jargon in your path, or trying to write the shortest possible code. Or, if you do write the shortest code, go into great detail to accurately explain how it works. The details of this page don't make much sense.

Here are the specific problems that I found:

1. The code doesn't work. I don't know python, but code should work when I try to run it. Ideally, this could should be presented as a function. And it didn't work not because of missing input parameters, but because of a syntax error on the second line.

2. The psuedo-code doesn't work. Consider that line 1.1.2 merely assigns the input word to itself, without modification. This isn't reflected in the python where it looks like the intent is to slice the first element off. Additionally, the variable p is not defined (but I think can be inferred to be the length of the fixed 'C' input parameter).

I suppose I'm annoyed that such an intriguing topic is being mishandled. I recognize the helpful intent, but not matter how helpful the intent when the code is broken and the explanation is wrong, this article would be better off not being on the internet unless it is corrected.

Almost a year ago I tried to see how short of a cyclic tag system I could make in Ruby. The result: https://github.com/elitheeli/stupid-machines/blob/master/sho...

At first I thought this was describing Bitwise Cyclic Tag (http://esolangs.org/wiki/Bitwise_Cyclic_Tag), but it's subtly different. And even simpler, as it turns out. I'm impressed.

"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's not obvious for a non-Pythonista, but the if .. else .. is meant to be on the previous line. It's a ternary conditional like cond?a:b in C (with the condition in the middle).

Yes, they should have broken the line before `word[1:]` so it was clearer.

If this interested you, consider checking out the book A New Kind of Science by Wolfram. It describes tag systems, and a hundred other things that are similarly cool and fun to play with.

I do have great interest in Wolfram point of view. There is still a lot of research to do in this area. It still feels like the second or third lecture in group theory, before you get to the good parts.

The completeness of CTS was also used in the proof of completeness of the 2-state 3-symbol Turing machine.

thanks, I wasn't aware of that. Do you have the reference?

The Wikipedia has some links: http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Tu...