# Definition:Unlimited Register Machine/Register

Jump to navigation
Jump to search

## Definition

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**.

### Index of Register

The subscript (which is a natural number) appended to a **URM register** is called the **index** of that **register**.

Hence, for example, the **index** of **register** $R_5$ is $5$.

## Also see

- Results about
**unlimited register machines**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)