Definition:Unlimited Register Machine

From ProofWiki
Jump to navigation Jump to search


An unlimited register machine, abbreviated URM, is an abstract machine with the following characteristics:


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.


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.


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.


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.


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.


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.


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