User:PkmnQ/Alt Flow

Alt Flow is a family of esolangs that consists entirely of control flow commands.

Commands

Each command takes only one argument, a non-negative integer.

• SKIP n - SKIP the next n commands. (Undefined behavior if there are less than n commands after this one.)
• COPY n - COPY the next n commands and append them to the end of the program. (Undefined behavior if there are less than n commands after this one.)
• PREV n - Jump back n PREV commands. (Undefined behavior if there are less than n PREV commands before this one.)

The program halts if it reaches the end of the program.

Variants

No-label and no-nop

Commands can be restricted to positive integers instead of non-negative integers, removing the commands SKIP 0, COPY 0, and PREV 0. PREV 0 acts as a "label" of sorts that does nothing but can be jumped to by future PREV commands, so removing this would be a no-label variant. Meanwhile, SKIP 0 and COPY 0 both do nothing other than act as a nop command that can be copied and skipped past, sort of acting like empty space, thus removing these would be a no-nop variant.

Neither of these are needed for the Turing-completeness construction below, but they may be interesting when combined with other variants.

Computational class

There is a proof sketch of Alt Flow's Turing-completeness by compiling a Tag system into it. It relies on a self-copying structure that appends itself to the end of the code and allows extra code to run afterwards. This structure copies itself once:

PREV 2
COPY n+5
SKIP 4
PREV 0 # jump here
COPY 2
PREV 2
COPY n+5
... (extra code, n commands)

However, an interesting limitation is that if the same command is ever run twice, the program trivially never halts, so this cannot be used more than once. Instead, a new structure has to be created specifically to allow copying twice (an extra SKIP command is added to the beginning, but it can be ignored by the rest of the program):

PREV 0
COPY m+n+18
SKIP 17
PREV 0
COPY m+n+15
SKIP m+14
PREV 0 # jump here for extra code A
COPY 3
SKIP 2
PREV 0
COPY m+n+18
PREV 4 # jump here for extra code B
COPY 6
SKIP 5
PREV 0
COPY m+n+18
SKIP 17
PREV 0
COPY m+n+15
PREV 6
... (extra code A, m commands)
... (extra code B, n commands)

This can be extended to be able to run an arbitrary amount of times, with different pieces of code running after copying. "Strands" will be used to refer to each separate possible use of this structure, for example tbe one above has two strands.

To compile a tag system into Alt Flow, each symbol consists of a SKIP command, a self-copying structure, another SKIP command, and a PREV command to run one of the strands. The structure changes based on the tag system. For example, take this tag system:

a -> bc
b -> a
c -> aaa

Since each symbol will contain the structure in it, one strand is required for each symbol in each production. Two strands are required for symbol a's production, one strand is required for symbol h's production, and three strands are required for symbol c's production. Each strand already copies SKIP+structure by default, so the only code that needs to be added for each strand is to copy SKIP+PREV and either a jump to another strand to append another symbol or to the next symbol to be produced from.

No NOPs are used, and all PREV 0's are never ran, so the numbers can be replaced with any positive integer, thus no-label and no-nop Alt Flow are also Turing-complete if this construction is correct.

The author is working on an automated translation to fully prove the computational class.