## You are here

Homecombining URMs

## Primary tabs

# 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. 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=\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:

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

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

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

- 9.

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

- 1 N. Cutland, Computability: An Introduction to Recursive Function Theory. Cambridge University Press, (1980).

## Mathematics Subject Classification

68Q05*no label found*03D10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections