Qrain

This language is a derivative of BF.

Qrain, pronounced like "queue rain", is a BF derivative which was meant to fill in a gap in the extensions page's table. It has an infinite tape of infinitely long queues of bits, as well as an output bitstream which functions like a queue.

Commands

Qrain has these 8 commands.

Character	Meaning
>	Increment the pointer (to point to the next queue to the right).
<	Decrement the pointer (to point to the next queue to the left).
+	Peek (look at the value at the front of the queue without removing it) the queue at the pointer and the output bitstream. Enqueue (add to the end of the queue) the bit 0 to the queue at the pointer if the bits are different Enqueue the bit 1 to the queue at the pointer if they are the same.
-	Dequeue (remove from the front of the queue) one bit from the queue at the pointer.
.	Dequeue up to eight bits from the queue at the pointer, or until the queue is empty, and enqueue that value to the output bitstream. If there are eight bits or more in the output bitstream, dequeue eight bits and output that as a byte, little-endian.
,	Accept one byte of input, little-endian, enqueueing that to the queue at the pointer.
[	Jump forward to the command after the corresponding ] if the bit at the front of the queue at the pointer is 0.
]	Jump back to the command after the corresponding [ the bit at the front of the queue at the pointer is 1.

An empty queue (including the output bitstream) is analyzed by the commands as having a front bit of 0 when you peek it, but causing an error when you dequeue it.

Computational Class

The language is Turing-complete because it can carry out the Turing-completeness proof in Brainfuck minus -, translating Sequential tag system and Cyclic tag system into Qrain. The empty queues can be thought of as 0. Every time + occurs, the empty output queue and the queue at that location will both be peeked as 0, which will cause 1 to be enqueued, thereby incrementing the cell for the only time it needs to be incremented. All of the other commands are the same in BF and Qrain in this context, meaning the exact same code can be used.

Now for the harder question: since the queues in Qrain can be infinitely long, how few cells does it need for a Turing-completeness proof?

Trivia

• At one point in its history, it was only possible to encode unary values into the queues. That version also would have been Turing-complete by the same proof.