Definition
Unrestricted Register Machine
An unrestricted register machine (URM) is a deterministic computational model with registers
, each containing a natural number, and a finite program . In a standard instruction set, for register indices
and instruction label :
: set . : set . : copy , leaving unchanged. : jump to if ; otherwise continue with the next instruction. Execution starts at
. Each non-jump instruction continues with the next instruction; reaching a label outside halts the machine. For input
, initially for and all other registers contain . The output is the final value of ; if execution never halts, the output is undefined. Unrestricted means that neither register contents nor the available register indices have a fixed upper bound. Each finite program nevertheless uses only finitely many registers, and each terminating computation takes finitely many steps.
Explicit return
An optional instruction
halts and returns . It adds no computability power: copy into with , then jump outside the program using .