combining URMs
Combining URMs
The basic idea of combining existing URMs is to produce URMs that can perform more complicated computations. Suppose we are given two URMs $M={I}_{1},\mathrm{\dots},{I}_{m}$ and $N={I}_{1}^{\prime},\mathrm{\dots},{I}_{n}^{\prime}$, define $M,N$ to be the URM
$$M,N:={I}_{1},{I}_{2},\mathrm{\dots},{I}_{m+n}$$ 
where ${I}_{m+i}={I}_{i}^{\prime}$, where $i\in \{1,\mathrm{\dots},n\}$. In other words, the instructions of $N$ are reindexed and appended to the last instruction of $M$.
In theory, we would like $M,N$ to first go through the instructions of $M$, and if the computations of $M$ terminate, go through the computations of $N$. In order to achieve this goal, modifications to $M$ and $N$ need to be made so computations of $M$ are kept apart from the computations of $N$:

1.
If ${I}_{k}=J(i,j,q)$ is in $N$, then change ${I}_{k}$ to $J(i,j,q+m)$. This is clearly necessary as the indices of the instructions of $N$ have been shifted by $m$. Let the modified $N$ be denoted by $N(m)$.

2.
If ${I}_{k}=J(i,j,p)$ is in $M$, and $p>m$, then change ${I}_{k}$ to $J(i,j,m+1)$. The purpose of this change is to ensure that computations of $M$ do not accidentally jump to an instruction of $N$. Furthermore, when $M$ halts, $N$ starts. Call this modified machine ${M}^{\prime}$. It is easy to see that every $M$ can be modified to ${M}^{\prime}$.
When $M$ computes a function $f:{\mathbb{N}}^{n}\to \mathbb{N}$ and $N$ computes a function $g:\mathbb{N}\to \mathbb{N}$, we would further want the combined machine to compute $g\circ f$. In essence, if $r$ is an input, and if $f(r)$ is computed by $M$, we want $f(r)$ to be the input of the machine $N$, so that $g(f(r))$ may be computed. To get the desired result, one more modification should be made:

3.
Suppose $M$ computes $f:{\mathbb{N}}^{n}\to \mathbb{N}$. Define $k=\mathrm{max}(n,\rho (M))$. Then ${M}^{*}$ is defined as the URM ${M}^{\prime},Z[k]$, where ${M}^{\prime}$ is defined in 2. above, and $Z[k]$ is the machine with instructions $Z(2),Z(3),\mathrm{\cdots},Z(k)$.
In other words, whenever $f(r)$ is computed by $M$, ${M}^{*}$ resets the contents of all registers potentially used by $M$ to $0$, except the first one, which contains the result $f(r)$. As a result, the input for $N$ has $0$ in all but possibly the first register.
With the three modifications above, let us define $M\circ N$ to be the machine ${M}^{*},N(M)$. It is easy to see that $\circ $ is an associative operation^{}. We can summarize our discussion above into the following:
Proposition 1.
Let $M\mathrm{,}N$ be URMs that compute $f\mathrm{:}{\mathrm{N}}^{n}\mathrm{\to}\mathrm{N}$ and $g\mathrm{:}\mathrm{N}\mathrm{\to}\mathrm{N}$ respectively, then $M\mathrm{\circ}N$ computes $g\mathrm{\circ}f$. In other words, if $f$ and $g$ are URM computable, so is $g\mathrm{\circ}f$.
For example, if $M$ computes $f(r,s):=r+s$ for any $r,s\in \mathbb{N}$, and $N$ computes $g(r):=r\dot{}1$ for any $r\in \mathbb{N}$, then $M\circ N$ computes $(g\circ f)(r,s)=(r+s)\dot{}1$. In addition, with input $r$, the URM
$$\underset{s}{\underset{\u23df}{N\circ N\circ \mathrm{\cdots}\circ N}}$$ 
computes ${g}^{s}(r):=r\dot{}s$. Note that ${g}^{s}$ is unary, and therefore not the same as the binary operation^{} $h(r,s):=r\dot{}s$. To construct a URM computing $h$ using the URM $N$, the method described above does not work, and a more general construction is needed.
URM as a Subroutine
Another way of generating URMs from existing ones is by inserting the existing URMs, so called subroutines, as part of a larger URM. Given a URM $M={I}_{1},\mathrm{\dots},{I}_{m}$, a subroutine of $M$ is defined as a block of consecutive instructions in $M$. Based on this definition, we see that combining machines can be seen as a special case: the URMs $M$ and $N$ are subroutines of the URM $M,N$. In fact, each instruction in a URM can be considered as a subroutine.
As in the case with combining two URMs, when inserting a URM as a subroutine in a larger URM, one would like to keep the computations done within the subroutine isolated from the remaining computations. Since only one tape is allowed, one can allocate a portion of the tape reserved only for subroutine computations, another portion for storage, while the rest for computations by the main program. This can be done as follows:

4.
For any URM $N$, define ${\rho}^{*}(N):=\mathrm{max}(\rho (N),n(N))$, where $\rho (N)$ is the number of registers used for computations by $N$, and $n(N)$ is the arity of the function computed by $N$.

5.
Suppose ${N}_{1},\mathrm{\dots},{N}_{k}$ are to be inserted as subroutines in a program $M$, define
$$n:=\mathrm{max}\{{\rho}^{*}({N}_{i})\mid i=1,\mathrm{\dots},k\}.$$ Allocate the first $n$ registers for computations by the subroutines ${N}_{i}$.

