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