# 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},\ldots,I_{m}$ and $N=I_{1}^{\prime},\ldots,I_{n}^{\prime}$, define $M,N$ to be the URM

 $M,N:=I_{1},I_{2},\ldots,I_{m+n}$

where $I_{m+i}=I_{i}^{\prime}$, where $i\in\{1,\ldots,n\}$. In other words, the instructions of $N$ are re-indexed 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. 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. 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:

1. 3.

Suppose $M$ computes $f:\mathbb{N}^{n}\to\mathbb{N}$. Define $k=\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),\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,N$ be URMs that compute $f:\mathbb{N}^{n}\to\mathbb{N}$ and $g:\mathbb{N}\to\mathbb{N}$ respectively, then $M\circ N$ computes $g\circ f$. In other words, if $f$ and $g$ are URM computable, so is $g\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

 $\underbrace{N\circ N\circ\cdots\circ N}_{s}$

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},\ldots,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:

1. 4.

For any URM $N$, define $\rho^{*}(N):=\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$.

2. 5.

Suppose $N_{1},\ldots,N_{k}$ are to be inserted as subroutines in a program $M$, define

 $n:=\max\{\rho^{*}(N_{i})\mid i=1,\ldots,k\}.$

Allocate the first $n$ registers for computations by the subroutines $N_{i}$.

3. 6.

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

4. 7.

For any URM $N$, and any positive integers $R_{1},\ldots,R_{s},R_{t}$, define the following URM:

 $N[R_{1},\ldots,R_{s};R_{t}]:=T(R_{1},1),T(R_{2},2),\ldots,T(R_{s},s),N,T(1,R_{% t}),Z(1),\ldots,Z(k),$

where $k=\rho^{*}(N)$.

5. 8.

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

6. 9.

For each $N_{i}$ to be inserted, insert $N[R_{1},\ldots,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},\ldots,N_{k}$ be URMs that compute $m$-ary functions $f_{1},\ldots,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},\ldots,r_{m}):=g(f_{1}(r_{1},\ldots,r_{m}),\ldots,f_{k}(r_{1},\ldots,r% _{m})),$

provided, of course, that the right hand side is defined. We show that $h$ is URM-computable by finding a suitable URM $P$ that computes $h$:

1. 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),\ldots,T(m,n+m)$
2. 2.

Insert programs

 $P_{2}:=N_{1}[n+1,\ldots,n+m;n+m+1],\ldots,N_{k}[n+1,\ldots,n+m;n+m+k]$

This has the effect of computing $f_{1}(r_{1},\ldots,r_{m}),\ldots,f_{k}(r_{1},\ldots,r_{m})$, and putting the results in registers $n+m+1,n+m+2,\ldots,n+m+k$.

3. 3.

Insert the program

 $P_{3}:=M[n+m+1,\ldots,n+m+k;1]$

so the results are copied to the first $k$ registers, and $g(f_{1}(r_{1},\ldots,r_{m}),\ldots,f_{k}(r_{1},\ldots,r_{m}))$ is computed.

4. 4.

Then $P:=P_{1},P_{2},P_{3}$ computes $h$.

Note that $r\in\operatorname{dom}(h)$ iff $N_{1}(r)\downarrow,\ldots,N_{k}(r)\downarrow$ and $M(f_{1}(r_{1},\ldots,r_{m}),\ldots,f_{k}(r_{1},\ldots,r_{m}))\downarrow$.

What we have shown above is summarized as follows:

###### Proposition 2.

If $m$-ary functions $f_{1},\ldots,f_{k}$ and a $k$-ary function $g$ are URM-computable, then so is $g(f_{1},\ldots,f_{k})$.

As a corollary, the following function is URM-computable:

###### Corollary 1.

If $f(x_{1},\ldots,x_{n})$ is URM-computable, so is $f(x_{\sigma(1)},\ldots,x_{\sigma(n)})$, where $\sigma$ is a permutation on $\{1,\ldots,n\}$.

###### Proof.

For each $i\in\{1,\ldots,n\}$, the function $g_{i}(x_{1},\ldots,x_{n})=x_{\sigma(i)}$ is computed by $T(\sigma(i),1)$, and $f(x_{\sigma(1)},\ldots,x_{\sigma(n)})=f(g_{1},\ldots,g_{n})$. ∎

## References

Title combining URMs CombiningURMs 2013-03-22 19:04:07 2013-03-22 19:04:07 CWoo (3771) CWoo (3771) 16 CWoo (3771) Application msc 68Q05 msc 03D10