Theorem: Function Obtained by Primitive Recursion from URM Computable Functions

Let the functions $f: \N^k \to \N$ and $g: \N^{k + 2} \to \N$ be URM computable functions.
Let $h: \N^{k + 1} \to \N$ be obtained from $f$ and $g$ by primitive recursion.
Then $h$ is also URM computable.

Proof:
From the definition:
:$\forall n \in \N: \map h {n_1, n_2, \ldots, n_k, n} = \begin {cases}
\map f {n_1, n_2, \ldots, n_k} & : n = 0 \\
\map g {n_1, n_2, \ldots, n_k, n - 1, \map h {n_1, n_2, \ldots, n_k, n - 1} } & : n > 0 
\end {cases}$
Let $P$ and $Q$ be normalized URM programs which compute $f$ and $g$ respectively.
Let $s = \map \lambda P$ and $t = \map \lambda Q$ be the number of basic instructions in $P$ and $Q$.
Let $u = \max \set {\map \rho P, \map \rho Q, k + 2}$.
{{explain|What's $\rho$? Should it be $\lambda$}}
Thus registers $R_{u + 1}, R_{u + 2}, \ldots$ are neither used by $P$ nor $Q$ nor for input.
So they can be used for storing values.
The following algorithm can be followed to create a URM program $H$ to compute $h$.
We assume that the input is $\tuple {n_1, n_2, \ldots, n_k, n}$, which is held in $R_1, R_2, \ldots, R_k, R_{k + 1}$.
The plan is that the program will compute $\map h {n_1, n_2, \ldots, n_k, i}$ for $i = 0, 1, 2, \ldots, n$ in order.
At the end of the last iteration, $\map h {n_1, n_2, \ldots, n_k, n}$ will be left in $R_1$.
We are to use the following registers:
:$R_{u + 1}, R_{u + 2}, \ldots, R_{u + k + 1}$ will be used to store the input $\tuple {n_1, n_2, \ldots, n_k, n}$ so it does not get overwritten.
::We note that $R_{u + k + 1}$ will hold the value of $n$.
:$R_{u + k + 2}$ will hold the current value of the recursion variable $i$.
When $r_{u + k + 2} = r_{u + k + 1}$, the computation will have ended.
{| border="1"
|-
! align="right" | Step !!
! align="left" | Process
! align="left" | Notes
! align="left" | $\map \lambda H$
|-
| align="right" | $1$ ||
| align="left" | Append a Block Copy Program $\map C {1, u + 1, k + 1}$ to $H$<ref>$H$, at this point, is a null URM program.</ref>.
| This stores the input somewhere safe so it can be accessed again later.
| $k + 1$
|-
| align="right" | $2$ ||
| align="left" | Append $\map Z {k + 1}$ to $H$.
| This clears $R_{k + 1}$ so that $R_1, R_2, \ldots, R_{k + 1}$ holds the input for calculating $f$.
| $k + 2$
|-
| align="right" | $3$ ||
| align="left" | Increment the <tt>Jump</tt>s in $P$ by $k + 2$ lines<ref>To '''increment the <tt>Jump</tt>s by $r$''' for any normalized URM program is done by changing all <tt>Jump</tt>s of the form $\map J {m, n, q}$ to $\map J {m, n, q + r}$.</ref>. Call this amended version $P'$.
| As $P$ was written so as to start from line 1, we need to move all the <tt>Jump</tt>s so as to point to the same lines relative to the start of $P'$.
|-
| align="right" | $4$ ||
| align="left" | Append $P'$ to $H$.
| This will compute $\map h {n_1, n_2, \ldots, n_k, n} = \map f {n_1, n_2, \ldots, n_k}$.
| $k + s + 2$
|-
| align="right" | $5$ ||
| align="left" | Append the command $\map J {u + k + 1, u + k + 2, k + s + t + 8}$ to $H$.
| If the iterator equals the value of $n$ that was input, this <tt>Jump</tt>s $H$ to a non-existent line to force $H$ to terminate.
| $k + s + 3$
|-
| align="right" | $6$ ||
| align="left" | Append the command $\map C {1, k + 2}$ to $H$.
| This copies the output of $P'$ into the last input location for function $g$, that is, the output from $\map h {n_1, n_2, \ldots, n_k, i - 1}$.
| $k + s + 4$
|-
| align="right" | $7$ ||
| align="left" | Append the command $\map C {u + k + 2, k + 1}$ to $H$.
| This moves the current contents of $R_{u + k + 2}$, the current iteration count, into the last but one input location for function $g$, that is, $i - 1$ itself.
| $k + s + 5$
|-
| align="right" | $8$ ||
| align="left" | Append a Block Copy Program $\map C {u + 1, 1, k}$ to $H$.
| This restores the input that we saved in step $1$ so it will be ready for program $Q$.
| $2 k + s + 5$
|-
| align="right" | $9$ ||
| align="left" | Append the command $\map S {u + k + 2}$ to $H$.
| This increments the iterator $i$.
| $2 k + s + 6$
|-
| align="right" | $10$ ||
| align="left" | Calculate $l = \map \lambda H$.
| This is the length of $H$ so far.
|-
| align="right" | $11$ ||
| align="left" | Increment the <tt>Jump</tt>s in $Q$ by $k + l$ lines. Call this amended version $Q'$.
| As $Q$ was written so as to start from line 1, we need to move all the <tt>Jump</tt>s so as to point to the same lines relative to the start of $Q'$.
|-
| align="right" | $12$ ||
| align="left" | Append $Q'$ to $H$.
| This will compute $\map h {n_1, n_2, \ldots, n_k, n} = \map f {n_1, n_2, \ldots, n_k}$.
| $2 k + s + t + 6$
|-
| align="right" | $13$ ||
| align="left" | Append the command $\map J {1, 1, k + s + 3}$ to $H$.
| This makes the program jump back to the command added at step $6$.
| $2 k + s + t + 7$
|}
The program $H$ finally looks like this:
{|
|-
! align="right" | Line !!
! align="left" | Command !!
! align="left" | Comment
|-
| align="right" | $1$ ||
| align="left" | $\map C {1, u + 1}$ ||
| Start of block copy of input to store.
|-
| align="right" |  ||
| align="left" | $\vdots$ ||
| 
|-
| align="right" | $k + 1$ ||
| align="left" | $\map C {k + 1, u + k + 1}$ ||
| End of block copy of input to store.
|-
| align="right" | $k + 2$ ||
| align="left" | $\map Z {k + 1}$ ||
| Clear the iterator to zero.
|-
| align="right" | $k + 3$ ||
| align="left" | ||
| Start of $P'$.
|-
| align="right" |  ||
| align="left" | $P'$ ||
| 
|-
| align="right" | $k + s + 2$ ||
| align="left" | ||
| End of $P'$.
|-
| align="right" | $k + s + 3$ ||
| align="left" | $\map J {u + k + 1, u + k + 2, k + s + t + 8}$ ||
| If all the iterations have finished, jump to the exit line.
|-
| align="right" | $k + s + 4$ ||
| align="left" | $\map C {1, k + 2}$ ||
| Copy the output of $P'$ into input of $Q'$.
|-
| align="right" | $k + s + 5$ ||
| align="left" | $\map C {u + k + 2, k + 1}$ ||
| Copy the current iteration count input location for function $Q'$.
|-
| align="right" | $k + s +6$ ||
| align="left" | $\map C {u + 1, 1}$ ||
| Start of block copy of stored input back to input of $Q'$.
|-
| align="right" |  ||
| align="left" | $\vdots$ ||
| 
|-
| align="right" | $2 k + s + 5$ ||
| align="left" | $\map C {u + k, k}$ ||
| End of block copy of stored input back to input of $Q'$.
|-
| align="right" | $2 k + s + 6$ ||
| align="left" | $\map S {u + k + 2}$ ||
| Increment the iterator.
|-
| align="right" | $2 k + s + 7$ ||
| align="left" | ||
| Start of $Q'$.
|-
| align="right" |  ||
| align="left" | $Q'$ ||
| 
|-
| align="right" | $2 k + s + t + 6$ ||
| align="left" | ||
| End of $Q'$.
|-
| align="right" | $2 k + s + t + 7$ ||
| align="left" | $\map J {1, 1, k + s + 3}$ ||
| Jump back to start the next iteration through $Q'$.
|-
| align="right" | $2 k + s + t + 8$ ||
| align="left" | Empty ||
| Exit line.
|}
It can easily be determined that $H$ computes $h$.
Hence $h$ is URM computable.
{{qed}}