A cyclic tag system in Haskell
Table of Contents
Background #
I came across cyclic tag systems from a Code Golf StackExchange challenge to make the smallest Turing-complete interpreter possible. One user implemented a cyclic tag system interpreter in Pip. I’m not a code golfer, but I found it interesting how simple they were as a Turing-complete system. Additionally, the implementation almost perfectly fits into a pure functional implementation, so I decided to write one up in Haskell to practice functional programming.
Like the Turing machine’s tape, a cyclic tag system keeps a word of symbols \(0\) and \(1\) as its register. And analogous to the states of a Turing machine, a cyclic tag system has an ordered list of smaller words called productions. At each step, we look at the leftmost character of the register. If the leftmost character is \(0\), nothing is added. If it is \(1\), the current production is appended to the end of the register. In either case, the leftmost character is then removed and the current production moved to the next production in the list. If we’re at the end of our list of productions, we cycle back to the beginning. Here’s an example of my code running a simple one to 15 steps, with productions listed and starting word 010001:
Productions:
["011","1010","111000","1000"]
Output:
010001 at step 0
10001 at step 1
00011010 at step 2
0011010 at step 3
011010 at step 4
11010 at step 5
10101010 at step 6
0101010111000 at step 7
101010111000 at step 8
01010111000011 at step 9
1010111000011 at step 10
010111000011111000 at step 11
10111000011111000 at step 12
0111000011111000011 at step 13
111000011111000011 at step 14
11000011111000011111000 at step 15Tag systems generalize this idea to removing any number of elements from the front per step and having more symbols. To have more symbols, a tag system’s production rules specify per symbol what should be added to the end of the register, but lose the cycling register. It turns out that cyclic tag systems can simulate any tag system and that tag systems are Turing-complete, so cyclic tag systems are Turing-complete1. We can consider our cyclic tag system to halt if it clears the register2 or if it enters a repeating state. For now, I’ve only implemented a halt if the register clears. (There is a way to ensure the register clears when simulating a halting Turing machine, but that’s outside the scope of simply implementing a cyclic tag system.)
Implementation #
Implementing a cyclic tag system requires two data structures: a looping list of lists for the productions, and a linked list for the register. The default Haskell list is a singly linked list, so concatenation is \(O(n)\)3; there are difference lists, which provide \(O(1)\) concatenation but non-constant head access.
Ideally, we’d just use a circular linked list for the productions and a custom singly linked list for the register with an additional pointer to the tail. This would make concatenation \(O(1)\); unfortunately, we can’t work directly with dynamic memory in Haskell like we could in C++, so I went with a naive implementation.
First, define the alphabet and what a word is.
data Alphabet = Zero | One
deriving (Show, Eq)
type Word = [Alphabet]Next, since we’re running a machine, we want a way to encapsulate the state of that machine at any given moment.
-- Encapsulates the state of the system at a snapshot
data State = State [Main.Word] Main.Word Int
| Halted Int
| EmptyThere’s three possible state types I’ve specified here. The first is a valid running state, which has, in order, the list of productions, the current register, and the current step. The next is output when the register runs out, which we’re counting as a halted machine, and tracks the step at which the machine halted. Finally, the last is an empty state for after the machine halted, which is useful since we’ll take advantage of Haskell’s laziness to run the machine for a theoretically infinite number of steps. If the machine halts at step 75 and we asked for 100 steps, the last 25 can just turn up empty instead of crashing.
To make the list of productions, we can use the cycle function to loop a list of productions infinitely. This is the first application of Haskell’s laziness; we have a pure functional infinite list. This only allocates the memory of the original list and loops it back onto itself by setting the end to the original list; since Haskell is lazy, the compiler will only go looking for what’s past the end of the list once it’s accessed, which will only then send the compiler back to the beginning4.
Thus, we can define a list of productions and cycle it, and write our update function with pattern matching assuming we have an infinite list of productions:
update :: State -> State
update (State (p:productions) (Zero:xs) i) = State productions xs (i + 1)
update (State (p:productions) (One:xs) i) = State productions (xs ++ p) (i + 1)
update (State _ [] i) = Halted i
update (State [] xs i) = State [] xs i
update (Halted i) = Empty
update Empty = EmptyThe first two lines after the function definition update a valid state by matching on the first element of the register. The last four are edge cases: the machine halts, the productions are empty (which can only happen with malformed input), or the machine has already halted either one or more steps ago.
Finally, we can run the machine.
machine :: [State]
machine = iterate update initstate
machineout :: [State]
machineout = take (steps + 1) machineWe iterate the update function on the starting state initstate and store it in the array machine. Notice we haven’t specified a number of steps, so machine is actually infinite! Haskell’s laziness lets us keep an infinite number of calculations in this way, and later ask for the number of calculations we actually want to run. The fourth line does just that.
With some extra code to pretty-print the output, a specified system and a main function, we can compile our Haskell script and run a machine. This one will have starting word 10101 and productions [000, 10, 11, 0] and run for 50 steps:
Productions:
["000","10","11","0"]
Output:
10101 at step 0
0101000 at step 1
101000 at step 2
0100011 at step 3
100011 at step 4
00011000 at step 5
0011000 at step 6
011000 at step 7
11000 at step 8
1000000 at step 9
00000010 at step 10
0000010 at step 11
000010 at step 12
00010 at step 13
0010 at step 14
010 at step 15
10 at step 16
0000 at step 17
000 at step 18
00 at step 19
0 at step 20
at step 21
Halted at step 21This one halted at 21 steps, and because of the edge cases, it correctly represented the halt. This tag system halted quickly, but in my testing, most grow quickly and run beyond any amount of steps I have the patience to look through. Modifying the production rules gives us one that runs beyond 50 steps (and will never clear the register):
Expand
Productions:
["010","10","11"]
Output:
10101 at step 0
0101010 at step 1
101010 at step 2
0101011 at step 3
101011 at step 4
0101110 at step 5
101110 at step 6
01110010 at step 7
1110010 at step 8
11001011 at step 9
1001011010 at step 10
00101101010 at step 11
0101101010 at step 12
101101010 at step 13
0110101010 at step 14
110101010 at step 15
10101010010 at step 16
010101001010 at step 17
10101001010 at step 18
0101001010010 at step 19
101001010010 at step 20
0100101001011 at step 21
100101001011 at step 22
0010100101110 at step 23
010100101110 at step 24
10100101110 at step 25
010010111010 at step 26
10010111010 at step 27
0010111010010 at step 28
010111010010 at step 29
10111010010 at step 30
0111010010010 at step 31
111010010010 at step 32
1101001001011 at step 33
101001001011010 at step 34
0100100101101010 at step 35
100100101101010 at step 36
00100101101010010 at step 37
0100101101010010 at step 38
100101101010010 at step 39
00101101010010010 at step 40
0101101010010010 at step 41
101101010010010 at step 42
01101010010010010 at step 43
1101010010010010 at step 44
10101001001001011 at step 45
0101001001001011010 at step 46
101001001001011010 at step 47
0100100100101101011 at step 48
100100100101101011 at step 49
0010010010110101110 at step 50The program I have for now just simulates the cyclic tag system specified in its code. In the future, I may implement reading in a system from the command line or alternate output that simply indicates whether the cyclic tag system halts or not. But for now, it’s a fun little script to mess with a mathematically interesting system.
What it means for something to be Turing-complete is a little confusing. In this case, one can show that for any Turing machine, there is a tag system that can emulate it, and from there, that there is a cyclic tag system that emulates that tag system. So we’re really doing two layers of simulation over the underlying Turing machine. Another interesting note is that Rule 110 can emulate a cyclic tag system, so it’s also Turing-complete. The story behind this particular proof is a good example of how fights over ownership happen in academia. ↩︎
The register clears iff it is only zeroes. For this to happen, assuming the register does not start in a state of all zeroes, at least one production must be all zeroes - otherwise, every time a 1 is hit in the register, another 1 will be added. ↩︎
Repeated left-associative concatenation is \(O(n^2)\) in Haskell lists because the append operation
++loops through the left list. This is our actual time complexity for concatenation; right-associative concatenation would be \(O(n)\), but that would require knowing future concatenations first, which is equivalent to knowing the state of our cyclic tag system before we actually compute it. ↩︎This is called tying the knot in Haskell parlance. ↩︎