Function Obtained by Minimization from URM Computable Functions

Theorem

Let the function $f: \N^{k+1} \to \N$ be a URM computable function.

Let $g: \N^k \to \N$ be the function obtained by minimization from $f$ thus:

$g \left({n_1, n_2, \ldots, n_k}\right) \approx \mu y \left({f \left({n_1, n_2, \ldots, n_k}\right) = 0}\right)$.

Then $g$ is also URM computable.

Proof

Let $f: \N^{k+1} \to \N$ be a URM computable function.

Let $P$ be a URM program which computes $f$.

Let $u = \rho \left({P}\right)$ be the number of registers used by $P$.

We can use:

• the registers $R_{u+1}, R_{u+2}, \ldots, R_{u+k}$ to store the input $\left({n_1, n_2, \ldots, n_k}\right)$;
• the register $R_{u+k+1}$ to store the current value of the recursion variable $y$.

We check whether or not $f \left({n_1, n_2, \ldots, n_k}\right) = 0$ by comparing the output from running $P$ (appearing in register $1$ at the end of the running of $P$) with the number in register $R_{u+k+2}$, which remains at $0$ throughout.

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}\right)$, which is held in $R_1, R_2, \ldots, R_k$.

We are to use the following registers:

• $R_{u+1}, R_{u+2}, \ldots, R_{u+k}$ will be used to store the input $\left({n_1, n_2, \ldots, n_k}\right)$ so it does not get overwritten.
• $R_{u+k+1}$ will hold the value of $y$.
• $R_{u+k+2}$ will hold the $0$ throughout.

When $r_{u+k+2} = r_{u+k+1}$, the computation will have ended.

We also define $v = \lambda \left({H}\right)$ to be the number of basic instructions in $H$.

Step		Process	Notes	$\lambda \left({H}\right)$
$1$		Append a Block Copy Program $C \left({1, u, k}\right)$ to $H$.	This stores the input somewhere safe so it can be accessed again later.	$k$
$2$		Increment the Jumps in $P$ by $k$ lines. 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'$.
$3$		Append $P'$ to $H$.	This will compute $f \left({n_1, n_2, \ldots, n_k, y}\right)$.	$k + s$
$4$		Append the command $J \left({1, u+k+2, v}\right)$ to $H$.	This Jumps $H$ to the end of the program if the output of $P$ is zero.	$k + s + 1$
$5$		Append the command $S \left({u + k + 1}\right)$ to $H$.	Increment $y$.	$k + s + 2$
$6$		Append a Block Copy Program $C \left({u+k+1, 1, k+1}\right)$ to $H$.	Recall the input values, and put $y$ in $R_{k+1}$.	$2 k + s + 3$
$8$		Append the command $J \left({1, 1, k + 1}\right)$ to $H$.	This makes the program jump back to the start of $P'$.	$2 k + s + 4$
$7$		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)$.	$2 k + s + 5$
$8$		Append the command $C \left({u+k+1, 1}\right)$ to $H$.	Put $y$ into the output register.	$v = 2 k + s + 6$

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

Hence $g$ is URM computable.

$\blacksquare$