4 ms·

Cyclic Tag System: 1 Line of Turing-Complete Code

74 points by barvinograd 14y ago

dbaupp 14y ago
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.
deleted 14y ago
[deleted]
graue 14y ago
At first I thought this was describing Bitwise Cyclic Tag (http://esolangs.org/wiki/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.
hippich 14y ago
"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:]
- dbaupp 14y ago
  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).
  - fmoralesc 14y ago
    Yes, they should have broken the line before `word[1:]` so it was clearer.
praptak 14y ago
The completeness of CTS was also used in the proof of completeness of the 2-state 3-symbol Turing machine.
- barvinograd 14y ago
  thanks, I wasn't aware of that. Do you have the reference?
  - praptak 14y ago
    The Wikipedia has some links: http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine#Proof_of_universality http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Tu...
unoti 14y ago
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.
- barvinograd 14y ago
  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.
elitheeli 14y ago
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/short_cyclic_tag_system.rb https://github.com/elitheeli/stupid-machines/blob/master/sho...
javajosh 14y ago
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.

74 points by barvinograd 14y ago

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.

deleted 14y ago

[deleted]

graue 14y ago

At first I thought this was describing Bitwise Cyclic Tag (http://esolangs.org/wiki/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.

hippich 14y ago

"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:]

dbaupp 14y ago
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).
- fmoralesc 14y ago
  Yes, they should have broken the line before `word[1:]` so it was clearer.

praptak 14y ago

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

barvinograd 14y ago
thanks, I wasn't aware of that. Do you have the reference?
- praptak 14y ago
  The Wikipedia has some links: http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine#Proof_of_universality http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Tu...

unoti 14y ago

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.

barvinograd 14y ago
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.

elitheeli 14y ago

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/short_cyclic_tag_system.rb https://github.com/elitheeli/stupid-machines/blob/master/sho...

javajosh 14y ago

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.