4
$\begingroup$

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 "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 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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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 "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.)

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user76284
    Commented Mar 13, 2021 at 4:20
  • $\begingroup$ 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. $\endgroup$
    – user76284
    Commented Mar 13, 2021 at 4:26
  • $\begingroup$ 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 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). $\endgroup$
    – ais523
    Commented Mar 14, 2021 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.