Is this variant of bitwise cyclic tag Turing-complete? Cross-posted to MathOverflow.

CT is an extremely minimalist programming language that can simulate arbitrary tag systems, and is therefore Turing-complete. A program consists simply of a string of 3 commands that operate on a queue of bits:




Command
Description




A
pop


B
push 0 if front is 1


C
push 1 if front is 1




These commands are executed in cyclic order from left to right. The queue is initialized with a single 1. If the queue becomes empty, the program terminates.
Let CT2 be the language that replaces command B with &quot;push 0&quot; (unconditionally). Is CT2 Turing-complete? One way to prove this would be to find a way to simulate CT or arbitrary tag systems in it, perhaps through some clever encoding.
Here are the busy beaver sequences for both languages with a 10K-step runtime limit (runtimes exceeding this are considered non-terminating):




Program length
CT
CT2




0
0
0


1
1
1


2
4
1


3
9
3


4
16
8


5
25
19


6
36
17


7
49
49


8
399
899


9
2159
1367


10
1407
300


11
7490
9893


12
9130
3348




Notice that CT2 also exhibits a rapid growth that is suggestive of Turing-completeness.
It is. There's a fairly simple construction compiling from CT to CT2.
First, consider that it's possible to double every command in a CT program without producing any behaviour (that is, A becomes AA, B becomes BB, C becomes CC). The queue of bits now has every bit doubled, but the cycle of commands only does anything with every second bit, so the modified behaviour has the same behaviour as the original.
Let $n$ be the number of A commands in a program. You can observe that pushing a string of $n$ false bits (indeed, any multiple of $n$) will have no effect on a CT program (as will not pushing a string of $n$ false bits), so you can safely write a string of $n$ Bs anywhere in a program without changing its behaviour.
Suppose we take a CT program with every command doubled, and insert a string of $2n$ Bs immediately before each AA pair (i.e. immediately before an A before it was doubled); here, $n$ is the number of A commands after the doubling (i.e. twice the number of A commands in the original program). This does not change the behaviour of the program. Additionally, those Bs that happen to be in even positions can be changed to Cs without changing the behaviour of the program (because the even-numbered bits in the queue are skipped by the second A command of a pair, their values are irrelevant). We can thus change somewhere from $0$ to $n$ of each run of $2n$ inserted Bs into Cs, and produce a CT program which has identical behaviour to the original, and for which additionally the number of Bs between each pair of As is a multiple of $n$.
Now consider what happens if we reinterpret this CT program as a CT2 program. It will have mostly the same behaviour as the CT program, except that sometimes an additional run of a multiple of $n$ false bits will be appended to the queue (due to B commands running when the head of the queue is false). The added bits will always be in runs whose length is a multiple of $n$.
When these runs reach the front of the queue, they will, in effect, end up pushing a number of false bits onto the queue equal to the number of B commands in the entire program (rather than doing nothing, like they would in CT); this happens regardless of where the false bits appear in the queue and regardless of what point of the program we have reached (they cycle through the program from some point in it back to that point again). But this is still going to be a multiple of $n$ (the number of B commands between any two A commands is a multiple of $n$, so the total number of B commands is produced by adding multiples of $n$ and is still a multiple of $n$).
In other words, there's a direct correspondence between CT programs constructed as above (which have the same computational power as CT programs in general), and their reinterpretations as CT2 programs. If you define CT2's halt state as &quot;the queue consists entirely of false bits&quot;, this is sufficient to make CT2 Turing-complete. (I don't know whether it's possible for nontrivial CT2 programs to halt if you continue to define the halt condition as the queue being empty, though.)
(As a side note: is this question just a question-in-the-abstract asked out of curiosity, or do you need it as an intermediate result for something? I've been looking at similar but more complex constructions when trying to produce Turing-completeness results for various simple languages, and if you're aiming to do something similar yourself, I'd be interested to know what you're working on.)