Definition:Unlimited Register Machine/Program/Termination
This page has been identified as a candidate for refactoring of advanced complexity. Until this has been finished, please leave {{Refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. 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
A URM program terminates when there are no more instructions to execute.
This can happen in either of two ways:
- $(1): \quad$ If the program executes the last instruction, and this does not involve a Jump to an earlier instruction, the program will stop.
- $(2): \quad$ If the program executes a Jump instruction to a non-existent instruction, the program will stop.
Exit Jump
Definition:Unlimited Register Machine/Program/Termination/Exit Jump
Such a Jump instruction is known as an exit jump .
Exit Line
Definition:Unlimited Register Machine/Program/Termination/Exit Line
The line on which a particular run of a URM program stops is called the exit line.
Endless Loop
Definition:Unlimited Register Machine/Program/Termination/Endless Loop
If a URM program, when running, never reaches a state where it terminates, then it is said to be in an endless loop and will never terminate.
This page or section has statements made on it that ought to be extracted and proved in a Theorem page. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by creating any appropriate Theorem pages that may be needed. To discuss this page in more detail, feel free to use the talk page. |
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.
Also known as
When a URM program terminates, it can also be said that it stops or halts.
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
A null program or empty program is a URM program which contains no instructions.
Also see
- Results about URM programs 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)