A machine made of numbers
A counter machine has no tape, no stack and no named variables of the usual kind. It has a small, fixed number of registers, each holding a non-negative whole number, and a short list of numbered instructions. This model is associated with the logician Marvin Minsky, and languages built the same way are often called Minsky style or register machine languages.
The usual instruction set has just two operations on a counter, plus control:
- INC r adds 1 to register r, then goes to the next instruction.
- DECJZ r, n checks register r. If it is zero, jump to instruction n. Otherwise subtract 1 from it and go to the next instruction.
- JUMP n goes to instruction n. Some presentations leave it out, since it can be built from the others with a spare register that stays at zero.
- HALT stops the machine.
Notice what is missing: there is no way to add two registers, copy a value or compare two numbers directly. Everything has to be built from counting up and down.
A first program: addition
Suppose r0 and r1 hold hypothetical starting values 2 and 3, and we want the sum in r0. The idea is to drain r1 into r0 one unit at a time.
0: DECJZ r1, 3
1: INC r0
2: JUMP 0
3: HALTTrace it. At instruction 0, r1 is 3, so it is not zero: r1 becomes 2 and execution continues. Instruction 1 raises r0 to 3. Instruction 2 jumps back to 0. The second pass takes r1 to 1 and r0 to 4. The third pass takes r1 to 0 and r0 to 5. On the fourth visit to instruction 0, r1 is zero, so it jumps to 3 and halts. The final state is r0 = 5, r1 = 0, which matches 2 + 3. Notice the cost. Like the Brainfuck move loop, the addition destroys r1. Copying a value needs a third register used as scratch, exactly as copying on a tape needs a scratch cell.
Relationship to Brainfuck
The link is close. A Brainfuck cell is a counter, + and - are increment and decrement, and [ … ] is a test for zero. The extra thing Brainfuck has is the tape, which means the program can choose which counter to act on by moving a pointer, so it can address as many counters as it likes. A counter machine has a fixed set of named registers, which makes it more restricted but easier to reason about.
Why two counters can be enough
A striking result associated with Minsky is that a machine with only two counters can, in principle, simulate any computation, provided the counters can hold arbitrarily large numbers. The trick is to encode a whole tape or several variables into a single enormous number, for instance by packing values into the exponents of prime factors. Updating the encoded data then means multiplying or dividing that number, which counters can do through repeated counting.
This is a statement about theory, not practice. The encoding is extremely slow and the numbers grow quickly, so nobody would write a real program that way. Its value is as a proof that very little machinery is needed to get a universal model, and it connects to the Turing machine, to the Church-Turing thesis, and to the general idea of Turing completeness.
Infinite memory is doing the work
Counters in theory can hold any size of number, which is a kind of infinite memory. A real machine has a fixed number of bits, so a real counter wraps or overflows. With bounded counters, the machine has only finitely many states and is no more powerful than the finite automata that are used to model simple pattern matching. Whether a language is universal depends on that assumption of unbounded storage, which is why practical languages are universal only up to the limits of the hardware.
The halting problem on counter machines
Because the model is so small, it is a popular setting for studying what cannot be decided. Asking whether a given counter machine program eventually halts is the halting problem in a very simple form. The question stays undecidable even when the machine has just two counters. A small instruction set makes the proofs concrete, and that is much of the reason these machines appear in textbooks.
Counter machines in esoteric languages
Some hobby languages take the model almost literally, with a handful of registers and a few commands, and others disguise it. Rewriting systems such as tag systems are close relatives, and minimal models of this kind can typically be translated into one another, which connects with the broader topic of language translation. Writing a small interpreter for a counter machine is a good exercise because the whole language fits in a dozen lines.
Takeaway
A counter machine strips a language to count, count down, and check for zero. Everything else, including arithmetic, copying and data structures, is built from those. It is a clean way to see how a conditional loop and unbounded numbers together are enough for universal computation in principle.