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

The language's author believes it is probably Turing complete. There are at least two sticking points in trying to create a proof of this, though. The largest is the initial initialisation of the queue; it may be that the language needs a different initial state to work correctly (the issue is that a run of + in unary will increase the labels of all commands to its right, thus requiring more +s – an infinite regress) and thus a compression scheme is needed to be able to store data within the program; such a compression scheme is entirely possible to implement given an arbitrary initial state, but may not be possible to bootstrap. The other, which is likely to be easier to fix, is that the control flow doesn't map neatly onto any of the usual suspects for proving Turing-completeness; in order to avoid the language degenerating to a 1-tag system (which is not Turing-complete), you need to start incrementing the tail of the queue before running a ^ command and continue running it afterwards, meaning that control flow is based on pairs of adjacent queue elements.

There is an outline plan for solving the former problem on the talk page Talk:Fusion Tag.

Implementations

In Python 3:

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