Grill Tag

From Esolang
Jump to navigation Jump to search

Grill Tag is a special case of cyclic tag that User:ais523 originally studied in 2019, but did not prove Turing-complete 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 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).

Specification

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, 10 and 11. The commands affect the queue of bits as follows:

  • 10: if the head of the queue is 1, enqueue 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 1, enqueue 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.

Alternative definitions

The behaviour of Grill Tag's two commands can be defined by giving direct translations to Bitwise Cyclic Tag:

  • 10 translates to 100;
  • 11 translates to 1110.

or to BIX Queue:

  • 10 translates to vt vd a;
  • 11 translates to vt vt;
  • there is a leading a.

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 [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 to vd a;
  • 1 translates to vt.

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 < 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 10.
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 10).
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 but 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).

Example

The program 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): 

[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 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

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

See also

Retrieved from "https://esolangs.org/w/index.php?title=Grill_Tag&oldid=126388"