Home > Register machine

1 Definition

A register machine can be seen as a finite set of registers r₁ ... r_n, each of which can hold a non-negative integer, and a finite set 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.

2 See also

• Turing machine
• Halting problem