Talk:Grill Tag

Bug in the example?

The interpreter that generated the example output looks like it is appending 01 instead of 10 as stated in the spec (and confirmed by the BCT translation 1110). I don't know for sure this changes the power of the language, but it's confusing. I thought I'd messed up my (thematic) Grill Tag implementation by misinterpreting how to append 10, so I flipped it to get the results in the example, which I was using as a test case. The BCT translation makes it clear 10 is correct though.

Starting with data string 110110 and working though the program 1011101110 manually:

Production [10] appends 0 and deletes head : 101100; all good so far.

[11] should append 10 according to the spec (and BCT translation 1110) to give datastring: 10110010

[10] will append 0 and delete head to give data: 01100100, this differs from the third line of the example:

   10  1110 [1110]  01100010

There are a lot of interpretations on the page, and I'm not familiar with BIX Queue Subset to verify against that representation, but I've worked with BCT enough to see there's an inconsistency somewhere. Hopefully it's just a typo, or a bug in one interpreter, and doesn't unravel any of the tag system results? Feel free to ignore my linked interpreter that prompted this, it probably won't help debug since I was leaning heavily into the "art" side of things with apophenic spec interpretations for that page, but I think there's a real inconsistency in the Grill Tag page with transposed appendants for the 11 production. Salpynx (talk) 05:21, 11 May 2026 (UTC)

The Stack Exchange post linked under the Turing machine implementation gives this description of Grill Tag:

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 0, 010, 01010, 0101010, and longer strings that follow the same pattern.

This would require the 11 command to enqueue 01, as otherwise the productions would instead be 0, 100, 10100, etc. The Turing-machine implementation itself seems to agree with this, along with the BIX Queue description and Turing-completeness proof. This seems to suggest the bug lies in the specification and BCT translation. –PkmnQ (talk) 07:18, 11 May 2026 (UTC)

I think PkmnQ is right – the typo was in the specification and everything else is consistent. (PkmnQ has now fixed the specification.) --ais523 16:07, 11 May 2026 (UTC)

Thanks User:PkmnQ, highlighting that line from the SE post clears it up for me! I see the 'grill' now, and thinking in terms of cyclic tag, rather than slightly lower level BCT, clarifies the run-length encoding significance.

I see now that both commands could be made to work equivalently by switching the run length encoding:

• appending 10 would work with prefixed production delimiters of 0
• appending 01 works when the production delimiter is suffixed, like the example [0,1,1] = 10 1110 1110

In the alternative prefix-delimiter scheme 1011 1011 10 (literally the same binary string) would encode as [1,1,0]. This is trivial-substitution territory though, it's the same language, but both parts need to be in sync, and the spec should settle on one. Looks like there may have been various iterations, and appending 01 is the 'final' version, at least the one that is most attested in useful proofs and examples. Suffixed delimiters seem to make most sense when comparing back to cyclic tag productions, but maybe the choice is somewhat arbitrary. Your correction is good (BCT: 1011).

Observation: the raw Grill Tag spec appears to permit a production containing a 1 at one end by excluding an expected delimiter so it can't be run-length encoded, e.g. 11 10 11 11 can't be directly run-length encoded, but appears syntactically valid from a command viewpoint. I don't think this is a problem; it's meaningful, but perhaps unlikely to be useful, like while False; do.

Now that I get the intended semantics, a another syntax error jumps out at me: In the Specifications section on rle: "followed by an 01 command", the command should be 10.

There are further mentions of a "01 command" in the Computational Class section, I think those should also be 10 if they refer to Grill Tag commands. The source of confusion is the same binary alphabet being used to represent data-strings, productions in at least three different tag dialects on the page (genera / cyclic / BCT), and perhaps a distinction between productions and commands that encode productions. I'm confident to fix the rle section, but worried a copy-paste edit in the proof will break it, can you provide any guidance User:ais523? Salpynx (talk) 21:22, 11 May 2026 (UTC)

When I was working on the proof I was working entirely in RLE, so I probably just copied the mistake from the specification when translating from RLE back into the primary syntax. --ais523 22:18, 11 May 2026 (UTC)