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 of the instructions in this list is one of the following:

• INC (j, k) — increment the value of register 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.

It may also be convenient to consider TEST to be separate from DEC; this causes no change in conceptual power, as any program in one variant can be straightforwardly translated to the other; however, traditional explanations of the Register machine (such as Minsky 1961) always describe DEC as including a test and branch.

See also

• Turing machine
• Halting problem
• The article on counters has a proof that two-counter machines are Turing-powerful.

References

External links

• Igblan - Minsky Register Machines

Computational models

Registermaschine | 寄存器机