Register machine
|
|
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 r1 ... rn, each of which can hold a non-negative integer, and a finite list of instructions I1 ... Im. Each instruction can only be either:
-
INC (j, k)— increment the value of rj by 1, then jump to instruction Ik. -
DEC (j, k, z)— check if the value of rj is zero. If so, jump to instruction Iz; otherwise, decrement rj by 1 and jump to Ik. -
HALT— halts the computation.