Definition:Unlimited Register Machine/Program
 | 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
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.
Basic Instruction
The basic instructions of a URM program form a finite sequence and hence can be considered a set indexed by the (positive) integer $1, 2, 3, \ldots$.
Execution
The operation of carrying out a basic URM instruction is referred to as execution.
Line Number
For historical reasons, the index of an instruction in a given URM program is called its line number.
We can refer either to the line of the program or the line in the URM.
Set of All URM Programs
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 sequence of basic instructions.
We define the function $\lambda: \Bbb U \to \N$ as follows:
- $\forall P \in \Bbb U: \map \lambda P = $ the number of basic instructions that comprise $P$
Thus $\map \lambda P$ is referred to as the length of $P$.
Highest Register
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 =$ the highest register number used by $P$
That is, in any URM program $P$, no instruction refers to any register with index greater than $\map \rho P$.
Highest Register
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 =$ the highest register number used by $P$
That is, in any URM program $P$, no instruction refers to any register with index greater than $\map \rho P$.
Termination
A URM program terminates when there are no more instructions to execute.
This can happen in either of two ways:
- $(1): \quad$ If the program executes the last instruction, and this does not involve a Jump to an earlier instruction, the program will stop.
- $(2): \quad$ If the program executes a Jump instruction to a non-existent instruction, the program will stop.
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$.
Also see
- Results about URM programs 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)