a counter (register) machine

Imagine a clerk with a fixed number of tally boxes and a tiny rulebook. Each box can hold any whole number of pebbles. The rulebook lets the clerk do only two kinds of thing: add one pebble to a box, or try to remove one pebble from a box (and, if the box was already empty, jump to a different rule instead). That is the whole repertoire. A counter machine, also called a register machine, is exactly this stripped-down computer: a finite program operating on a few integer counters with just increment, decrement, and test-for-zero.

Formally, a counter machine has a fixed finite set of registers, each holding a natural number, and a finite numbered list of instructions. The typical instructions are INC(r) (add 1 to register r, go to the next instruction), and a combined test-and-decrement: 'if register r is zero, jump to instruction j; otherwise subtract 1 from r and continue'. Input is loaded into one register as a number; the machine halts with its answer in a register. There are no symbols, no tape, no string, just counting up and down and branching on whether a counter has hit zero.

The startling theorem is that a machine with just two counters and this minuscule instruction set is already Turing-complete: it can compute every Turing-computable function. The trick is encoding: you can pack the entire contents of several work-tapes or registers into a single integer (for example using powers of primes, like 2^a * 3^b * 5^c), and then increment, decrement, and zero-testing are enough to read and update that encoding. Counter machines matter because they show how breathtakingly little hardware computation requires, and they are a favorite tool for undecidability proofs precisely because their bare-bones structure makes simulations easy to write down. The honest caveat: 'two counters suffice' is a beautiful result about computability, not efficiency, the encodings make such machines absurdly slow.