Incdecisive Machine

Incdecisive Machine (not indecisive, 'INC-decisive') is a small counter machine designed by Keymaker in 2022. The language is essentially a Minsky Machine variation and was designed as such.

Language description

The program consists of a finite number of instructions (including zero) that are executed until the end of the program is reached (if it is ever reached).

Each instruction has an identifier, an instruction type (inc or dec), and a register/counter. In case of inc, there's also an additional identifier.

In written form the program consists of lines divided by new-lines. Comments begin with ; and last till the end of line. There can be empty lines. Only one instruction per line, spaces separating the instruction parts (at least one per separation), which themselves are strings of characters of at least one character (without new-lines or spaces).

There can be any number of registers, which are initially 0, can grow limitlessly, but not go below 0.

The program execution begins in the first defined instruction. After executing an instruction the execution moves to the next instruction (unless special case in inc). After executing the very last instruction the program halts (successfully).

The two instructions are:

Differences to Minsky Machine

I got the idea for this language while I was inspecting a variation of Minsky Machine where execution is sequential except for the case when decreasing a register fails (when the register is already 0) and a jump to an arbitrary instruction occurs. The question was whether this variant was Turing-complete with only two registers. (At the moment of writing this that case is not proven or disproven, as far as I know.) As I thought about it, I realized that I could bypass certain limitations easily if I changed the instruction set a bit -- still keeping it as minimal as possible, but changing the branching powers from the decreasing instruction to the increasing instruction. Before this, in years of inspecting Minsky Machines, it has never occurred to me that the INC instruction could be changed -- and as far as I know, it has not occurred to anyone else either. My variation instantly allowed powers that the traditional 'decrease until zero and decide' variation does not have in the case of programming with just two registers, as I was doing. My variation allowed for more complex program structure, which is possible in the ordinary Minsky Machine that I normally use, where every transition can move execution anywhere, but not in the variant I was inspecting at this time. My variation allowed for powers comparable to the 2-register ordinary Minsky Machine (with its defined transitions for every instruction) with the more limited sequential execution and only one arbitrary jump case (if register was larger than 0 when increased), while using just two registers.

Minsky Machine into Incdecisive Machine translation

There is a simple way to translate Minsky Machine with x number of registers into Incdecisive Machine program with x+1 number of registers. This is also a simple way to prove the Turing-completeness of Incdecisive Machine. To do the translation, insert the following line

0 inc nr x_1 ;; increase nr (the new register). it changes from 0 to 1, so go to the instruction x_1.

into the beginning of the program. Here 0 is a placeholder for an instruction identifier not used in the program, while nr is the new register not in the original Minsky Machine program (thus the name x+1), and x_1 is the name of the first instruction.

INC: Instruction like x INC A y becomes

x_1 inc A y_1 ;; increase A. if it changes from 0 to 1, go to next instruction (x_2), otherwise to y_1.
x_2 inc nr y_1 ;; increase nr (the new register) and jump to y_1. nr is guaranteed to be non-zero, so this jump always happens.

DEC: Instruction like x DEC B suc fai becomes

x_1 inc B x_4 ;; increase B. if it increased from 0 to 1, it means B is 0. go to next line (x_2). otherwise, if B was not 0, go to x_4.
x_2 dec B ;; if here, B was 0. because it was incremented on x_1, this instruction decreases it by one. now it is back to normal. go to next instruction (x_3).
x_3 inc nr fai ;; increase nr (the new register) and jump to fai (because B was 0, it could not be decreased, end of instruction).
x_4 dec B ;; if here, B was larger than 0. because it was incremented on x_1, decrease it by one to return it to normal. go to next instruction (x_5).
x_5 dec B ;; decrease B again, this time to do the actual decrementing. B has now been decreased. go to next instruction (x_6).
x_6 inc nr suc ;; increase nr (the new register) and jump to suc (because B was larger than 0 and could be decreased the instruction was successful).

HALT: Instruction like x HALT becomes

x_1 inc nr halt ;; because nr (the new register) is guaranteed to be larger than 0 this jump always happens.

and after the last instruction add this:

halt dec nr

Now when 'halt' is used the execution jumps to the very last instruction (halt) and after decreasing nr (for no other reason that an instruction must do something), the program halts on its own.

Minsky Machine into 2-register Incdecisive Machine translation

There is a way to translate any Minsky Machine into an Incdecisive Machine that only uses two registers, A and B. It uses the multiples of prime numbers technique.

Since the translation is somewhat difficult to explain in detail, I am pasting things from my design document, which should explain it well enough. There is also the translator (see below) whose code can be inspected.

Before any instructions, place lines

01 inc A 02
02 inc A 1_a1

which increases register A to 1 (when all registers are zero, A is 1), then increases it again and moves to the first instruction block (1_a1 here), which will immediately decrease A again.

INC: Instruction like x INC A y becomes

;;INC start;;
;; to increase a register, multiply it with the prime associated with the register. 2 in this example.
a1 dec A ;; when jumping instruction blocks, A is increased, so decrease it by one to get it to normal.
         ;; then continue to next. also a loop start.
