Two counters already = Turing power
Parent: minsky-machine
Minsky (1961)A counter machine with just two registers can simulate any Turing machine — so
INC+test/DECon two unbounded counters is already Turing-complete (and its halting problem is undecidable).
Why (the encoding)
A TM tape splits at the head into a left half and a right half — two stacks (one stack vs two). Encode each stack of symbols as one number (e.g. base-k digits, or prime powers). Then:
- moving the head = pop a digit off one number and push it onto the other = divide one counter / multiply the other — and multiply/divide by a constant is just repeated [[minsky-examples|
INC/DECloops]]; - reading/writing the scanned symbol = looking at the low digit = a bounded
mod/div, again loops.
So 2 stacks = 2 numbers = 2 counters = one tape = Turing. (Three counters simulate a TM directly — one per stack + a scratch; squeezing to two needs the extra Gödel-style number encoding, which is slow but works.)
The lesson
Adding any unbounded, zero-testable memory to a finite control gives full computation — the same sudden jump as one stack → two, or a single [[recursive-functions|μ-operator]]. Turing power is cheap; it's decidability that's expensive. That cheapness is exactly why counter machines are the favorite tool for building undecidability (e.g. the generalized-collatz reduction encodes a counter machine).