Function Obtained by Primitive Recursion from URM Computable Functions

From ProofWiki
Jump to navigation Jump to search

Theorem

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: h \left({n_1, n_2, \ldots, n_k, n}\right) = \begin{cases} f \left({n_1, n_2, \ldots, n_k}\right) & : n = 0 \\ g \left({n_1, n_2, \ldots, n_k, n-1, h \left({n_1, n_2, \ldots, n_k, n-1}\right)}\right) & : n > 0 \end{cases}$


Let $P$ and $Q$ be normalized URM programs which compute $f$ and $g$ respectively.

Let $s = \lambda \left({P}\right)$ and $t = \lambda \left({Q}\right)$ be the number of basic instructions in $P$ and $Q$.


Let $u = \max \left\{{\rho \left({P}\right), \rho \left({Q}\right), k+2}\right\}$.

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 $\left({n_1, n_2, \ldots, n_k, n}\right)$, which is held in $R_1, R_2, \ldots, R_k, R_{k+1}$.

The plan is that the program will compute $h \left({n_1, n_2, \ldots, n_k, i}\right)$ for $i = 0, 1, 2, \ldots, n$ in order.

At the end of the last iteration, $h \left({n_1, n_2, \ldots, n_k, n}\right)$ 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 $\left({n_1, n_2, \ldots, n_k, n}\right)$ 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.


Step Process Notes $\lambda \left({H}\right)$
$1$ Append a Block Copy Program $C \left({1, u+1, k+1}\right)$ to $H$[1]. This stores the input somewhere safe so it can be accessed again later. $k + 1$
$2$ Append $Z \left({k+1}\right)$ 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$
$3$ Increment the Jumps in $P$ by $k+2$ lines[2]. Call this amended version $P'$. As $P$ was written so as to start from line 1, we need to move all the Jumps so as to point to the same lines relative to the start of $P'$.
$4$ Append $P'$ to $H$. This will compute $h \left({n_1, n_2, \ldots, n_k, n}\right) = f \left({n_1, n_2, \ldots, n_k}\right)$. $k + s + 2$
$5$ Append the command $J \left({u+k+1, u+k+2, k+s+t+8}\right)$ to $H$. If the iterator equals the value of $n$ that was input, this Jumps $H$ to a non-existent line to force $H$ to terminate. $k + s + 3$
$6$ Append the command $C \left({1, k+2}\right)$ to $H$. This copies the output of $P'$ into the last input location for function $g$, that is, the output from $h \left({n_1, n_2, \ldots, n_k, i-1}\right)$. $k + s + 4$
$7$ Append the command $C \left({u+k+2, k+1}\right)$ 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$
$8$ Append a Block Copy Program $C \left({u+1, 1, k}\right)$ to $H$. This restores the input that we saved in step $1$ so it will be ready for program $Q$. $2 k + s + 5$
$9$ Append the command $S \left({u+k+2}\right)$ to $H$. This increments the iterator $i$. $2 k + s + 6$
$10$ Calculate $l = \lambda \left({H}\right)$. This is the length of $H$ so far.
$11$ Increment the Jumps 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 Jumps so as to point to the same lines relative to the start of $Q'$.
$12$ Append $Q'$ to $H$. This will compute $h \left({n_1, n_2, \ldots, n_k, n}\right) = f \left({n_1, n_2, \ldots, n_k}\right)$. $2 k + s + t + 6$
$13$ Append the command $J \left({1, 1, k + s + 3}\right)$ 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:

Line Command Comment
$1$ $C \left({1, u+1}\right)$ Start of block copy of input to store.
$\vdots$
$k+1$ $C \left({k+1, u+k+1}\right)$ End of block copy of input to store.
$k+2$ $Z \left({k+1}\right)$ Clear the iterator to zero.
$k+3$ Start of $P'$.
$P'$
$k+s+2$ End of $P'$.
$k+s+3$ $J \left({u+k+1, u+k+2, k+s+t+8}\right)$ If all the iterations have finished, jump to the exit line.
$k+s+4$ $C \left({1, k+2}\right)$ Copy the output of $P'$ into input of $Q'$.
$k+s+5$ $C \left({u+k+2, k+1}\right)$ Copy the current iteration count input location for function $Q'$.
$k+s+6$ $C \left({u+1, 1}\right)$ Start of block copy of stored input back to input of $Q'$.
$\vdots$
$2k+s+5$ $C \left({u+k, k}\right)$ End of block copy of stored input back to input of $Q'$.
$2k+s+6$ $S \left({u+k+2}\right)$ Increment the iterator.
$2k+s+7$ Start of $Q'$.
$Q'$
$2k+s+t+6$ End of $Q'$.
$2k+s+t+7$ $J \left({1, 1, k + s + 3}\right)$ Jump back to start the next iteration through $Q'$.
$2k+s+t+8$ Empty Exit line.


It can easily be determined that $H$ computes $h$.

Hence $h$ is URM computable.

$\blacksquare$


Comment

Note that there are two things going on here. The first table is an algorithm for creating the program, the second table is the program itself.


Footnotes

  1. $H$, at this point, is a null URM program.
  2. To increment the Jumps by $r$ for any normalized URM program is done by changing all Jumps of the form $J \left({m, n, q}\right)$ to $J \left({m, n, q+r}\right)$.