Cyclic Tag: a Turing-completeness proof

[ais523]

Being an esoprogrammer, I couldn't resist the opportunity to prove Rubicon Turing-complete (given infinite playfield space). See http://esolangs.org/wiki/Bitwise_Cyclic_Tag for details (I implemented Cyclic Tag itself, not the bitwise version).

geponod is the interpreter itself. The program is entered at the bottom-right; use A to represent a 0 in the program, 9 to represent a 1 in the program, and 0 to represent a semicolon that separates rules. (Don't forget the final semicolon!) The initial data is entered at the top; for the data, use 8 to represent a 0 in the data, and 7 to represent a 1 in the data.

voladik is a possible setup for the interpreter; it adds the program and data given in the Collatz sequence example on Esolang, and thus calculates (very slowly; it took about 9000 ticks to get the second entry in the sequence) the Collatz sequence starting with 3.

Although there's limited space in the playfield itself, the queue used for the data can easily be extended to be unbounded; you just need to continue the rows of conveyors and downpipes infinitely to the right.

[Bucky]

It was already suspected that one could stack finite state machines (As in kagupun) to produce an arbitrary cellular automaton where each cell has at most 16 states.  Extending the same finite state machine design to accommodate an arbitrary number of states (which one could combine with a pair of queues to form a Turing machine directly) is possible too, but there isn't enough room to demonstrate it.