Turing machine (finitely initialized, halts) implementing an encoding of Grill Tag, 2 states, 14 symbols, 232 bytes
We've had a few answers implementing Turing machines in various languages. Time to go the other way, and implement a language in a Turing machine. (A lot of time… I started working on this problem in 2019, and only proved Grill Tag, the implemented language, to be Turing-complete just now.)
0 e e r 1
0 P p l 0
1 P p r 1
0 p P l 0
1 p q r 0
0 q P r 1
* > < r *
0 < > l 0
1 < < l 0
0 i a r 0
1 i < l 1
0 I A r 0
1 I < r 0
0 a x l 0
1 a i l 1
0 A X l 0
1 A I l 1
* X a r *
* x A r *
0 _ o l 0
1 _ _ l halt
0 o _ l 1
1 o A r 0
Try this program in an online simulator
Something that needs to be made clear, because the details can make a huge difference to the size of a universal Turing machine: the problem I'm solving here is the problem of creating a universal Turing machine where the program to implement is specified using a finitely initialized tape (i.e. all but finitely many cells are blank), and for which the Turing machine halts when the implemented program halts. It is possible for a Turing machine to be much smaller if, e.g., you allow for an infinite repeating pattern on the tape, and work out whether the program "should have halted" by inspecting the tape rather than by using a halt state, but that is effectively an entirely different problem (and both are interesting).
As far as I can tell, the previous record for a 2-state Turing machine was 18 symbols, so unless there's been some development I've missed since, this is a huge proportion golfed off a very long-standing mathematical problem.
You can encode a Grill Tag program and initial string into an initial tape for this Turing machine using this Jelly program (the last line of output is the initial tape, the other lines are debug output). The program is specified in the RLE syntax, and its initial queue in JSON (with the head at the start of the array).
The implemented language
Grill Tag is a variant of cyclic tag in which all productions have an odd length, start and end with 0, and alternate between 0 and 1. In other words, the only valid productions are
0101010, and longer strings that follow the same pattern.
In case you don't know what cyclic tag is, the language works like this: there is a queue of bits, which handles all the data storage for the program; and a program, which runs in an infinite loop forever until/unless the queue becomes empty. Each program command, known as a "production", dequeues a bit from the front of the queue, then enqueues either something (if a 1 bit was dequeued) or nothing (if a 0 bit was dequeued) to the back of the queue – the only freedom you have when writing the program is in specifying what exactly it is that gets enqueued. In the full version of cyclic tag, you can enqueue any arbitrary sequence of bits, but Grill Tag is restricted to using
010…010-style sequences ("grills") only.
Grill Tag is something that I've been looking at as a potential target for interpreter golf for several years now. However, back in 2019 when I created it, I wasn't able to determine whether or not it was Turing-complete; the language has a fundamental issue that make it very hard to program in (the number of 0s minus the number of 1s in any given string is equal to the number of 1s in the string that produced it, which means that programming in it requires controlling both the length and the 0/1 ratio of everything you use in order to keep control of which productions the 1s will expand).
I have very recently proven it Turing-complete, via creating a Turing-complete language (Genera Tag) in which you can write programs where every symbol expands in a very regimented way: every symbol always expands into two symbols in the next generation, each of those expands into another two symbols, and so on. Unfortunately, this construction tends to cause a useless explosion of no-ops (one no-op expands into two, then four, then eight, etc.) and makes programs run very slowly, but that is not an obstacle to Turing-completeness (and is probably not inherent in the language, but just trying to find anything that works was hard enough – I'm not immediately planning to go looking for something more efficient, even though it probably exists).
A decomposition of Grill Tag
As described above, Grill Tag has some fairly complex commands ("pop, and conditionally append
… if a 1 bit was popped"). However, it is possible to break it down into smaller pieces, in a way that's quite suitable for a simple language like a Turing machine to handle.
The first observation (which is a standard transformation which I learned from Bitwise Cyclic Tag) is that instead of appending to the end of the queue all in one go, it is instead possible to split it up and push bit by bit: "dequeue a bit, and if it was a 0 bit, ignore any commands that would enqueue to the queue until the next bit is dequeued", "enqueue a 0 bit", "enqueue a 1 bit". The existence of the first command here effectively leads to two global states, which I think of as "blocked" and "extending"; in a blocked state, enqueuing commands do nothing, and in an extending state, they enqueue onto the back of the queue. This is still 3 commands, though, which is not ideal for implementing in a 2-state Turing machine (it's possible, but you need to add a lot of extra symbols to remember the half-command that you've seen already).
The second observation is that, in order to reach the far end of the queue, a Turing machine has to move its head over the entire queue as it does so (and generally speaking it's terser to have the "growing" end of the queue – the tail – at the opposite end from where the program is stored, so that it doesn't end up crashing into the program or forcing you to move the program out of the way). That gives it an opportunity to make simple changes as it goes, like, say, inverting the queue by flipping every bit in it. So instead of "dequeue and possibly block", "enqueue 0", "enqueue 1", it's possible instead to use "dequeue and possibly block", "enqueue 1", "invert the queue" (with an enqueuing of 0 implemented as an invert, enqueueing of 1, and another invert).
Look at what happens when using this decomposition on grills, rather than arbitrary strings:
0: dequeue/block; invert; enqueue 1; invert
010: dequeue/block; invert; enqueue 1; invert; enqueue 1; invert; enqueue 1; invert
01010: dequeue/block; invert; enqueue 1; invert; enqueue 1; invert; enqueue 1; invert; enqueue 1; invert; enqueue 1; invert
Every second command is an
invert command, so they can be paired with the preceding (or subsequent) commands in order to create a language that has only two commands, rather than three. I chose to pair them with the subsequent commands, meaning that Grill Tag can be implemented using only two commands:
- invert, then dequeue/block
- invert, then enqueue 1
(These commands actually give you a little more power than Grill Tag has – I made a catalogue of "languages that might be good to implement in low-powered languages and might be Turing-complete" back in 2019, and codenamed the full version of this language
a vd vt. The extra power of
a vd vt is not needed, though, with Grill Tag being Turing-complete on its own.)
Now that there are only two commands, it is possible for the Turing machine to remember which command it is executing via using its two states – it no longer needs to store a "half-command" onto the tape to remember what it's doing.
In the next section, I discuss how
a vd vt (thus Grill Tag) is implemented in the Turing machine.
How the Turing machine works
This is a program of two halves, each of which does something sensible in isolation: the "left half" that uses the four symbols
epPq, and the "right half" that uses the other ten symbols (including the "blank tape" symbol). The left half stores the program; the right half stores the queue, and implements the logic of Grill Tag.
Let's look at the right half of the program first. This is an implementation of all of Grill Tag other than the routines for determining what the next Grill Tag command is (which are implemented by the left half of the program).
The part of the tape used by this half of the program consists of a section of
> symbols, followed by the tape, and possibly an
o at the end (and beyond that is blank tape forever). The queue is encoded very directly: the head of the queue is towards the left-hand side of the tape (with the tail being at the right-hand side), and uses states represented by capital letters to encode 1 bits and states represented by lowercase letters to encode 0 bits. This part of the program is, in effect, a state machine; it remembers which state it is in by using different pairs of symbols to represent the queue (either
The only requirement that the right half of the program makes on the left half is that it can ask for commands. To ask for a command, it moves the tape head to the left out of its own section of the program, in state 0. The left half of the program responds with a command, returning the tape head in state 1 for an "invert and enqueue" command, or state 0 for an "invert and dequeue" command. There are a couple of quirks:
- After a returning a 0 command, the next "ask for a command" must, instead of returning the next command in the program, unconditionally return in state 1.
- Every second 0 command is implemented as unconditionally blocking the queue, rather than inverting and dequeuing a bit. This can be worked around by adding a sequence of dummy commands after each original 0 command: arbitrarily many 1 commands in the program, followed by one 0 command (to unblock the queue and dequeue the bit that should have been dequeued by the original 0 command).
These quirks are present because they allow the Turing machine to be smaller, and the workarounds don't hurt its universality. (In fact, each of the quirks has positive (or at least simplifying) impacts on both halves of the Turing machine, which is something of an amazing coincidence.) The reasoning behind them, and the way that they benefit the construction, will be explained in the appropriate sections below.
Apart from storing the queue, the right half of the Turing machine is effectively just one state machine, with a few hardcoded states.
Below, I take a look at every state. If you'd prefer to read the description in Jelly rather than English (maybe to have something to compare the Turing machine to), I have a Jelly implementation of the state machine available (which implements the program queue itself rather than asking the left half of the tape).
The idle state happens a) at the start of the program, b) immediately after a 0 command. In this state, the right half of the Turing machine consists of an arbitrary number
> symbols, followed by the queue written with
iI (which could be any combination of lowercase
i and capital
I, reflecting the 0 and 1 bits that make up the queue).
In this implementation, a 0 command does not actually dequeue the first bit of the queue immediately. Instead, it sets the state to idle, and then allows the implementation of the idle state to handle dequeuing the bit of the queue.
The idle state is intended to run immediately after a 0 command, at a time when the left half of the tape is unconditionally returning control in state 1 (rather than reading a command from the program); the Jelly implementation unconditionally rotates the program to emulate this. That means that the idle state will be entered in state 1 (and this is the reason why the "always 1 after 0" quirk is helpful to the right-hand half – it ensures that the idle state is entered with the Turing machine in the correct state, necessary because the idle state wouldn't work properly in Turing machine state 0).
The Turing machine proceeds to move along the row of
>, changing them to
< and remaining in state 1 (per the rules for
>). When it reaches the end of the row of
>, one of three things happens:
The next symbol could be
i. In this case, the
< and the head moves left, remaining in state 1. It will move to a
<, which remains as
<, moves the tape head to the left and changes to state 0. In state 0, the machine will change all the remaining
< back to
> and pass control to the left half in state 0.
The machine has dequeued a 0 from the queue (a lowercase letter became a filler symbol
<), and entered a double-blocked state (
>>>…>>><<). This dequeues a symbol (as required), and blocks the queue (also as required when a 0 bit is dequeued).
The next symbol could be
I. In this case, the
<, the head moves to the right, and the Turing machine enters state 0. In state 0,
a, with the head moving to the right over the entire queue; the queue is becoming active. When it reaches the end of the queue, the Turing machine is in mark as extending state. This dequeues a symbol (as required), and does not block the queue (as required when a 1 bit is dequeued). The mark as extending state will handle marking the queue as extending.
The queue could be empty – there might be no next symbol. In this case, beyond the last
> will be an empty portion of the tape. The rule for empty tape is to halt in state 1, and we will be in state 1, so this correctly emulates a halt; Grill Tag halts when the queue is empty, and so does the Turing machine.
Blocked and double-blocked
The blocked and double-blocked states are very similar to each other. They handle situations where enqueue commands should be ignored, either because a 0 was dequeued, or due to the quirk where every second 0 command unconditionally blocks the queue.
A double-blocked state effectively says "the last 0 command blocked the queue, and the next 0 command should block the queue as well" – this is used to remember the fact that after a "regular" block of the queue when a 0 command dequeues a 0 bit in idle state, a "quirky" block is required on the next 0. A blocked state is one in which the last 0 command blocked the queue, but the next 0 command should be processed normally. As such, a 0 command changes the state from double-blocked to blocked or blocked to idle. 1 commands are entirely ignored in this state, because its entire purpose is to discard inverts and enqueues.
The blocked and double-blocked states read commands from the program – they are entered from the left half of the program. When either state is initially entered, it will be after a 0 command was read, so there will be a spurious 1 command arriving – but that quirk is irrelevant here, because the states discard 1 commands anyway. So all they actually have to do is to wait for a 0 command, and then remove one blockage upon receiving it.
There are two possibilities for what could happen, because the left half of the program could give this half control in either state 0 or state 1. In either state, the machine moves along the row of
>, changing them to
<, while remaining in the same state. When it reaches the
<, there are two possibilities.
- In state 1, with a 1 command (or spurious-1-after-0) having been read from the program, the
< remains unchanged and moves the head back to the left in state 0 (as per the rules for
<). The rest of the row of
> will be flipped back to
<, and control will move to the left half of the program in state 0 (asking for a new program command). In other words, nothing changes other than a new command is being requested; in particular, the row of
< ends up exactly as it started, so the machine will remain in blocked or double-blocked state (whichever it was in previously).
- In state 0, with a 0 command having been read from the program, everything is almost the same as in state 1; however, the rule for
< in state 0 is to change to
> and remain in state 0 (rather than remaining as
< and changing to state 0). Thus, everything ends up the same, except that the machine has changed from double-blocked to blocked or blocked to idle state (because the only difference between the representation of those states is the number of
< at the rightmost end of the
Mark as extending
The mark as extending state is used to produce the correct representation of the queue for extending state. It is entered with the Turing machine in state 0, with the tape head in the blank space to the right of the tape.
This one works very simply: the rule for blank space (
_ in the notation used by the interpreter I chose) in state 0 is to write an
o, then move the head to the left in state 0.
<aA's rules for state 0 all move the head to the left, with
X. The content of the queue has remained unchanged, the head has moved to the left in state 0 (reading the next command) and now the machine is in extending state.
The extending state is used to handle the "invert" half of commands, in cases where the queue is not blocked.
The extending state can be entered with the Turing machine in either state 0 or state 1 – a command has just been read from the program. The rules for
X are basically the same between the two states: they leave the Turing machine in the same state, but otherwise the state doesn't matter (it's just remembered so that the
o at the end of the tape knows which command to implement the second half of).
X all move the head to the right, in both state 0 and state 1.
a. This mapping of lowercase to capital and capital to lowercase letters is inverting the sense of the queue; 0 bits become 1 bits and vice versa. The machine is now in enqueue or stop extending state.
<<<…<<<aAAaa…Aaao[head] in state 1
The enqueue state is entered from extending when a 1 command was read (and thus the Turing machine is in state 1), with the head over the
o at the end of the tape. This is the simplest state in the entire machine, implemented by a single Turing machine transition: the
o becomes an
A (writing a capital letter at the end of the queue and thus enqueueing a 1 onto it), and the head moves to the right, onto the blank space beyond the queue. The Turing machine is now in mark as extending state, which will set the tape back to the format it was in before the "invert and enqueue" command ran – but the tape has now been inverted (because extending inverts the queue but mark as extending does not invert it back), and then an
A (which becomes an
X during mark as extending) was appended to the end.
<<<…<<<aAAaa…Aaao[head] in state 0
The stop extending state has an identical tape to enqueue, and the head is likewise over the
o, but the Turing machine is in a different state. The purpose of this state is to bridge between the "invert" and "dequeue" halves of an "invert and dequeue" command – the "invert" half leaves the head at the rightmost end of the tape, but the "dequeue" command needs the head at the left, so the stop extending state is used to move the head into the correct location and appropriately re-encode the queue as it goes.
o at the end of the queue deletes itself (which is what the rules for
o do in state 0), switching to state 1 and moving the head back onto the last
Then, the head moves back leftwards over the queue, remaining in state 1 (
A leave the state the same), with
I – the queue encoding is going back to the encoding used for idle.
When the head moves back to the
<, the logical thing to do (and the obvious thing to try to implement) would be to change the
< back to
>, and enter idle state (which implements the "dequeue" half of an "invert and dequeue" command). Unfortunately, golfing the Turing machine down to only 14 symbols ended up making the logical and obvious behaviour impossible to fit in, so the machine does something else instead;
< in state 1 remains
< and moves to the left, changing to state 0. The remaining
< do change back to
>, though (now that the machine is in state 0), so the resulting queue state consists of arbitrarily many
<, and the queue encoded with
iI – in other words, this is blocked state!
This explains the quirk in which every second 0 command unconditionally blocks the queue, rather than doing an invert-and-dequeue like it's supposed to. If a 0 command runs when the queue is unblocked, then stop extending will end up inverting and then blocking the queue – it's the next 0 command that will actually do the dequeue (so the invert happens when it's supposed to, but the dequeue is delayed until the next 0 command). I couldn't find a terse way to avoid this behaviour. However, it was trivial to change the behaviour of a 0 command that blocks the queue to match (by making it double-block the queue rather than merely blocking it), in order to produce a construction in which every second block of 111…1110 in the program is consistently ignored (a quirk that is trivial to work around if you know it exists, simply by adding dummy commands).
That concludes the entire functionality of the right hand half of the program: enqueuing, dequeuing, inverting and halting. Apart from the weirdness of stop extending becoming blocked rather than idle (requiring a double-blocked state to compensate), everything is fairly straightforward and intuitive, and you can generally immediately understand what it's doing in the simulator.
Unfortunately, the left half will be a whole lot weirder and harder to understand – unlike the right half, it wasn't constructed, but rather discovered. Let's take a look at how it works.
The left half of the program uses only 4 of the 14 symbols (
q), and in fact only 6 of the 8 transitions are used (the other two do not have a rule defined because they never occur). Its purpose is to store the program, which it does by producing a specific, endlessly repeating stream of "state 0" and "state 1" signals; whenever the tape head enters it from the right (in state 0 – the right half always sets the state to 0 when giving the left half control), it will return the tape head to the right in either state 0 or state 1, whichever is the next element in the sequence.
First, let's take a look at what the rules actually do. The structure of the left half of the tape, when the tape head is outside it, is always of one of the following two forms (where
P can be arbitrarily mixed):
Let's consider the first of these forms, and what happens when the tape head enters it in state 0. While moving to the left, the behaviour is fairly simple;
P, and vice versa, with the machine remaining in state 0. When it reaches the
e, it changes to state 1 and moves back to the right.
When moving rightwards, things are more complex. A
P becomes a
p, moves to the right, and remains in state 1; in other words, it undoes the inversion that was done when moving to the left, restoring the symbol to its original state. However, a
p has a much weirder rule: it becomes a
q and moves to the right, while switching to state 0. This has the effect of inverting the symbol to the right (because both
P, when encountered in state 0, invert), and moving back to the left, onto the
q then becomes
P and moves to the right in state 1, as "normal".
In other words, when moving to the right,
p inverts the symbol to the right and then becomes
P. The result of this is that each cell, when the head leaves it, becomes set equal to the cumulative/running XOR of the original states (i.e. before they were inverted while moving to the left) of all the cells so far. This can be seen inductively. The base case is that the first cell starts out as the inversion of its original value, i.e. the XOR of all the cells so far, i.e. itself. For the inductive case, immediately before a cell changes to
P (i.e. asserting that the XOR of all the cells so far was odd), it inverts the cell to its right, so it ends up being inverted three times and flipping (i.e. it was set to its original value XOR 1 = its previous value XOR that of all the cells to its left), whereas if a cell changes to
p, the cell to its right is inverted only twice (leaving it at its original value, which must be the XOR of all the cells seen so far because the cells to its left XOR to 0).
People familiar with small Turing machines may be familiar with this general algorithm, of using a running XOR to store data. I learned about this pattern from Wolfram's (2,3) Turing machine, which is capable of doing a running-XOR and which uses this mechanism as its primary data storage. In fact, the rules used in this Turing machine were based on those from the (2,3) Turing machine, with all the relevant states and transitions being the same and used for the same purpose (the only difference is the addition of an
e symbol to reflect the tape head, which is required because both transitions of the blank symbol are both being used for other purposes).
One quirk of this method of doing things is the way in which output is produced. When the last symbol becomes a
p (i.e. all the symbols XOR to 0), the output uses a sensible protocol: it just reports the 1 via transferring control to the right half in state 1 (the state numbering is inverted, so a 1 command has to be stored as a 0 and vice versa, but this is not a significant issue because you can just invert the commands before encoding them). When the last symbol becomes a
P (i.e. all the symbols XOR to 1), the head does indeed move to the right half in state 0, informing the right half of a 0 command – but this happens during the "invert the next cell" attempt, when the scan over the program storage has not yet finished. As a consequence, there is a
q at the end of the program storage rather than a
P. The next time control is transferred to the left half, it will finish the scan, changing to a
P and transferring control to the right half in state 1 (which is the state that it would normally use to scan its next cell). The consequence is that each 0 is necessarily followed by a spurious 1. Fortunately, this quirk turned out to be easy to work around in the right-hand half of the program (and it actually simplifies the idle state a little, whilst not having negative consequences on anything else).
Encoding a running-XOR storage
Only one question remains: is it possible to encode a running-XOR storage such that iterating the running-XOR operation will produce any desired sequence of 0s and 1s?
The answer is "not any sequence: there's a restriction". It turns out that the period of a running-XOR storage will always be a power of 2. However, it is possible to construct a running-XOR storage that outputs 0s and 1s in any arbitrary pattern whose period is any arbitrary power of 2. Fortunately, this is a trivial restriction to obey: a quirk in the right half of the program means that every second block of
0111…111 in the output gets entirely ignored, and it is possible to pad out any of these blocks by inserting extra 1s until the length of the program becomes a power-of-2 number of commands.
As for encoding the actual sequence, the encoding algorithm is a fairly simple recursive algorithm:
- The sequence  encodes as ;
- The sequence  encodes as ;
- Otherwise, split the sequence into two equal-length halves A and B, and concatenate (the encoding of A pointwise-xor B) with (the encoding of B).
Proving that this works is a somewhat interesting induction, as the inductive hypothesis needs to include both the encoding rule itself, and the behaviour of a length-2n running-XOR memory if you invert all the storage cells (this causes the running-XOR memory to output the same period-2n sequence except that the last element in the sequence gets inverted). It is most intuitive to think of a running-XOR memory as a length-2n queue whose output is XORed with its input; when entering the memory normally, the last element is dequeued, and both output and enqueued back onto the queue; when entering the memory "inverted" (i.e. with the cells to its left XORing to 1), the last element is dequeued, inverted, and the inverted value is both output and enqueued back onto the queue. If you concatentate two such queues of length 2n together, then for 2n cycles, you get the XOR of the values dequeued from both queues, and after those cycles the later of the original queues has pointwise-XORed itself with the earlier (because the values it output were enqueued back onto it), whilst the earlier has its original values. The next 2n cycles will then output the XOR of the new values of the queues, i.e. the original value of the earlier queue XOR (the original value of the earlier queue XOR the original value of the later queue), which is just the original value of the later queue. Thus, concatenating a running-XOR memory representing A and a running-XOR memory of the same power-of-2 width representing B will output the sequence (A pointwise-XOR B) concatenate B (which is why the recursive encoding algorithm works).
This is a 2-state, 14-symbol strongly universal Turing machine (i.e. it starts from a finitely initialized tape and implements halting correctly). Finding small universal Turing machines is effectively a code golf problem, so it makes sense to post it on a code golf site.
Most of the machine actually functions fairly intuitively. The only confusing part is the running-XOR storage used for the program, but that can easily be encoded mechanically (and there is a program to do it) – it's generally considered that as long as the encoding algorithm can be proven to always halt and produce a finite result, it counts. (I prefer for the encoding algorithms to be primitive recursive, so that you can easily tell how long the encoding to take, but this one is (and in fact runs in O(n log n) time, so is even pretty fast.)
There is still quite a bit of slack in this construction; I ended up not needing to use 2 of the 28 transitions that were available, and it seems likely that many small variations of this machine are also going to be strongly universal. In 2019, I catalogued a range of small programming languages that could be encoded into 2-state 14-symbol Turing machines (the "Core BIX Queue Subsets"), although I didn't at the time mention what my motivation for selecting that particular set of languages was.
a vd vt is not the only Core BIX Queue Subset that seems promising for Turing-completeness (although it did seem like the easiest to prove, and given that it took me almost 4 years, I have not been particularly inspired to try to work on one of the harder ones…); this Turing machine can easily be adapted to interpret any of the others.
I'd be interested to know whether anyone else has been trying to golf universal Turing machines recently (either strongly universal Turing machines like this one, or one of the less restrictive categories of universality). A quick search didn't turn up anything better for 2 states than 18 symbols, but it's quite possible that this sort of result would be in some obscure corner of the Internet that might be hard to find.