Definition:Unlimited Register Machine/Program/Basic Instruction
< Definition:Unlimited Register Machine | Program(Redirected from Definition:Basic URM Instruction)
Jump to navigation
Jump to search
Definition
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$.
The basic instructions are as follows:
| Name | Notation | Effect | Description |
|---|---|---|---|
| Zero | $\map Z n$ | $0 \to R_n$ | Replace the number in $R_n$ by $0$. |
| Successor | $\map S n$ | $r_n + 1 \to R_n$ | Add $1$ to the number in $R_n$. |
| Copy | $\map C {m, n}$ | $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 | $\map J {m, n, q}$ | $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. |
Execution
The operation of carrying out a basic URM instruction is referred to as execution.
Also known as
Basic URM instructions are also (and more commonly) known as commands, because the word is shorter and quicker to say.
During the course of the exposition, the term instruction will also be found, which again means the same thing.
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)