Cyclic Tag System: 1 Line of Turing-Complete Code

#1

Post by barvinograd » Sat, Nov 24, 2012, 5:39 PM UTC

Cyclic Tag System: 1 Line of Turing-Complete Code
blog.barvinograd.com

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

#2

Post by dbaupp » Sat, Nov 24, 2012, 5:58 PM UTC

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.

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

#3

Post by [deleted] » Sat, Nov 24, 2012, 6:07 PM UTC

[deleted]

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

#4

Post by graue » Sat, Nov 24, 2012, 7:05 PM UTC

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.

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

#5

Post by hippich » Sat, Nov 24, 2012, 7:15 PM UTC

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

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

#6

Post by dbaupp » Sat, Nov 24, 2012, 7:40 PM UTC

hippich wrote: post #5

"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).

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

#7

Post by praptak » Sat, Nov 24, 2012, 7:50 PM UTC

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

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

#8

Post by unoti » Sat, Nov 24, 2012, 8:31 PM UTC

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.

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

#9

Post by elitheeli » Sat, Nov 24, 2012, 9:11 PM UTC

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...

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

#10

Post by fmoralesc » Sat, Nov 24, 2012, 9:42 PM UTC

dbaupp wrote: post #6

hippich wrote: post #5

"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.