Incrementing machine

From Esolang
Jump to navigation Jump to search

Incrementing machine is a variation of Minsky machine discovered by User:ChuckEsoteric08. Unlike any other counter machines it can only increment registers, but not decrementing or setting them to 0. It was discovered while author was working on Turing-completness proof for AddJump


Incrementing machine uses unbounded amount of registers as memory which are numerated with the first register being 0, second being 1 and so on. All of them are initially set to 0. Commands look like this:

<label> <counter1> <counter2> <branch>

It is executed as follows: increment register <counter1> and if result is equal to <counter2> then jump to label <branch>

Computational class

Incrementing machine is Turing-complete since it can implement Counter machine with following instructions:

INC x - Increment counter x
DEC x y - Decrement counter x and if result was 0 jump to line y

If DEC has only one argument, it means that it would jump to the next command
Which can simulate Minsky machine JZDEC x y insturction like that:

DEC x y

Each counter is represented as two Incrementing machine counters, called a and b. INC insturction is simulated like that:

<line number> a a <line number+1>

DEC instruction is simulated like that:

<line number> b a y

Where y is the line to which it should jump to.