<p>It is. There's a fairly simple construction compiling from CT to CT2.</p>
<p>First, consider that it's possible to double every command in a CT program without producing any behaviour (that is, <code>A</code> becomes <code>AA</code>, <code>B</code> becomes <code>BB</code>, <code>C</code> becomes <code>CC</code>). 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.</p>
<p>Let <span class="math-container">$n$</span> be the number of <code>A</code> commands in a program. You can observe that pushing a string of <span class="math-container">$n$</span> false bits (indeed, any multiple of <span class="math-container">$n$</span>) will have no effect on a CT program (as will <em>not</em> pushing a string of <span class="math-container">$n$</span> false bits), so you can safely write a string of <span class="math-container">$n$</span> <code>B</code>s anywhere in a program without changing its behaviour.</p>
<p>Suppose we take a CT program with every command doubled, and insert a string of <span class="math-container">$2n$</span> <code>B</code>s immediately before each <code>AA</code> pair (i.e. immediately before an <code>A</code> before it was doubled); here, <span class="math-container">$n$</span> is the number of <code>A</code> commands <em>after</em> the doubling (i.e. twice the number of <code>A</code> commands in the original program). This does not change the behaviour of the program. Additionally, those <code>B</code>s that happen to be in even positions can be changed to <code>C</code>s without changing the behaviour of the program (because the even-numbered bits in the queue are skipped by the second <code>A</code> command of a pair, their values are irrelevant). We can thus change somewhere from <span class="math-container">$0$</span> to <span class="math-container">$n$</span> of each run of <span class="math-container">$2n$</span> inserted <code>B</code>s into <code>C</code>s, and produce a CT program which has identical behaviour to the original, and for which additionally the number of <code>B</code>s between each pair of <code>A</code>s is a multiple of <span class="math-container">$n$</span>.</p>
<p>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 <span class="math-container">$n$</span> false bits will be appended to the queue (due to <code>B</code> commands running when the head of the queue is false). The added bits will always be in runs whose length is a multiple of <span class="math-container">$n$</span>.</p>
<p>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 <code>B</code> 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 <span class="math-container">$n$</span> (the number of <code>B</code> commands between any two <code>A</code> commands is a multiple of <span class="math-container">$n$</span>, so the total number of <code>B</code> commands is produced by adding multiples of <span class="math-container">$n$</span> and is still a multiple of <span class="math-container">$n$</span>).</p>
<p>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.)</p>
<p>(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.)</p>

CC BY-SA 4.0
2021-03-13T04:20:41.817Z
Thank you for your comprehensive answer. Is there an alternative encoding that has the same halting condition as the original, i.e. the queue becoming empty? The empirical runtimes suggest there might be, which is what prompted my original question.
user76284
CC BY-SA 4.0
2021-03-13T04:26:03.510Z
Regarding your last question, I've been interested in Turing tarpits and minimalist universal systems for a while. There's an even simpler queue system (with nontrivial runtimes) that I suspect is non-universal, but haven't gotten around to proving it. I can ask a question about it, if you'd like. What you're referring to also sounds interesting. I'd love to hear more about it.
user76284
CC BY-SA 4.0
2021-03-14T05:43:44.950Z
My initial reaction is that there wasn't – the problem is that the program must contain more `A` than `B` commands to avoid a trivial infinite loop, which is very unusual in cyclic tag programs and makes them hard to program. However, I can't easily prove that it's impossible to write a cyclic tag program like that, so maybe there's an alternate programming style where it's possible. As for what I was referring to, see https://esolangs.org/wiki/Echo_Tag for an example (it's basically a CT variant where every command is `BBA` or `CCA`, and is probably Turing-complete).
ais523
CC BY-SA 4.0
2021-03-05T15:50:25.130Z
2021-03-05T15:50:25.130Z
ais523
<p><em><a href="https://mathoverflow.net/questions/384959/is-this-variant-of-bitwise-cyclic-tag-turing-complete">Cross-posted</a> to MathOverflow.</em></p>
<hr />
<p><a href="https://esolangs.org/wiki/Bitwise_Cyclic_Tag#The_language_CT" rel="nofollow noreferrer">CT</a> is an extremely minimalist programming language that <a href="https://esolangs.org/wiki/Bitwise_Cyclic_Tag#Computations_in_BCT" rel="nofollow noreferrer">can simulate</a> arbitrary <a href="https://en.wikipedia.org/wiki/Tag_system" rel="nofollow noreferrer">tag systems</a>, and is therefore Turing-complete. A program consists simply of a string of 3 commands that operate on a <a href="https://en.wikipedia.org/wiki/Queue_(abstract_data_type)" rel="nofollow noreferrer">queue</a> of bits:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>Command</th>
<th>Description</th>
</tr>
</thead>
<tbody>
<tr>
<td>A</td>
<td>pop</td>
</tr>
<tr>
<td>B</td>
<td>push 0 if front is 1</td>
</tr>
<tr>
<td>C</td>
<td>push 1 if front is 1</td>
</tr>
</tbody>
</table>
</div>
<p>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.</p>
<p>Let CT2 be the language that replaces command B with &quot;push 0&quot; (unconditionally). <strong>Is CT2 Turing-complete?</strong> 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.</p>
<p>Here are the <a href="https://en.wikipedia.org/wiki/Busy_beaver" rel="nofollow noreferrer">busy beaver</a> sequences for both languages with a 10K-step runtime limit (runtimes exceeding this are considered non-terminating):</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>Program length</th>
<th>CT</th>
<th>CT2</th>
</tr>
</thead>
<tbody>
<tr>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>2</td>
<td>4</td>
<td>1</td>
</tr>
<tr>
<td>3</td>
<td>9</td>
<td>3</td>
</tr>
<tr>
<td>4</td>
<td>16</td>
<td>8</td>
</tr>
<tr>
<td>5</td>
<td>25</td>
<td>19</td>
</tr>
<tr>
<td>6</td>
<td>36</td>
<td>17</td>
</tr>
<tr>
<td>7</td>
<td>49</td>
<td>49</td>
</tr>
<tr>
<td>8</td>
<td>399</td>
<td>899</td>
</tr>
<tr>
<td>9</td>
<td>2159</td>
<td>1367</td>
</tr>
<tr>
<td>10</td>
<td>1407</td>
<td>300</td>
</tr>
<tr>
<td>11</td>
<td>7490</td>
<td>9893</td>
</tr>
<tr>
<td>12</td>
<td>9130</td>
<td>3348</td>
</tr>
</tbody>
</table>
</div>
<p>Notice that CT2 also exhibits a rapid growth that is suggestive of Turing-completeness.</p>

