Fusion Tag

Fusion Tag is a variant of a tag system created by User:ais523 in 2018. It's intended to require less complex data structures to implement than most tag system variants do.

Commands

The language uses a single queue of integers (initially empty), and three commands:

0	Push a 0 onto the tail of the queue.
+	Increment the tail of the queue in-place.
^	Shift an integer n off the head of the queue, and goto the nth command (where the first command is numbered 0, the second is numbered 1, and so on).

Implementations of the language are free to vary the syntax to whatever they find most convenient to implement; however, the "canonical syntax" uses the three command characters above and interprets everything else as comments. Running off the end of the program terminates it. Running + or ^ on an empty queue is an error, but implementations need not be able to diagnose the error (and thus may treat it as undefined behaviour if they wish).

Computational class

Fusion Tag is Turing-complete because cyclic tag systems can be translated into it.

The first problem the proof must overcome is the difficulty of jumping to an arbitrary point in the program. Every + will shift every instruction after it to the right by 1; therefore, a compression scheme is necessary. The compression scheme is trivial to implement: write a long string of +s (the number of +s used will be defined as the constant c) and repeatedly jump to the beginning of that string (via a ^ placed at the end of it). Every + will add to the same number, creating an arbitrarily large multiple of c. The problem with this approach is that, in order to use the decompression routine, it must be possible to reach an arbitrary point past it; a bootstrapper is necessary. The bootstrapper wraps around the decompression routine: the beginning is 0+0+++0, followed by the decompression routine, and finally ^ followed by a number of copies (defined as the constant I) of 0+++++++ (which will enqueue a 7) ending with a ^. This will cause the program to jump to instruction (I - 1) * c + 10. For example, if c = 15, then one possible bootstrapper and decompressor is 0+0+++0+++++++++++++++^^0+++++++0+++++++0+++++++0+++++++0+++++++^, which will jump to instruction 70. See Talk:Fusion Tag for more information on how this problem was solved.

The second problem is that, in order to use an element at the back of the queue (which is what will be receiving all the increments), the program must first shift every single element enqueued before it off the queue. Therefore, certain elements in the queue must be preserved when passing over them while other elements are consumed. This is done by breaking up the program flow into 2 alternating phases: decompression and execution. In the decompression phase, the queue holds a number of streaks of 7s, each followed by a 2c (ex: [7 7 7 7 2c 7 7 7 7 7 2c 7 7 7 7 2c]). When the program jumps to instruction 2c, it will simply enqueue a 0 and then continue shifting elements off the queue. The first streak of 7s will act as if there were 2 more 7s in it; every other streak will simply enqueue a multiple of c with the same coefficient as its length. The example queue from above would look like [6c 5c 4c] after the decompression phase. The execution phase does 2 things: runs the current cyclic tag production (located at the head of the queue and will be explained in the next paragraph) and converts every other element back into its compressed form. When the program jumps to 3c it will enqueue 3 7s and then a 2c. When the program jumps to 6c it will enqueue 6 7s and then a 2c. Like this, only the first element of the queue at the beginning of each cycle will be consumed and have a lasting effect on the queue.

In this translation, a 0 in cyclic tag is represented by a 3c (or 3 7s in its compressed form), and a 1 in cyclic tag is represented by a 6c (or 6 7s in its compressed form). Each production may start at any multiple of c, so long as they don't overlap with any other code segment. The beginning of a production is defined as P, and its length in the program depends on the length of the production. A production is made up of 3 distinct parts, based on the current state of the queue: the front of the queue is 0, the front of the queue is 1, and the queue is empty. When the front of the queue is 0, the program will jump to instruction P + 4c (it's not +3c due to what happens when the queue is empty). At instruction P + 4c, the program will only enqueue the location of the next production. If that location is defined as Q, then Q + 1 7s will be enqueued. When the front of the queue is 1, the program will jump to instruction P + 7c. At instruction P + 7c, the program will first enqueue all the digits in its production in their decompressed form, then enqueue the location of the next production. In both cases, when the next element in the queue is converted into its compressed form, it will add to the length of the streak of 7s that corresponds to the location of the next production (ex: 9c enqueues 8 7s, [9c 3c] -> [3c 7 7 7 7 7 7 7 7] -> [7 7 7 7 7 7 7 7 7 7 7 2c]). When the queue is empty, the streak of 7s will add to the last 7 in the streak, which will cause a jump to instruction P + 7. There, the program will enqueue enough 7s to jump past the end of the program to make it halt. This must be less than 4c - 7 instructions so that it doesn't overlap with the instructions at P + 4c. The queue is initialized at instruction (I - 1) * c + 10. The initializer first enqueues the location of the next production, then enqueues every digit of the initial queue in its compressed form (streaks of 7s ending with a 2c). Like the productions, the initializer cannot overlap with any other code segment.

The constant c must be large enough to prevent segments from overlapping (mainly in the case of the queue being empty, where it has 4c - 7 instructions to jump to the end of the program). Any valid instruction may be used to fill in the empty space between each segment of the program.

Implementations

In Python 3:

q,i,c=[],0,input()
while i<len(c):exec({"+":"q[-1]+=1","^":"i=q.pop(0)-1","0":"q+=0,"}[c[i]]);i+=1