Composition of One-Variable URM Computable Functions

From ProofWiki
Jump to navigation Jump to search

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$.