# Single Instruction URM Programs/Identity Function

## Theorem

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

- $\forall n \in \N: I_\N \left({n}\right) = n$

is URM computable by a single-instruction URM program.

## Proof

Any of the following URM programs compute the identity function:

Line | Command | |
---|---|---|

$1$ | $Z \left({m}\right)$ |

... where $m \ne 1$.

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

Line | Command | |
---|---|---|

$1$ | $S \left({m}\right)$ |

... 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$ | $C \left({j, m}\right)$ |

... 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$ | $C \left({1, 1}\right)$ |

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 $C \left({1, 1}\right)$, is a direct implementation of the projection function program $\operatorname{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.