Single Instruction URM Programs/Identity Function

Theorem

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

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

is URM computable by a single-instruction URM program.

Proof

Any of the following URM programs compute the identity function:

Line		Command
$1$		$\map Z m$

... where $m \ne 1$.

This sets the value $0$ into $R_m$ and then stops.

Line		Command
$1$		$\map S m$

... where $m \ne 1$.

The input $n$ is in $R_1$ when the program starts.

The program adds $1$ to $r_m$ and then stops.

Line		Command
$1$		$\map C {j, m}$

... where $m \ne 1$.

The input $n$ is in $R_1$ when the program starts.

The program copies $r_j$ to $r_m$ and then stops.

Line		Command
$1$		$\map C {1, 1}$

The input $n$ is in $R_1$ when the program starts.

The program copies $r_1$ to $r_1$, i.e. to itself, and then stops.

In none of these programs is $R_1$ affected, and so no change is effected to the input, which is returned as the output unchanged.

Hence they all compute the identity function.

$\blacksquare$

Note that the latter program, consisting entirely of $\map C {1, 1}$, is a direct implementation of the projection function program $\pr^1_1: \N \to \N$.

This latter function is the usual way of implementing the identity function as it is well-defined and obvious, and guaranteed to have no other side-effects when embedded in a larger program.