SetIncrementor
SetIncrementor is an esolang derived from SETANDCOUNT, made by islptng.
Data format
This esolang operates on a set(sorted) of positive integers.
Syntax
A list of tokens separated by spaces.
If it is a number N, it increments the Nth number in the set. If the set's size is even less than N, it increments all the numbers and add 1 into the set.
If it's something inside a brackets [x], it's a label and does nothing on its own.
If it's the name of a label, it jumps to the label only if the previous operation don't generate a duplicate. If it's a duplication, do nothing.
That's it.
Interpreter
Fast Rust interpreter by User:DGCK81LNN (github repo)
Turing-Completeness proof
Consider this representation format of a 2-register Minsky machine which consists of these lines of code:
label a -- define label a goto a -- go to label a inc r -- increment r tdec r,a -- decrement r, if already zero, go to a
where a can be any label name, and r can be x/y. Apparently, it's Turing Complete.
For we're operating on ordered sets and cannot decrement, let's consider the following representation of two registers:
{a,b,c}
where x is b-a-1, y is c-b-1.
We can thus initialize with
1 2 3
So now we have easy increment(i.e. increase upper bond) instructions:
3 2 -- inc x 3 -- inc y
TestDecrement is somehow harder: We need to first decrement(i.e. increase lower bond), then if it's zero(i.e. duplicates) we need to do recovery.
1 e 3 4 [s] 2 t 1 tar [t] 1 s [e] -- tdec x,tar
tdec y,tar is more complex but still possible.
2 e 3 4 5 [s] 3 t [q] 3 p 2 2 1 1 1 tar [p] 2 q [t] 2 1 s [e] 1 -- tdec y,tar
(Remember to change the name of the labels since you can't define 2 same labels!)
Therefore, 2-register Minsky machine can be compiled into this esolang, so it's Turing Complete.