Definition:Unlimited Register Machine/Operation
Definition
When a URM runs a program, it always starts by executing the first instruction of the program.
When it has executed an instruction, it moves to the next instruction and executes that one, unless required otherwise by a Jump instruction.
Execution
The operation of carrying out a basic URM instruction is referred to as execution.
Instruction Pointer
The line number of the instruction which is currently about to be executed is known as the instruction pointer.
It can be imagined as a special-purpose register in the URM whose purpose is to hold that line number.
Stage of Computation
The stage of computation (or just stage) of a URM program is the count of how many instructions have been executed.
Thus each stage corresponds to the processing of one instruction.
State
The state of a URM program at a particular stage is defined as:
- $(1): \quad$ the value of the instruction pointer
- $(2): \quad$ the values contained by each of the registers that are used by the URM program.
Also see
- Results about unlimited register machines can be found here.
Sources
- 1963: John C. Shepherdson and H.E. Sturgis: Computability of Recursive Functions (J. ACM Vol. 10, no. 2: pp. 217 – 255)