Incdecisive Machine

Incdecisive Machine is a Minsky Machine variation designed by Keymaker in 2022.

Program and execution

The program consists of 0 or more instructions. Execution begins in the first instruction and halts (successfully) if the very last instruction goes to 'the next instruction' (which does not exist in that case). The two instructions are:

x inc A n : Increase register A by one. If A was 0 before it was increased, go to the next instruction. If A was non-zero before it was increased, go to the instruction n.

y dec A : Decrease A by one if its value is larger than 0. Then continue to the next instruction whether the register was decreased or stayed 0.

Computational class

The language is Turing-complete. It was designed with the 2-register Turing-completeness in mind, and there exists a translator that can translate any Minsky Machine program with any number of registers into 2-register Incdecisive Machine. There also exists a simple translation that uses x+1 registers, where x is the amount of them in the Minsky Machine program. See the external link.

There is also a simple method for translating n-register Minsky Machine into n-register Incdecisive Machine, made by ais523, found here.

External resources

• Incdecisive Machine page (detailed explanations of the language and the translations, translator program, interpreter in Python)