<computability><pl.programming-languages><universal-computation>
Is this variant of bitwise cyclic tag Turing-complete?
user76284
# Is this variant of bitwise cyclic tag Turing-complete?

(Asked by: username_0 on 2021-02-08)

*[Cross-posted](https://mathoverflow.net/questions/384959/is-this-variant-of-bitwise-cyclic-tag-turing-complete) to MathOverflow.*

---

[CT](https://esolangs.org/wiki/Bitwise_Cyclic_Tag#The_language_CT) is an extremely minimalist programming language that [can simulate](https://esolangs.org/wiki/Bitwise_Cyclic_Tag#Computations_in_BCT) arbitrary [tag systems](https://en.wikipedia.org/wiki/Tag_system), and is therefore Turing-complete. A program consists simply of a string of 3 commands that operate on a [queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)) 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 "push 0" (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](https://en.wikipedia.org/wiki/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.

**Tags:** computability, pl.programming-languages, universal-computation


---

## 1 answers

### Answer by username_1 on 2021-03-05. Score: 2

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$ `B`s anywhere in a program without changing its behaviour.

Suppose we take a CT program with every command doubled, and insert a string of $2n$ `B`s 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 `B`s that happen to be in even positions can be changed to `C`s 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 `B`s into `C`s, and produce a CT program which has identical behaviour to the original, and for which additionally the number of `B`s between each pair of `A`s 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 "the queue consists entirely of false bits", 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.)

> **Comments:**
> **username_0**: Thank you for your comprehensive answer. Is there an alternative encoding that has the same halting condition as the original, i.e. the queue becoming empty? The empirical runtimes suggest there might be, which is what prompted my original question.  
> **username_0**: Regarding your last question, I've been interested in Turing tarpits and minimalist universal systems for a while. There's an even simpler queue system (with nontrivial runtimes) that I suspect is non-universal, but haven't gotten around to proving it. I can ask a question about it, if you'd like. What you're referring to also sounds interesting. I'd love to hear more about it.  
> **username_1**: My initial reaction is that there wasn't – the problem is that the program must contain more `A` than `B` commands to avoid a trivial infinite loop, which is very unusual in cyclic tag programs and makes them hard to program. However, I can't easily prove that it's impossible to write a cyclic tag program like that, so maybe there's an alternate programming style where it's possible. As for what I was referring to, see https://esolangs.org/wiki/Echo_Tag for an example (it's basically a CT variant where every command is `BBA` or `CCA`, and is probably Turing-complete).  

---

