In theoretical computer science a register machine is an abstract machine used to study decision problems, similar to how a Turing machine is used. Register machines are also sometimes called counter machines (because the registers act like counters), Minsky machines (because they were introduced and developed by Marvin Minsky), or program machines (this being what Minsky called them).

The computational power of register machines is equivalent to that of Turing machines, although due to their unary processing style, register machines are typically slower by a factor that is exponential in the space used by the comparable Turing Machine.

Definition

A register machine consists of a finite set of registers r₁ ... r_n, each of which can hold a non-negative integer, and a finite list of instructions I₁ ... I_m. Each instruction can only be either:

• INC (j, k) — increment the value of r_j by 1, then jump to instruction I_k.
• DEC (j, k, z) — check if the value of r_j is zero. If so, jump to instruction I_z; otherwise, decrement r_j by 1 and jump to I_k.
• HALT — halts the computation.

See also

• Turing machine
• Halting problem