# 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.
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)