6.
Allocate the next ${n}^{*}$ registers for storage, where ${n}^{*}={n}_{1}+\mathrm{\cdots}+{n}_{k}$.

7.
For any URM $N$, and any positive integers ${R}_{1},\mathrm{\dots},{R}_{s},{R}_{t}$, define the following URM:
$$N[{R}_{1},\mathrm{\dots},{R}_{s};{R}_{t}]:=T({R}_{1},1),T({R}_{2},2),\mathrm{\dots},T({R}_{s},s),N,T(1,{R}_{t}),Z(1),\mathrm{\dots},Z(k),$$ where $k={\rho}^{*}(N)$.

8.
Computations of by the remaining instructions of $M$ will take place in registers $n+{n}^{*}+1$ or beyond.

9.
For each ${N}_{i}$ to be inserted, insert $N[{R}_{1},\mathrm{\dots},{R}_{s};{R}_{t}]$ instead, where each ${R}_{j}$ is determined by the computations done by instructions just prior to the point of insertion.
The above only serves as a guideline, not a definite rule to follow. The following example serves as an illustration: let ${N}_{1},\mathrm{\dots},{N}_{k}$ be URMs that compute $m$ary functions ${f}_{1},\mathrm{\dots},{f}_{k}$, and let $M$ be a URM that computes a $k$ary function $g$. Define an $m$ary function $h:{\mathbb{N}}^{m}\to \mathbb{N}$ as the composition^{} of the $f$’s and $g$:
$$h({r}_{1},\mathrm{\dots},{r}_{m}):=g({f}_{1}({r}_{1},\mathrm{\dots},{r}_{m}),\mathrm{\dots},{f}_{k}({r}_{1},\mathrm{\dots},{r}_{m})),$$ 
provided, of course, that the right hand side is defined. We show that $h$ is URMcomputable by finding a suitable URM $P$ that computes $h$:

1.
Given input $r$ occupying the first $n$ registers, first copy contents of the input to the storage area by the following instructions:
$${P}_{1}:=T(1,n+1),T(2,n+2),\mathrm{\dots},T(m,n+m)$$ 
2.
Insert programs
$${P}_{2}:={N}_{1}[n+1,\mathrm{\dots},n+m;n+m+1],\mathrm{\dots},{N}_{k}[n+1,\mathrm{\dots},n+m;n+m+k]$$ This has the effect of computing ${f}_{1}({r}_{1},\mathrm{\dots},{r}_{m}),\mathrm{\dots},{f}_{k}({r}_{1},\mathrm{\dots},{r}_{m})$, and putting the results in registers $n+m+1,n+m+2,\mathrm{\dots},n+m+k$.

3.
Insert the program
$${P}_{3}:=M[n+m+1,\mathrm{\dots},n+m+k;1]$$ so the results are copied to the first $k$ registers, and $g({f}_{1}({r}_{1},\mathrm{\dots},{r}_{m}),\mathrm{\dots},{f}_{k}({r}_{1},\mathrm{\dots},{r}_{m}))$ is computed.

4.
Then $P:={P}_{1},{P}_{2},{P}_{3}$ computes $h$.
Note that $r\in \mathrm{dom}(h)$ iff ${N}_{1}(r)\downarrow ,\mathrm{\dots},{N}_{k}(r)\downarrow $ and $M({f}_{1}({r}_{1},\mathrm{\dots},{r}_{m}),\mathrm{\dots},{f}_{k}({r}_{1},\mathrm{\dots},{r}_{m}))\downarrow $.
What we have shown above is summarized as follows:
Proposition 2.
If $m$ary functions ${f}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{f}_{k}$ and a $k$ary function $g$ are URMcomputable, then so is $g\mathit{}\mathrm{(}{f}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{f}_{k}\mathrm{)}$.
As a corollary, the following function is URMcomputable:
Corollary 1.
If $f\mathit{}\mathrm{(}{x}_{\mathrm{1}}\mathrm{,}\mathrm{\dots}\mathrm{,}{x}_{n}\mathrm{)}$ is URMcomputable, so is $f\mathit{}\mathrm{(}{x}_{\sigma \mathit{}\mathrm{(}\mathrm{1}\mathrm{)}}\mathrm{,}\mathrm{\dots}\mathrm{,}{x}_{\sigma \mathit{}\mathrm{(}n\mathrm{)}}\mathrm{)}$, where $\sigma $ is a permutation^{} on $\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{\dots}\mathrm{,}n\mathrm{\}}$.
Proof.
For each $i\in \{1,\mathrm{\dots},n\}$, the function ${g}_{i}({x}_{1},\mathrm{\dots},{x}_{n})={x}_{\sigma (i)}$ is computed by $T(\sigma (i),1)$, and $f({x}_{\sigma (1)},\mathrm{\dots},{x}_{\sigma (n)})=f({g}_{1},\mathrm{\dots},{g}_{n})$. ∎
References
 1 N. Cutland, Computability: An Introduction to Recursive Function^{} Theory. Cambridge University Press, (1980).
Title  combining URMs 

Canonical name  CombiningURMs 
Date of creation  20130322 19:04:07 
Last modified on  20130322 19:04:07 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  16 
Author  CWoo (3771) 
Entry type  Application 
Classification  msc 68Q05 
Classification  msc 03D10 