a2 dec A ;; because A is always at least 1 on the very first cycle of this loop, it can be decreased without
         ;; inspecting its value first. so decrease by one, continue to next.
;; below two increments of B as this example is for prime 2.
n1 inc B n2
n2 inc B s1
s1 inc A a1 ;; inspect A. if it is 0, go to next. otherwise return to a1 for beginning of the loop.
            ;; it also removes the additional increasing done by this instruction.
s2 dec A ;; if here, loop has ended. decrease A because previous instruction increased it. go to next.

;; now B has all the data. it needs to be moved back to A.
x1 inc B x2 ;; increase B because next instruction (a loop start) will decrease it on every cycle.
x2 dec B ;; decrease B because loop keeps adding to it when skipping here.

e1 dec B ;; decrease B, now to actually reduce its value.
e2 inc A e3 ;; increase A. if A was changed from 0 to 1 go to next (e3), otherwise go to e3 (as well).
e3 inc B x2 ;; inspect B, if it was 0, loop is over, move to next (e4). otherwise return to loop start (x2).
e4 dec B ;; decrease B back to 0 because previous instruction increased it.
e5 inc A suc ;; A is known to be non-zero. increase it by one and jump to another instruction block, where A will be
             ;; immediately decreased to return it to normal.

DEC: Instruction like x DEC B suc fai becomes

;;DEC start;;
;; to decrease a register, see if it can be divided by the prime associated with the register.
;; this example set for prime 3.
a1 dec A ;; arriving here, decrease A to normal.

n1a inc A n1c ;; test A. if A was 0, go to next. otherwise n1c.
n1b inc A r0 ;; since A was 0, quit this loop to r0.
;;----
n1c dec A ;; decrease A back to normal. go to next.
n1d dec A ;; actually decrease A's value.

n2a inc A n2c ;; test A. if A was 0, go to next. otherwise n2c.
n2b inc A r1 ;; since A was 0, quit this loop to r1.
;;----
n2c dec A ;; decrease A back to normal. go to next.
n2d dec A ;; actually decrease A's value.

n3a inc A n3c ;; test A. if A was 0, go to next. otherwise n3c.
n3b inc A r2 ;; since A was 0, quit this loop to r2.
;;----
n3c dec A ;; decrease A back to normal. go to next.
n3d dec A ;; actually decrease A's value.

;; add three to B.
e1 inc B e2
e2 inc B e3
e3 inc B m1

;; A is tested for one additional time. if it is 0, the loop can be ended as A was divided without remainders.
;; otherwise, continue to the loop.
m1 inc A a1 ;; if A was 0, continue to next. otherwise jump to loop start a1 (which decreases A back to normal).

;; if here, A could be divided by three, and A's full value is copied in B.
;; thus decrease B by three for every increment of A. then go to suc instruction block.
m2 dec A ;; decrease A by one because m1 or m8 changed it. a loop starting point.
y1 dec B
y2 dec B
y3 dec B
m3 inc A m4 ;; increase A by one. go to next / m4.
m4 inc B m7 ;; if B is 0, copying is done, go to next. otherwise m7.
m5 dec B ;; return B back to zero because previous instruction increased it. go to next.
m6 inc A suc ;; increase A by one and jump to another instruction block, A always known to be non-zero here. success.

m7 dec B ;; decrease B by one to return it to normal. go to next.
m8 inc A m2 ;; increase A in order to jump to m2. A is always non-zero here so jump happens.


;; failure case.
r2 inc B r1 ;; increase B. if landing here, B will be increased by this and the next.
r1 inc B r0 ;; increase B.
r0 dec A ;; decrease A twice,
v1 dec A ;; because code before jumping here increased it twice.

v2 inc B v3 ;; increase B because next instruction will decrease it. (v3 is a loop start point.)
v3 dec B ;; decrease B (because of v2 or z3 increasing it). a loop start.
;; it is known that B is at least 1, and could not be divided by 3. return B to A and go to fai instruction block.
z1 dec B ;; decrease B. go to next.
z2 inc A z3 ;; increase A. go to next.
z3 inc B v3 ;; test B. if it is 0, go to next, loop is over. otherwise, jump to v3.
z4 dec B ;; decrease B because previous increased it. it is 0 now.
z5 inc A fai ;; here A is known to be non-zero before it's increased, so the jump will always happen. end of instruction.

HALT: Instruction like x HALT becomes

a1 dec A ;; jumping instruction blocks increases A, so decrease it by one.
a2 inc A halt ;; increase A and jump. A is always known to be non-zero here, so jump always happens.

and after the last instruction add:

halt dec A ;; decrease A to return it to normal. go to next instruction, which does not exist, so halt (successfully).

Interpreter and translator

incdecisive.py - A simple Incdecisive Machine interpreter written in Python.

mmtoinc.py - A translator that translates the given Minsky Machine program into a 2-register Incdecisive Machine program (default), if given an additional parameter such as "abc" creates the simpler translation that uses x+1 registers.

-- Keymaker, 20.9.2022