Single Instruction URM Programs/Projection Function
Jump to navigation
Jump to search
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$