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

Try it online!

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. This is 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.