Minsky (register / counter) machines

Parent: logic

The minimal assembly language for computability — a finite program over a few integer registers. Because it's as powerful as a Turing machine with almost nothing, it's the easiest model to reduce from in undecidability proofs.

Counter machine

Finitely many registers r₁,…,rₖ, each holding a natural number, and a finite numbered program of two instruction kinds:

INC(rⱼ); goto L — add 1 to rⱼ;

if rⱼ>0 then DEC(rⱼ); goto L₁ else goto L₂ — the only test (zero-test fused with decrement). Halt at a designated instruction.

That's it — no tape, just increment, and test-and-decrement.

Is this the "register" in a real CPU?

Same idea, different essentials. A Minsky register is an unbounded natural-number counter with only inc / dec / test-zero; a CPU register is fixed-width (e.g. 64-bit) with a full ALU and there are only a fixed handful. The register machine (Minsky; Shepherdson–Sturgis) was designed to look like a real computer (registers + a program counter), so it's the bridge from Turing-machine theory to assembly-language practice — real assembly is a richer register machine. The crucial gap is unbounded vs finite: a real machine with finite memory is a (huge) finite-state machine; its Turing-completeness is the idealization of unbounded memory, and Minsky's counter is that idealization in its purest form. (The realistic idealization used in algorithm analysis is the RAM model; the 2-counter machine is its minimal cousin.)

Children

minsky-examples — small programs (add, copy, multiply) traced by hand, plus a Haskell simulator.
two-counters-turing — why two counters already give full Turing power (the tape encoding).