Grill Tag
Grill Tag is a special case of cyclic tag that User:ais523 originally studied in 2019, but did not prove Turingcomplete until 2023.
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 Turingcomplete.
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).
Specification
Grill Tag is a queuebased 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, 10
and 11
. The commands affect the queue of bits as follows:
10
: if the head of the queue is1
, enqueue0
, otherwise enqueue nothing, and in either case dequeue and discard the first bit of the queue.11
: if the head of the queue is1
, enqueue10
, 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 runlengthencoded 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.
Alternative definitions
The behaviour of Grill Tag's two commands can be defined by giving direct translations to Bitwise Cyclic Tag:
10
translates to100
;11
translates to1110
.
or to BIX Queue:
10
translates tovt vd a
;11
translates tovt vt
; there is a leading
a
.
Grill Tag is a special case of cyclic tag; when using the runlengthencoded view of the language, a run length of 0 corresponds to a production [0], 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:
0
translates tovd a
;1
translates tovt
.
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.
Computational class
Grill Tag is Turing complete because it is possible to compile Genera Tag (with m=2 and each production containing exactly two symbols) into it.
The basic idea is to assign an index y (0 ≤ y < y_{max}) to each Genera Tag symbol, define a constant a (which is 28(y_{max}+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 a3 1s; then
010101010101010
(15 bits, 7 of which are 1); then a grill with a2 1s; then 3a14y10 zeros. If the symbol has even width, this is followed by another 7a 0s.  The total width of this pattern is 14y+7 + 2a5 + 15 + 2a7 + 3a14y10 = (1414)y + (2+2+3)a +75+15710 = 7a (or 14a if the symbol has even width).
 Encoding L
 a3 zeroes; then a grill with 14y+7 1s; then
0101010
(7 bits, 3 of which are 1); then a grill with 3a14y10 1s. If the symbol has even width, this is followed by another 7a repeats of10
.  The total width of this pattern is a3 + 28y+15 + 7 + 6a28y19 = (2828)y + (1+6)a 3+15+719 = 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 3a14y10 1s; then a4 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 of10
).  The total width of this pattern is 1 + 28y+15 + 7 + 6a28y19 + a4 = (2828)y + (1+6)a +1+15+7194 = 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 EtoL/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 variablelength 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 fixedlength 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: a3;
 28y+19: 7;
 28y+21: a4;
 Runs that implement generating Encoding E from Encoding L

 28y+a+13: a3;
 28y+a+15: 7;
 28y+a+17: a4;
 Runs that implement generating an Encoding L and Encoding R pair from Encoding E

 14y+2a+3: 14y_{0} + 7;
 14y+2a+5: 3
 14y+2a+7: 3a  14y_{0}  10 (adjusted for y_{0}'s width and halting status by adding 7a or 1½a if necessary)
 14y+2a+9: 0
 14y+2a+11: 14y_{1} + 7;
 14y+2a+13: 3
 14y+2a+15: 3a  14y_{1}  10 (adjusted for y_{1}'s width and halting status by adding 7a or 1½a if necessary)
Here, y_{0} and y_{1} 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 Turingcomplete.
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 plausibleseeming 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 variablelength productions, which would have prevented this proof technique working).
Example
The program 1011101110
(which runlengthencodes as [0,1,1]
) runs as follows on the input 110110
(here, square brackets show which commands run between this line and the next):
[10] 1110 1110 110110 10 [1110] 1110 101100 10 1110 [1110] 01100010 [10] 1110 1110 1100010 10 [1110] 1110 1000100 10 1110 [1110] 000100010 [10] 1110 1110 00100010 10 [1110] 1110 0100010 10 1110 [1110] 100010 [10] 1110 1110 00010010 10 [1110] 1110 0010010 10 1110 [1110] 010010 [10] 1110 1110 10010 10 [1110] 1110 00100 10 1110 [1110] 0100 [10] 1110 1110 100 10 [1110] 1110 000 10 1110 [1110] 00 [10] 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 2state 14symbol 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
Explanation about how to use the Turing machine, together with a proof of correctness, can be found in this Stack Exchange post. You might also want to try it in an online simulator.
External resources
 Basic interpreter for the runlengthencoded 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 2state 14symbol Turing machine that implements Grill Tag
 Compiler from Grill Tag into an initial state for the 2state 14symbol Turing machine