/minsky

Minsky machine simulator.

Primary LanguagePython

Minsky Machine.

A Minsky machine (aka a register machine) is a model of computation. It has a finite number of registers and labelled instructions. There are three kinds of instructions:

  • Add 1 to a register and goto a line.
  • Check if a register contains a value greater than 0. If it does, subtract 1 and goto a line. If it doesn't, do nothing and goto another line.
  • Halt computation.

To run a Minsky machine on input x, the machine is started with register 1 containing x and the rest containing 0. The output of a Minsky machine is the value in register 1 when it halts.

The Simulation.

Programs to a Minsky machine are specified in .minsky files. They can be run like so:

python3 minsky.py --machine is_odd.minsky --input 2

This means "run the program is_odd on input 2":

Input: [2]
Output: [1]

There is an optional flag, trace, which you can use to see what the machine is doing step-by-step.

python3 minsky.py --machine is_odd.minsky --input 5 --trace True
Input: [2]
[1] 	 Sub 1 from r0, goto 2
[0] 	 Sub 1 from r0, goto 1
[0] 	 r0 is empty, goto 3
[1] 	 Add 1 to r0, goto 4
[1] 	 HALT
Output: [1]