Single Instruction URM Programs/Projection Function

Theorem

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$

are each URM computable by a single-instruction URM program.

Proof

The projection functions are computed by the following URM program:

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

The input $\tuple {n_1, n_2, \ldots, n_j, \ldots, n_k}$ is in $R_1, R_2, \ldots, R_j, \ldots, R_k$ when the program starts.

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

The output $n_j$ is in $R_1$ when the program terminates.

$\blacksquare$