Single Instruction URM Programs

From ProofWiki
Jump to navigation Jump to search

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: I_\N \left({n}\right) = 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$ $J \left({m, n, q}\right)$

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$ $J \left({m, n, 1}\right)$

does not specify a URM computable function, as:

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$