BIX Queue Subset
The BIX Queue subsets are a set of esoteric programming languages devised by User:ais523 in 2019, that work roughly like cyclic tag systems. The set of languages is interesting because it seems to contain multiple different languages whose computational class is non-obvious in interesting ways (typically due to uncertainty about whether or not they are Turing-complete). They may also be suitable source languages for computational class proofs in their own right, as they admit implementation even in languages with highly restricted control flow.
BIX Queue Subset itself is a meta-language for describing these languages. It does so in terms of a more general language called BIX Queue.
BIX Queue
A BIX Queue program consists of three parts: two queues, the command queue and the data queue, and a single variable, the mode flag with three possible values ("blocked" b, "idle" i, "extending" x). The data queue is a queue of bits (each element is 0 or 1); the command queue is a queue of commands. There are six possible commands:
| Command | Syntax | Defined in mode/modes | Effect when executed |
|---|---|---|---|
| ask | a |
idle | Halt program execution if the data queue is empty. Otherwise, dequeue the data queue, and enter blocked mode if a 0 was dequeued, or extending mode if a 1 was dequeued. |
| continue | c |
idle | Enter extending mode. |
| done | d |
blocked, extending | Enter idle mode. |
| false | f |
blocked, extending | If in extending mode, enqueue a 0. (This is a no-op in blocked mode.)
|
| true | t |
blocked, extending | If in extending mode, enqueue a 1. (This is a no-op in blocked mode.)
|
| invert | v |
blocked, extending | If in extending mode, change the value of every bit within the queue (0 becomes 1 and vice versa). (This is a no-op in blocked mode.)
|
A program is notated by giving the initial values of the command queue, mode flag, and data queue, in that order; for example, afttdatfdatftd i 1. Queues are written with their head at the leftmost end. Whitespace is ignored. Comments can be used (starting with # and ending at end of line), and are ignored, but apart from comments, unexpected characters are a syntax error.
Program execution consists of repeatedly dequeuing the command queue, executing the command dequeued this way, and then enqueuing this command back onto the command queue. (Thus, the command queue just rotates in place; it never changes except for a cyclic permutation.) Executing a or c outside idle mode, or d, f, t, or v inside idle mode, is undefined behaviour. (However, it is easy to determine via static analysis whether undefined behaviour can ever occur, because transitions into and out of idle mode can never be data-dependent; in fact, it is even possible to analyse programs to the extent of either proving that undefined behaviour must happen or that undefined behaviour cannot happen. Compilers for BIX Queue and for BIX Queue subsets are thus encouraged to reject programs that would encounter undefined behaviour.)
BIX Queue Subset
Starting from BIX Queue, it is possible to imagine a language with additional commands formed by composing two or more existing commands. For example, ft has the same behaviour as f then t, i.e. "if in extending mode, enqueue a 0 then a 1; do nothing in blocked mode". A BIX Queue subset is simply a language formed by starting with BIX Queue, adding zero or more compound commands, and then removing zero or more commands from the resulting language. For example, BIX Queue without the t command is a BIX Queue subset, as is the BIX Queue variant with the four commands {at, ct, f, vtd} (with ct defined as "switch to extending mode and enqueue a 1", and likewise the other commands are defined by composing the meaning of the existing BIX Queue commands that make up their names). An example of a legal program in this latter subset might be at vtd ct f vtd i 1101. It should be noted that every program in a BIX Queue subset is also a legal program in BIX Queue itself, and has the same semantics (i.e. it halts in BIX Queue if and only if it halts in the BIX Queue subset). However, in most BIX Queue subsets, there will be some BIX Queue programs that are not legal in the subset.
BIX Queue Subset is a notation for specifying a particular BIX Queue subset. It consists of a list of available commands within the language, separated by whitespace. For example, the latter subset discussed above could be defined in BIX Queue Subset as at ct f vtd.
Core BIX Queue Subset
Core BIX Queue Subset is a BIX Queue Subset subset; that is, a language that can define only some of the languages that BIX Queue Subset can. These languages are the "Core BIX Queue subsets". ais523 intends the set of Core languages as a set of languages that are particularly easy to implement, even compared to the other BIX Queue subsets.
A Core BIX Queue Subset description has the same meaning as it would in BIX Queue Subset, but must obey the following restrictions:
amust be present, but no other commands containingamay be. No command containingcmay be present.- There are exactly two other commands.
- At least one command must contain
d. - Every command must be present in one of the following explicit lists of possible commands:
a.v,f,t,vf,vt.d,vd,fd,td,vfd,vtd.
There are 5×6=30 Core BIX Queue subsets containing one d, and a further (2 choose 6)=15 Core BIX Queue subsets containing two ds, thus 45 Core BIX Queue subsets in total. Many of these are interesting in one way or another.
Some interesting BIX Queue subsets
Existing languages
At least two existing languages are directly equivalent to BIX Queue subsets.
The BIX Queue subset da f t almost directly implements cyclic tag (in Bitwise Cyclic Tag notation, da corresponds to 0, f to 10, t to 11). A cyclic tag program is translated to a BIX Queue subset program that uses the mode flag to store the head of the cyclic tag queue (extending = 1, blocked = 0), and stores the remainder of the cyclic tag queue in the BIX Queue data queue.
The BIX Queue subset affd attd defines 2-Echo Tag (other Echo Tags can also be defined this way, e.g. 3-Echo Tag is afffd atttd).
a c fd td
1-Echo Tag, afd atd (expressible in Core form as a fd td) is obviously Turing-incomplete, because the data queue can never grow. However, adding c variants to this set (i.e. afd cfd atd ctd or a c fd td) produces a minor 1-Echo Tag variant that is no longer obviously Turing-incomplete (its commands are "dequeue and append 0 if a 1 was dequeued", "dequeue and append 1 if a 1 was dequeued", "unconditionally enqueue 0", "unconditionally enqueue 1"). ais523 believes that this language is Turing-complete in the weak sense of "any Acyclic Tag program can be compiled into an a c fd td program in such a way that there is a mapping between internal states of the two programs"; however, the most direct sort of construction that would produce this result leaves the a c fd td program with no way to halt, because it's hard to simultaneously write a program that allows the queue to be capable of both growing indefinitely and shrinking to zero. Thus, it is highly unclear whether a c fd td is Turing-complete in the stronger sense of "any insert Turing-complete language of your choice here program can be compiled into an a c fd td program with the same halting behaviour".
a t fd
The language a t fd, in effect, implements a form of cyclic tag in which every production matches the regular expression /^1+0$/, i.e. consists of any number of 1s followed by a 0. This is a major restriction on cyclic tag, but may not be a fatal one; just as programming in Echo Tag requires being able to anticipate the length of the data you will generate "in advance" (in Echo Tag, the length of the data generated from a particular section of data queue depends on the number of 1s in that section), programming in a t fd requires being able to anticipate the number of 0s in the data you will generate. ais523 suspects that this subset is Turing-complete, but so far, has not found a proof, nor even an approach that seems likely to create one.
It should be noted that the more intuitive language a f td, in which the number of 1s is fixed rather than the number of 0s, is sadly Turing-incomplete despite being much more straightforward to program in: there is no way for the number of 1s in the queue to ever increase (or reduce, for that matter), and the maximum ratio of 0s to 1s in the data queue is a hardcoded part of the program, meaning that there is a limit to how large the data queue can ever become. a f td is quite possibly a bounded-storage machine.
a vd vt
- Main article: Grill Tag
In 2019, ais523 considered a vd vt the most likely candidate for strong Turing-completeness among the Core BIX Queue subsets (although it's always possible that an even more promising candidate will be discovered!). a vd vt is capable of implementing the subset of cyclic tag that allows only the productions 0, 010, 01010, 0101010, etc. (it is more powerful than this, because it also admits sequences like a vd that conditionally invert the data queue). The reason that this seemed promising is that two productions can generate sequences of the forms 001010101010 or 010101010100 that have the 1s offset from each other, allowing small differences in the data queue to be used to produce arbitrarily large differences in the data that results after two more scans through the data queue, yet without losing control over the positions of the data queue and command queue relative to each other.
This subset does have something of a major issue, though, that makes Turing-completeness proofs difficult: a 1 in the data queue necessarily does something when dequeued (you either have to append a 0 to the data queue, or else invert it). This makes it hard to process sequence of alternating 0s and 1s to produce something with one of the two possible parities, but nothing with the other parity; a Turing-complete construction would thus probably have to generate bursts of 0s on the unwanted parity and then allow for them later.
In 2023, a vd vt (in fact, the slightly more restrictive subset a vtvt vtvd) was proven to be strongly Turing-complete, and given the name Grill Tag. Details of the Turing-completeness proof are available on the linked page.
Computational class
Because cyclic tag and Echo Tag are BIX Queue subsets, BIX Queue must be Turing-complete. There is also a Core subset that is known to be Turing-complete, a vd vt.
However, there are still a lot of BIX Queue subsets (including Core subsets) whose Turing-completeness is unclear – the BIX Queue construction seems to be a particularly fruitful one in terms of producing interesting Turing-completeness problems.
External resources
- Rudimentary BIX Queue interpreter (can also be used for implementing a BIX Queue subset)