It is a BIX Queue Subset,
a vtvt vtvd. Notably, this is itself a subset of the Core BIX Queue Subset
a vd vt, making
a vd vt the first Core BIX Queue Subset to be proven Turing-complete.
Like all Core Bix Queue Subsets, Grill Tag is particularly easy to implement; it can be seen as a simplification of Bitwise Cyclic Tag, which was already very easy to implement, but with only two commands rather than three (or two commands neither of which takes an argument, rather than two commands for which one requires an argument). The hope is that this might be able to provide smaller implementations of the language in some Turing tarpits than Bitwise Cyclic Tag could manage, because there are only two cases to consider rather than three (even though the cases are individually a little more complicated).
Grill Tag is a queue-based language which stores data using a queue of bits (with the initial value of this queue specified in the program). In its basic syntax, it has two commands,
11. The commands affect the queue of bits as follows:
10: if the head of the queue is
0, otherwise enqueue nothing, and in either case dequeue and discard the first bit of the queue.
11: if the head of the queue is
10, and otherwise do nothing.
The program runs in a loop until the queue of bits is empty.
In the basic syntax, the commands are just concatenated directly to form a program; separators between commands are not required, and indeed are not allowed.
Rather than writing out the commands directly, Grill Tag is often represented in a run-length-encoded form: a number n represents n
11 commands followed by an
01 command. When using this representation, the lengths are separated by commas, and the entire program enclosed in square brackets.
The behaviour of Grill Tag's two commands can be defined by giving direct translations to Bitwise Cyclic Tag:
or to BIX Queue:
vt vd a;
- there is a leading
Grill Tag is a special case of cyclic tag; when using the run-length-encoded view of the language, a run length of 0 corresponds to a production , of 1 to [0,1,0], of 2 to [0,1,0,1,0], of 3 to [0,1,0,1,0,1,0], and so on. This pattern of alternating 0s and 1s (with 0s at the edges) is what gives Grill Tag its name; the pattern itself is, in the context of Grill Tag, called a "grill".
Grill Tag's commands have the names that they do because some implementations may want to split them into two subcommands. The BIX Queue view of the commands is as follows:
Alternatively, you could implement them like this:
0: dequeue and discard the first bit of the queue;
1: if the first bit of the queue is 1, enqueue a 0 (if an even number of commands have run, not including this command) or 1 (if an odd number have run); otherwise do nothing.
The basic idea is to assign an index y (0 ≤ y < ymax) to each Genera Tag symbol, define a constant a (which is 28(ymax+1)) which is used to control the size of the symbols, and represent each such symbol in Grill Tag using one of the following three encodings:
- Encoding E
- 14y+7 zeroes; then a grill with a-3 1s; then
010101010101010(15 bits, 7 of which are 1); then a grill with a-2 1s; then 3a-14y-10 zeros. If the symbol has even width, this is followed by another 7a 0s.
- The total width of this pattern is 14y+7 + 2a-5 + 15 + 2a-7 + 3a-14y-10 = (14-14)y + (2+2+3)a +7-5+15-7-10 = 7a (or 14a if the symbol has even width).
- Encoding L
- a-3 zeroes; then a grill with 14y+7 1s; then
0101010(7 bits, 3 of which are 1); then a grill with 3a-14y-10 1s. If the symbol has even width, this is followed by another 7a repeats of
- The total width of this pattern is a-3 + 28y+15 + 7 + 6a-28y-19 = (28-28)y + (1+6)a -3+15+7-19 = 7a (or 21a if the symbol has even width).
- Encoding R
- 1 zero; then a grill with 14y+7 1s; then
0101010(7 bits, 3 of which are 1); then a grill with 3a-14y-10 1s; then a-4 zeroes. If the symbol has even width, the last grill pattern is extended to have an additional 7a 1s (i.e. adding an additional 7a repeats of
- The total width of this pattern is 1 + 28y+15 + 7 + 6a-28y-19 + a-4 = (28-28)y + (1+6)a +1+15+7-19-4 = 7a (or 21a if the symbol has even width).
Encoding E is used in the initial string. On each generation, the encodings alternate: an encoding E symbol produces a mix of encoding L and R symbols, then the encoding L and encoding R symbols each produce encoding E symbols. The E-to-L/R productions are used to actually perform the logic of Genera Tag; each L and each R encoding simply just produces the E encoding of the same symbol, rather than performing a Genera Tag generation.
To implement the halt symbol, add 1½a repeats of
10 to its L/R encoding, rather than the 0 or 7a that would normally be added based on symbol width; a is even, so this repeat count is an integer. The runs of the Grill Tag program are designed so that any run that is actually produced from during normal execution has a degenerate run consisting of a single
01 command 3a runs later; thus, once a halt symbol is produced, everything beyond it in that generation, and everything produced from symbols before it in the next generation, will produce nothing but zero bits (causing the program to rapidly end because with nothing zero bits remaining, nothing more can be produced and the queue will empty).
The Grill Tag program consists of 14a runs, most of which are degenerate runs consisting of a single
01 command and no
11 commands. In particular, the first, third, fifth, etc. runs are all degenerate, meaning that all the variable-length grills will produce nothing but zeros (because their parities are designed so that the nonzero parts of the grill only ever fall on the degenerate runs). This means that the only nontrivial runs are those which produce from the nonzero parts of the fixed-length grills, the
010101010101010 of encoding E and
0101010 of encoding L/R. These can easily be worked out from the definition above, but here's an explicit list anyway (with the first run being indexed 0):
- Runs that implement generating Encoding E from Encoding R
- 28y+17: a-3;
- 28y+19: 7;
- 28y+21: a-4;
- Runs that implement generating Encoding E from Encoding L
- 28y+a+13: a-3;
- 28y+a+15: 7;
- 28y+a+17: a-4;
- Runs that implement generating an Encoding L and Encoding R pair from Encoding E
- 14y+2a+3: 14y0 + 7;
- 14y+2a+5: 3
- 14y+2a+7: 3a - 14y0 - 10 (adjusted for y0's width and halting status by adding 7a or 1½a if necessary)
- 14y+2a+9: 0
- 14y+2a+11: 14y1 + 7;
- 14y+2a+13: 3
- 14y+2a+15: 3a - 14y1 - 10 (adjusted for y1's width and halting status by adding 7a or 1½a if necessary)
Here, y0 and y1 are the two symbols produced from y at the appropriate position – the whole set of 7a runs is written twice, once using the position 0 productions, and once using the position 1 productions.
With the above definitions, the Grill Tag program simulates the Genera Tag program directly; an encoding E encoding of one Genera Tag generation becomes an Encoding L/R encoding of the next generation, and then an Encoding E encoding of that generation. In an Encoding L/R generation, it does not matter whether the position is initially 0 or 7a – the same strings will be produced either way. The position will stay the same, because the total length of the queue will be a multiple of 14a (because there are an even number of symbols – each symbol in the previous generation produced two symbols – and each symbol has a length that's 7a mod 14a). In an Encoding E generation, the length of each symbol is 0 mod 14a if it has an even width in Genera Tag, or 7a mod 14a if it has an odd width in Genera Tag, so the Grill Tag instruction pointer will exactly model the Genera Tag position (multiplied by a factor of 7a). This exact correspondence between the two programs will cause the Grill Tag program to halt if and only if the Genera Tag program halts, proving Grill Tag Turing-complete.
It should be noted that Grill Tag is in general very hard to program in because the difference between the number of 0s and 1s in a substring has to equal the number of 1s in the string that produced it, which places a fairly strict invariant on programs and rules out a lot of plausible-seeming possibilities. The numbers in the proof above were determined by initially working out the basic nature of the program, and then solving simultaneous equations to work out the exact size of all the runs of zeroes and grills. In order to make this work, it was required that the number of symbols produced from each other symbol would be statically known (thus the use of Genera Tag as the language to compile from; languages like traditional tag systems are simpler in most respects but have variable-length productions, which would have prevented this proof technique working).
1011101110 (which run-length-encodes as
[0,1,1]) runs as follows on the input
110110 (here, square brackets show which commands run between this line and the next):
 1110 1110 110110 10  1110 101100 10 1110  01100010  1110 1110 1100010 10  1110 1000100 10 1110  000100010  1110 1110 00100010 10  1110 0100010 10 1110  100010  1110 1110 00010010 10  1110 0010010 10 1110  010010  1110 1110 10010 10  1110 00100 10 1110  0100  1110 1110 100 10  1110 000 10 1110  00  1110 1110 0
Turing machine implementation
Part of ais523's motivation for looking at Grill Tag is that it is particularly easy to implement in a Turing machine. The following 2-state 14-symbol Turing machine implements a version of Grill Tag, with a somewhat weird program encoding:
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
- Basic interpreter for the run-length-encoded format, written in Perl
- Genera Tag to Grill Tag compiler, written in Perl
- Filter that recognises patterns within Grill Tag debug output that match Genera Tag symbols – useful to manually verify that the Genera Tag to Grill Tag compiler is working correctly
- A discussion of the 2-state 14-symbol Turing machine that implements Grill Tag
- Compiler from Grill Tag into an initial state for the 2-state 14-symbol Turing machine