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 number of locations called registers which can store natural numbers: $\set {0, 1, 2, \ldots}$.
Any given URM program may make use of only a finite number of registers.
Registers are usually referred to by the subscripted uppercase letters $R_1, R_2, R_3, \ldots$. The subscript (which is a natural number) is called the index of the register.
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 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 list of basic instructions.
The instructions are written in a fixed order and numbered $1, 2, 3, \ldots$.
For historical reasons, the number of the instruction is called its line number.
We can refer either to the line of the program or the line in the URM.
It is convenient to use $\Bbb U$ to stand for the set of all URM programs.
Length of Program
Let $P \in \Bbb U$ be a URM program.
By definition, $P$ is a finite list of basic instructions.
We define the function $\lambda: \Bbb U \to \N$ as follows:
- $\forall P \in \Bbb U: \map \lambda P = \text { the number of basic instructions that comprise } P$.
Number of Registers Used
Let $P \in \Bbb U$ be a URM program.
By definition, $P$ uses a finite number of registers.
We define the function $\rho: \Bbb U \to \N$ as follows:
- $\forall P \in \Bbb U: \map \rho P = \text{ the highest register number used by } P$.
So in any URM program $P$, no instruction refers to any register with index greater than $R_u$, where $u = \map \rho P$.
Basic Instructions
| Name | Notation | Effect | Description |
|---|---|---|---|
| Zero | $\map Z n$ | $0 \to R_n$ | Replace the number in $R_n$ by $0$. |
| Successor | $\map S n$ | $r_n + 1 \to R_n$ | Add $1$ to the number in $R_n$. |
| Copy | $\map C {m, n}$ | $r_m \to R_n$ | Replace the number in $R_n$ by the number in $R_m$ (leaving the one in $R_m$ as it was). |
| Jump | $\map J {m, n, q}$ | $r_m = r_n ? \Rightarrow q$ | If the numbers in $R_m$ and $R_n$ are equal, go to instruction number $q$, otherwise go to the next instruction. |
Basic instructions are also (and more commonly) known as commands, because the word's shorter and quicker to say.
Operation
When a URM runs a program, it always starts by executing the first instruction of the program.
When it has carried out an instruction, it moves to the next instruction and executes that one, unless required otherwise by a Jump instruction.
Instruction Pointer
The line number 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 that holds the line number.
Stage of Computation
The stage of computation (or just stage) of a URM program is the count of how many basic instructions have been carried out.
Thus each stage corresponds to the processing of one instruction.
State
The state (or situation) of a URM program at a particular point in time is defined as:
- the value of the instruction pointer
- the value, at that point, of each of the registers that are used by the program.
Termination
A URM program stops, or terminates, or halts, when there are no more instructions to carry out. This can happen in either of two ways:
- $(1): \quad$ If the program carries out the last instruction, and this does not involve a Jump to an earlier instruction, the program will stop.
- $(2): \quad$ If the program carries out a Jump instruction to a non-existent instruction, the program will stop. Such a Jump instruction is known as an exit jump .
The line on which a particular run of a URM program stops is called the exit line.
If the program, when running, never reaches such a state, then it is said to be in an endless loop and will never terminate.
Note that whether a program terminates or not may depend on its input.
It may terminate perfectly well for one input, but go into an endless loop on another.
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
A null program or empty program is a URM program which contains no instructions.
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)