Beeping cyclic tag

Beeping Cyclic Tag aims to be super-Turing complete tarpit inspired by Bitwise Cyclic Tag (i.e. this program is as powerful as a Turing machine augmented with an oracle).

This is a very rudimentary Turing Tarpit that is stronger than a regular Turing machine.

Commands

There are two data queues: Q1 and Q2, and an internal variable Q. We start with Q=Q1 but we may toggle it to Q=Q2 and Q=Q1. All commands here are two bits:

11: If the leftmost bit of Q1 is 1, append 1 to the right of Q
10: If the leftmost bit of Q1 is 1, append 0 to the right of Q
01: Unconditionally toggle Q
00: Unconditionally delete the leftmost bit of Q

One may notice that if we replace all the 00's with 0 and deleted the 01's, we get the original BCT again.

Inputs and outputs

Inputs is a bit array that goes directly into the data string. If the input is empty, we default the input to the bitstream 1.

Outputs are much more interesting. First, this program does not halt at all. However, there might exist a point where Q2 does not get modified at all for the rest of time. In that case, we output Q2. If Q2 is updated infinitely many times though, then we fail to output anything and error out. Obviously we need a halting oracle to check this.

Computational Class

Here, the "Beep" occurs anytime Q2 gets updated, and hopefully there is a last beep. Beeping cyclic tag is trivially Turing complete, but we can also pseudo-solve the Halting problem by running multiple programs in parallel and beeping whenever a program halts.

This logic is ultimately similar to Boolshit where we take advantage of "last update."