Single Instruction URM Programs

Theorem

Basic Primitive Recursive Functions

The basic primitive recursive functions are URM computable by a single-instruction URM program:

Zero Function

The zero function $\Zero: \N \to \N$, defined as:

$\forall n \in \N: \map \Zero n = 0$

Successor Function

The successor function $\Succ: \N \to \N$, defined as:

$\forall n \in \N: \map \Succ n = n + 1$

Projection Function

The projection functions $\pr_j^k: \N^k \to \N$, defined as:

$\forall j \in \closedint 1 k: \forall \tuple {n_1, n_2, \ldots, n_k} \in \N^k: \map {\pr_j^k} {n_1, n_2, \ldots, n_k} = n_j$

Identity Function

The identity function $I_\N: \N \to \N$ defined as:

$\forall n \in \N: \map {I_\N} n = n$

No other functions $f: \N^k \to \N$ can be computed using a single-instruction URM program.

Proof

Apart from the programs given, the only other single-instruction programs are of the form:

Line		Command
$1$		$\map J {m, n, q}$

The convention is that, at the start of the program, $R_1$ contains the input, and all other registers contain $0$.

Suppose $q > 1$.

Then whatever $m$ or $n$ are, the program either jumps to $q$ (a location outside the program) or steps one instruction.

In either case the program stops without changing what is in $R_1$.

Hence this is another way of computing the identity function $I_\N$.

Suppose $q = 1$.

If $m = n$, then whatever is held in the registers, $r_m = r_n$ and the program will go back to execute step 1 again.

Thus the program will loop round and do step 1 endlessly, and never terminate.

If $m \ne n$, then the program's behaviour depends on the contents of $R_n$ and $R_m$.

If $m = 1$ and $n \ne 1$, then the program will compare the input against the contents of $r_n$.

If $r_1 = 0$ the program will go into an endless loop, and never terminate.

Otherwise, i.e. if $r_1 \ne 0$, the program will never terminate with $r_1$ unchanged.

If $m \ne 1$ and $n \ne 1$ then the program will once more never terminate, as $r_m = r_n = 0$ at the start of the program.

So the program:

Line		Command
$1$		$\map J {m, n, 1}$

does not specify a URM computable function, as:

when $m = n$ the program will never terminate for any input

when $m \ne n, m = 1$ the program will never terminate on input $0$

when $m \ne n, n = 1$ the program similarly will never terminate on input $0$

when $m \ne n, m \ne 1, n \ne 1$ the program will never terminate for any input.

In all cases there is at least one input for which the program will never terminate.

The result follows from the definition of URM computability.

$\blacksquare$