Minsky machine — small programs

Parent: minsky-machine

Everything is built from INC and test/DEC. (Rj = register j.)

Addition: R1 := R1 + R2 (consumes R2)

L0: if R2 > 0 then { DEC R2; goto L1 } else goto END
L1: INC R1; goto L0
END: halt

"Pour R2 into R1, one unit at a time."

Trace on R1=2, R2=3:

Copy: R2 := R1 (non-destructive, via temp R3)

A: if R1>0 then { DEC R1; INC R2; INC R3; goto A } else goto B   # drain R1 into R2 and R3
B: if R3>0 then { DEC R3; INC R1; goto B } else halt             # refill R1 from R3

Leaves R2 = R1 with R1 restored — you can't read without destroying, so you copy through a spare and put it back.

Multiply: R3 := R1 * R2

Add R1 to R3 exactly R2 times (using the copy trick so R1 survives each round). Repeated addition is all you have — and it's enough.

A simulator (Haskell — program is data)

import qualified Data.Map as M
data Instr = Inc Int Int          -- Inc r goto
           | Dec Int Int Int      -- Dec r ifPositive ifZero
           | Halt
type Prog = M.Map Int Instr       -- label -> instruction
type Regs = M.Map Int Int

step :: Prog -> (Int, Regs) -> Maybe (Int, Regs)
step p (pc, rs) = case M.lookup pc p of
  Just (Inc r l)     -> Just (l, M.insertWith (+) r 1 rs)
  Just (Dec r pos z) -> case M.findWithDefault 0 r rs of
                          0 -> Just (z,   rs)
                          n -> Just (pos, M.insert r (n-1) rs)
  _                  -> Nothing            -- Halt (or fell off) -> stop

run :: Prog -> (Int, Regs) -> (Int, Regs)
run p st = maybe st (run p) (step p st)

Same shape as the TM simulator: a tiny driver + the program as data — which is exactly what makes a universal machine possible.