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=I1,,Im and N=I1,,In, define M,N to be the URM


where Im+i=Ii, where i{1,,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 Ik=J(i,j,q) is in N, then change Ik 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 Ik=J(i,j,p) is in M, and p>m, then change Ik 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. It is easy to see that every M can be modified to M.

When M computes a function f:n and N computes a function g:, we would further want the combined machine to compute gf. 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:n. Define k=max(n,ρ(M)). Then M* is defined as the URM M,Z[k], where M is defined in 2. above, and Z[k] is the machine with instructions Z(2),Z(3),,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 MN to be the machine M*,N(|M|). It is easy to see that is an associative operationMathworldPlanetmath. We can summarize our discussion above into the following:

Proposition 1.

Let M,N be URMs that compute f:NnN and g:NN respectively, then MN computes gf. In other words, if f and g are URM computable, so is gf.

For example, if M computes f(r,s):=r+s for any r,s, and N computes g(r):=r-˙1 for any r, then MN computes (gf)(r,s)=(r+s)-˙1. In addition, with input r, the URM


computes gs(r):=r-˙s. Note that gs is unary, and therefore not the same as the binary operationMathworldPlanetmath h(r,s):=r-˙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=I1,,Im, 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 ρ*(N):=max(ρ(N),n(N)), where ρ(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 N1,,Nk are to be inserted as subroutines in a program M, define


    Allocate the first n registers for computations by the subroutines Ni.

  3. 6.

    Allocate the next n* registers for storage, where n*=n1++nk.

  4. 7.

    For any URM N, and any positive integers R1,,Rs,Rt, define the following URM:


    where k=ρ*(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 Ni to be inserted, insert N[R1,,Rs;Rt] instead, where each Rj 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 N1,,Nk be URMs that compute m-ary functions f1,,fk, and let M be a URM that computes a k-ary function g. Define an m-ary function h:m as the compositionMathworldPlanetmath of the f’s and g:


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:

  2. 2.

    Insert programs


    This has the effect of computing f1(r1,,rm),,fk(r1,,rm), and putting the results in registers n+m+1,n+m+2,,n+m+k.

  3. 3.

    Insert the program


    so the results are copied to the first k registers, and g(f1(r1,,rm),,fk(r1,,rm)) is computed.

  4. 4.

    Then P:=P1,P2,P3 computes h.

Note that rdom(h) iff N1(r),,Nk(r) and M(f1(r1,,rm),,fk(r1,,rm)).

What we have shown above is summarized as follows:

Proposition 2.

If m-ary functions f1,,fk and a k-ary function g are URM-computable, then so is g(f1,,fk).

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

Corollary 1.

If f(x1,,xn) is URM-computable, so is f(xσ(1),,xσ(n)), where σ is a permutationMathworldPlanetmath on {1,,n}.


For each i{1,,n}, the function gi(x1,,xn)=xσ(i) is computed by T(σ(i),1), and f(xσ(1),,xσ(n))=f(g1,,gn). ∎


Title combining URMs
Canonical name CombiningURMs
Date of creation 2013-03-22 19:04:07
Last modified on 2013-03-22 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