1 of 4

Simulate a Cyclic Tag System

A cyclic tag system is a tiny, Turing-complete computational model consisting of a two-symbol alphabet (I'll use {0,1}), a finite, nonempty cyclic list of production rules that consist of those two symbols, and an unbounded word which also consists of those two symbols.

At each step:

  • the first element in the word is removed
  • if it was 0 the current production is skipped
  • if it was 1 the current production is appended to the end of the word.
  • the next production rule becomes active. If this was the last production rule, go back to the first one.

The system halts when the word becomes empty.

An example (from Wikipedia):

Productions: (010, 000, 1111)
Initial word: 11001

Generation  Production   Word (before)            Word (after)
   0           010           11001             →     1001010       
   1           000            1001010          →      001010000
   2           1111            001010000       →       01010000
   3           010              01010000       →        1010000
   4           000               1010000       →         010000000
   5           1111               010000000    →          10000000
   6           010                 10000000    →           0000000010
   7           000                  0000000010 →            000000010
   8           1111                  000000010 →             00000010
   9           010                    00000010 →              0000010

Your task, if you choose to accept it, is to write a program or function that takes:

  • a list of productions,
  • the initial word, and
  • a generation,

and prints or returns the word at that generation.

For example,

      gen=4) => [1,0,1,0,0,0,0]

Implementation details:

  • The alphabet does not matter. You may use 0 and 1, True and False, T and NIL, A and B, or even 1 and 0, or whatever else you may come up with, as long as you are consistent. All input and output must use the same alphabet, and you must indicate what you are using for 0 and what for 1.

  • The length of the word must be theoretically unbounded. That is, you may not hardcode a maximum word length. If I run your program on an ideal computer with an infinite amount of memory, your program must theoretically be able to make use of it. (You may ignore your interpreter's/compiler's limits.)

  • If the given system halts before the given generation is reached, you must return or print the empty word.

  • The empty production exists, and you must be able to handle it. If you write a full program, your I/O must also be able to handle it.