Composition of One-Variable URM Computable Functions

Theorem

Let $f: \N \to \N$ and $g: \N \to \N$ be URM computable functions of one variable.

Let $f \circ g$ be the composition of $f$ and $g$.

Then $f \circ g: \N \to \N$ is a URM computable function.

Proof

Let $f: \N \to \N$ and $g: \N \to \N$ be URM computable functions of one variable.

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

Let $Q$ be a URM program which computes $g$.

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

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

In order to compute $f \circ g$ the program must compute $g$ first (by running $Q$), then use the output of $Q$ as the input of $P$, which must then compute $f$.

After $Q$ has computed the value of $g \left({n}\right)$, its output is to be found in $R_1$.

Its instruction pointer is greater than $s$, and may at this point be indeterminate.

Also, the contents of $R_2, R_3, \ldots, R_u$ are also indeterminate.

So we need to do the following things:

1. The instruction pointer needs to be set to the line immediately after the end of $Q$, that is, to line $s+1$.
2. The registers used by $Q$, except $R_1$, the one holding the output of $Q$, must be set to $0$. So a Clear Registers Program $Z \left({2, u}\right)$ must be appended to the end of $Q$.
3. The program $P$ must be appended to the end of $Q$ with $Z \left({2, u}\right)$ appended. However, $P$ no longer starts at line $1$ but at line $\left({q + u - 1}\right)$, so any Jump instructions of the form $J \left({m, n, q}\right)$ in $P$ must have $q$ changed to $\left({q + u - 1}\right)$.

When that has been achieved, the following happens:

1. The program runs $Q$, amended if necessary so that the instruction pointer ends up at $s+1$.
2. The contents of $R_2$ to $R_u$ are then set to zero.
3. $P$ is now run, with the output of $Q$ in its input $R_1$, and all the other registers set to zero.

The output of $P$ can now be found in $R_1$.

The resulting program $Q$ followed by $Z \left({2, u}\right)$ followed by $P$ is called:

• the concatenation of $Q$ and $P$, or, in general:
• a concatenated program,

and is denoted $Q * P$.

Note that this is read:

• Run $Q$ first;
• Then run $P$.

So it is read from left to right.

In that sense the notation is different from that of $f \circ g$ for the composition of $f$ and $g$, which is read from right to left.

So $f \circ g$ is computed by $Q * P$.

$\blacksquare$

Its length $\lambda \left({Q * P}\right)$ is given as:

$\left({Q * P}\right) = \lambda \left({Q}\right) + \left({u-1}\right) \lambda \left({P}\right)$.

The $u-1$ comes from the length of the Clear Registers Program.

Thus we have an algorithm for concatenating two URM programs, as follows:

Alternative Proof

It can be noted that this is an instance of a Function Obtained by Substitution from URM Computable Functions‎ where $t = k = 1$.

$\blacksquare$

Concatenation of two URM Programs

Let $P$ and $Q$ be one-variable URM programs.

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

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

Then the concatenation of $Q$ and $P$ is written $Q * P$, and is the program obtained as follows:

• Replace every Jump instruction of $P$ of the form $J \left({m, n, q}\right)$ by $J \left({m, n, q + s + u - 1}\right)$.

• Replace every Jump instruction of $Q$ of the form $J \left({m, n, q}\right)$, where $q > s$, by $J \left({m, n, s + 1}\right)$.

• If $u > 1$, then add the instructions for the Clear Registers Program $Z \left({2, u}\right)$ to the end of $Q$ from line $s+1$ onwards.

• Add the amended (as above) instructions for $P$ to the end of the above, renumbering each line $l$ to be $l + s + u - 1$.

The resulting program $Q * P$ is technically $Q * Z \left({2, u}\right) * P$.