Definition:Unlimited Register Machine
 | This page has been identified as a candidate for refactoring of advanced complexity. Until this has been finished, please leave {{Refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code. |
Definition
An unlimited register machine, abbreviated URM, is an abstract machine with the following characteristics:
Registers
A URM has a sequence of registers which can store natural numbers: $\set {0, 1, 2, \ldots}$.
Any given URM program may make use of only a finite number of these registers.
Registers are usually referred to by the subscripted uppercase letters $R_1, R_2, R_3, \ldots$.
The number held at any one time by a register is usually referred to by the corresponding lowercase letter $r_1, r_2, r_3, \ldots$.
The registers are unlimited in the following two senses:
- $(1): \quad$ Although a URM program may make use of only a finite number of registers, there is no actual upper bound on how many a particular URM program can actually use.
- $(2): \quad$ There is no upper bound on the size of the natural numbers that may be stored in any register.
Program
The numbers held in the registers of a URM are manipulated according to a program.
A URM program is a finite sequence of basic instructions.
Operation
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.
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.
Input
The input to a URM program is:
- either an ordered $k$-tuple $\tuple {n_1, n_2, \ldots, n_k} \in \N^k$
- or a natural number $n \in \N$.
In the latter case, it is convenient to consider a single natural number as an ordered $1$-tuple $\tuple {n_1} \in \N^1 = \N$.
Hence we can discuss inputs to URM programs solely as instances of tuples, and not be concerned with cumbersome repetition for the cases where $k = 1$ and otherwise.
The convention usually used is for a URM program $P$ to start computation with:
- the input $\left({n_1, n_2, \ldots, n_k}\right)$ in registers $R_1, R_2, \ldots, R_k$
- $0$ in all other registers used by $P$.
That is, the initial state of the URM is:
- $\forall i \in \closedint 1 k: r_i = n_i$
- $\forall i > k: r_i = 0$.
It is usual for the input (either all or part) to be overwritten during the course of the operation of a program. That is, at the end of a program, $R_1, R_2, \ldots, R_k$ are not guaranteed still to contain $n_1, n_2, \ldots, n_k$ unless the program has been explicitly written so as to ensure that this is the case.
Output
At the end of the running of a URM program, the output will be found in register $R_1$.
Null Program
The null URM program is a URM program which contains no instructions.
That is, a URM program whose length is zero.
Comment
The particular details of a URM may differ between presentations.
The one defined here closely follows the design of that in Nigel J. Cutland.
Also see
- Results about unlimited register machines can be found here.
Historical Note
The unlimited register machine is a more versatile and easy to understand alternative to the Turing machine, which has the same capabilities and (to a certain extent) to which it is logically equivalent.
It was introduced in a paper by John C. Shepherdson and Howard E. Sturgis published in $1963$.
Sources
- 1963: John C. Shepherdson and H.E. Sturgis: Computability of Recursive Functions (J. ACM Vol. 10, no. 2: pp. 217 – 255)