The basic idea of combining existing URMs is to produce URMs that can perform more complicated computations. Suppose we are given two URMs and , define to be the URM
where , where . In other words, the instructions of are re-indexed and appended to the last instruction of .
In theory, we would like to first go through the instructions of , and if the computations of terminate, go through the computations of . In order to achieve this goal, modifications to and need to be made so computations of are kept apart from the computations of :
If is in , then change to . This is clearly necessary as the indices of the instructions of have been shifted by . Let the modified be denoted by .
If is in , and , then change to . The purpose of this change is to ensure that computations of do not accidentally jump to an instruction of . Furthermore, when halts, starts. Call this modified machine . It is easy to see that every can be modified to .
When computes a function and computes a function , we would further want the combined machine to compute . In essence, if is an input, and if is computed by , we want to be the input of the machine , so that may be computed. To get the desired result, one more modification should be made:
Suppose computes . Define . Then is defined as the URM , where is defined in 2. above, and is the machine with instructions .
In other words, whenever is computed by , resets the contents of all registers potentially used by to , except the first one, which contains the result . As a result, the input for has in all but possibly the first register.
Let be URMs that compute and respectively, then computes . In other words, if and are URM computable, so is .
For example, if computes for any , and computes for any , then computes . In addition, with input , the URM
computes . Note that is unary, and therefore not the same as the binary operation . To construct a URM computing using the URM , 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 , a subroutine of is defined as a block of consecutive instructions in . Based on this definition, we see that combining machines can be seen as a special case: the URMs and are subroutines of the URM . 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:
For any URM , define , where is the number of registers used for computations by , and is the arity of the function computed by .
Suppose are to be inserted as subroutines in a program , define
Allocate the first registers for computations by the subroutines .
Allocate the next registers for storage, where .
For any URM , and any positive integers , define the following URM:
Computations of by the remaining instructions of will take place in registers or beyond.
For each to be inserted, insert instead, where each 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 be URMs that compute -ary functions , and let be a URM that computes a -ary function . Define an -ary function as the composition of the ’s and :
provided, of course, that the right hand side is defined. We show that is URM-computable by finding a suitable URM that computes :
Given input occupying the first registers, first copy contents of the input to the storage area by the following instructions:
This has the effect of computing , and putting the results in registers .
Insert the program
so the results are copied to the first registers, and is computed.
Then computes .
Note that iff and .
What we have shown above is summarized as follows:
If -ary functions and a -ary function are URM-computable, then so is .
As a corollary, the following function is URM-computable:
If is URM-computable, so is , where is a permutation on .
For each , the function is computed by , and . ∎