Incrementing machine
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.
Specification
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 the following instructions:
INC x y - Increment counter x and jump to line y DEC x y - Decrement counter x and if result was 0 jump to line y
If a command has only one argument, it means that it would jump to the next command
Which can simulate Minsky machine JZDEC x y instruction like that:
INC x DEC x y DEC x
Each counter is represented as two Incrementing machine counters, called a and b. INC instruction is simulated like that:
<line number> a a y
DEC instruction is simulated like that:
<line number> b a y
Where y is the line to which it should jump to. It will also prove that it needs only 4 counters to be Turing complete
Implementations
The following Python script is an interpreter.
prgm = [[]]
prgm.pop(0)
while True:
line = input('%s ' % len(prgm)) # Generates labels automatically
if line != "eof":
line = list(line.split(" "))
prgm.append([int(line[0]), int(line[1]), int(line[2])])
else: break
tape = [0]
for i in range(0, 256): # Expansion is trivial
tape.append(0)
# Executes the program
def incmac(label, counter1, counter2, branch):
global tape
global inst
tape[counter1] += 1
if tape[counter1] == tape[counter2]:
inst = branch
else: inst += 1
print(tape[counter1], end=" ") # For debugging
inst = 0
while inst < len(prgm):
incmac(inst, prgm[inst][0], prgm[inst][1], prgm[inst][2])
256-cell implementation, but it can be expanded.