Minsky 机——小程序

父节点：minsky-machine

一切都由 INC 和 test/DEC 构建而成。（Rj 表示寄存器 j。）

加法：R1 := R1 + R2（消耗 R2）

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

“把 R2 一点一点地倒进 R1。”

在 R1=2, R2=3 上的执行轨迹：

复制：R2 := R1（非破坏性，借助临时寄存器 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

最终 R2 = R1，且 R1 被复原——你无法在不破坏的情况下读取，所以要借一个备用寄存器中转，再把它放回去。

乘法：R3 := R1 * R2

把 R1 加到 R3 上恰好 R2 次（用复制技巧让 R1 每一轮都能保留下来）。你能用的只有重复加法——但这就够了。

一个模拟器（Haskell——程序即数据）

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)

与 TM simulator 同构：一个微型驱动器 + 作为数据的程序——这正是 universal machine 得以成立的原因。