Definition:Unlimited Register Machine

From ProofWiki
(Redirected from Definition:URM Program)
Jump to: navigation, search

Definition

An unlimited register machine, abbreviated URM, is an abstraction (or idealization) of a computing device with the following characteristics:


Registers

A URM has a number of locations called registers which can store natural numbers: $\left\{{0, 1, 2, \ldots}\right\}$.

Any given URM program may make use of only a finite number of registers.

Registers are usually referred to by the subscripted uppercase letters $R_1, R_2, R_3, \ldots$. The subscript (which is a natural number) is called the index of the register.

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:


Program

The numbers held in the registers of a URM are manipulated according to a program.

A URM program is a finite list of basic instructions.


The instructions are written in a fixed order and numbered $1, 2, 3, \ldots$.

For historical reasons, the number of the instruction is called its line number.

We can refer either to the line of the program or the line in the URM.


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 list of basic instructions.


We define the function $\lambda: \Bbb U \to \N$ as follows:

$\forall P \in \Bbb U: \lambda \left({P}\right) = \text{the number of basic instructions that comprise } P$.


Number of Registers Used

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: \rho \left({P}\right) = \text{the highest register number used by } P$.

So in any URM program $P$, no instruction refers to any register with index greater than $R_u$, where $u = \rho \left({P}\right)$.


Basic Instructions

Name Notation Effect Description
Zero $Z \left({n}\right)$ $0 \to R_n$ Replace the number in $R_n$ by $0$.
Successor $S \left({n}\right)$ $r_n+1 \to R_n$ Add $1$ to the number in $R_n$.
Copy $C \left({m, n}\right)$ $r_m \to R_n$ Replace the number in $R_n$ by the number in $R_m$ (leaving the one in $R_m$ as it was).
Jump $J \left({m, n, q}\right)$ $r_m = r_n ? \Rightarrow q$ If the numbers in $R_m$ and $R_n$ are equal, go to instruction number $q$, otherwise go to the next instruction.

Basic instructions are also (and more commonly) known as commands, because the word's shorter and quicker to say.


Operation

  • When a URM runs a program, it always starts by executing the first instruction of the program.
  • When it has carried out an instruction, it moves to the next instruction and executes that one, unless required otherwise by a Jump instruction.


Instruction Pointer

The line number 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 that holds the line number.


Stage of Computation

The stage of computation (or just stage) of a URM program is the count of how many basic instructions have been carried out.

Thus each stage corresponds to the processing of one instruction.


State

The state (or situation) of a URM program at a particular point in time is defined as:


Termination

A URM program stops, or terminates, or halts, when there are no more instructions to carry out. This can happen in either of two ways:

  1. If the program carries out the last instruction, and this does not involve a Jump to an earlier instruction, the program will stop.
  2. If the program carries out a Jump instruction to a non-existent instruction, the program will stop. Such a Jump instruction is known as an exit jump .

The line on which a particular run of a URM program stops is called the exit line.


If the program, when running, never reaches such a state, then it is said to be in an endless loop and will never terminate.


Note that whether a program terminates or not may depend on its input.

It may terminate perfectly well for one input, but go into an endless loop on another.


Input

The input to a URM program is:


In the latter case, it is convenient to consider a single natural number as an ordered $1$-tuple $\left({n_1}\right) \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 \left[{1 \, . \, . \, k}\right]: 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

A null program or empty program is a URM program which contains no instructions.


Comment

The particular details of a URM may differ between presentations.

The one defined here closely follows the design of that in Cutland[1].


Historical Note

The URM 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 J. C. Shepherdson and H. E. Sturgis[2] published in 1963.


References

  1. Nigel Cutland: Computability (Cambridge University Press, 1980).
  2. John C. Shepherdson, Howard E. Sturgis: Computability of Recursive Functions. J. ACM 10(2): 217-255 (1963).