Single Instruction URM Programs/Identity Function

From ProofWiki
Jump to navigation Jump to search

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.