5.3 The Scope of Abacus Computability

We now turn from showing that particular functions are abacus computable to showing that certain processes for defining new functions from old, when applied to old abacuscomputable functions, produce new abacus-computable functions. (These processes will be explained and examined in more detail in the next chapter, and readers may wish to defer reading this section until after that chapter.)

Now we initially indicated that to compute a function of r arguments on an abacus, we must specify r registers or boxes in which the arguments are to be stored initially (represented by piles of rocks) and we must specify a register or box in which the value of the function is to appear (represented by a pile of rocks) at the end of the computation. To facilitate comparison with computations by Turing machines in standard form, we then insisted that the input or arguments were to be placed in the first r registers, but left it open in which register n the output or value would appear: it was not necessary to be more specific, because the simulation of the operations of an abacus by a Turing machine could be carried out wherever we let the output appear. For the purposes of this section, we are therefore free now to insist that the output register n, which we have heretofore left unspecified, be specifically register r + 1. We also wish to insist that at the end of the computation the original arguments should be back in registers 1 through r. In the examples considered earlier this last condition was not met, but those examples are easily modified to meet it. We give some further, trivial examples here, where all our specifications are exactly met.

5.7 Example (Zero, successor, identity). First consider the zero function z, the one-place function that takes the value 0 for all arguments. It is computed by the vacuous program: box 2 is empty anyway.

Next consider the successor function s, the one-place function that takes any natural number x to the next larger natural number x + 1. It is computed by modifying the program in Example 5.3, as shown in Figure 5-14.

Figure 5-14. Three basic functions.

Initially and finally, [1] = x; initially [2] = 0; finally, [2] = s(x). Finally consider identity function idmn , the n-place function whose value for n arguments x1, . . . , xn is the mth one among them, xm . It is computed by the program of the same Example 5.3. Initially and finally, [1] = x1, . . . , [n] = xn ; initially, [n + 1] = 0; finally [n + 1] = xm .

Three different processes for defining new functions from old can be used to expand our initial list of examples. A first process is composition, also called substitution. Suppose we have two 3-place functions g1 and g2, and a 2-place function f . The function h obtained from them by composition is the 3-place function given by

h(x1, x2, x3) = f (g1(x1, x2, x3), g2(x1, x2, x3)).

Suppose g1 and g2 and f are abacus computable according to our specifications, and we are given programs for them.

We want to find a program for h, to show it is abacus computable:

↓

h([1], [2], [3]) → 4 .

↓

The thing is perfectly straightforward: It is a matter of shuttling the results of subcomputations around so as to be in the right boxes at the right times.

First, we identify five registers, none of which are used in any of the given programs. Let us call these registers p1, p2, q1, q2, and q3. They will be used for temporary storage. In the single program which we want to construct, the 3 arguments are stored initially in boxes 1, 2, and 3; all other boxes are empty initially; and at the end, we want the n arguments back in boxes 1, 2, 3, and want the value f (g1([1], [2], [3]), g2([1], [2], [3])) in box number 4. To arrange that, all we need are the three given programs, plus the program of Example 5.2 for emptying one box into another.

We simply compute g1([1], [2], [3]) and store the result in box p1 (which figures in none of the given programs, remember); then compute g2([1], [2], [3]) and store the result in box p2; then store the arguments in boxes 1, 2, and 3 in boxes q1, q2, and q3, emptying boxes 1 through 4; then get the results of the computations of g1 and g2 out of boxes p1 and p2 where they have been stored, emptying them into boxes 1 and 2; then compute f ([1], [2]) = f [g1(original arguments), g2(original arguments)], getting the result in box 3; and finally, tidy up, moving the overall result of the computation from box 3 to box 4, emptying box 3 in the process, and refilling boxes 1 through 3 with the original arguments of the overall computation, which were stored in boxes q1, q2, and q3. Now everything is as it should be. The structure of the flow chart is shown in Figure 5-15.

Another process, called (primitive) recursion, is what is involved in defining multiplication as repeated addition, exponentiation as repeated multiplication, and so on. Suppose we have a 1-place functions f and a 3-place function g. The function h obtained from them by (primitive) recursion is the 2-place function h given by

h(x, 0) = f (x)

h(x, y + 1) = g(x, y, h(x, y)).

Figure 5-16. Recursion.

Initially, [1] = x, [2] = y, and [3] = [4] = · · · = 0. We use a register number p that is not used in the f and g programs as a counter. We put y into it at the beginning, and after each stage of the computation we see whether [ p] = 0. If so, the computation is essentially finished; if not, we subtract 1 from [ p] and go through another stage. In the first three steps we calculate f (x) and see whether entry y was 0. If so, the first of the pair of equations for h is operative: h(x, y) = h(x, 0) = f (x), and the computation is finished, with the result in box 3, as required. If not, the second of the pair of equations for h is operative, and we successively compute h(x, 1), h(x, 2), . . . (see the cyle in Figure 5-16) until the counter (box p) is empty. At that point the computation is finished, with h(x, y) in box 3, as required.

A final process is minimization. Suppose we have a 2-place function f ; then we can define a 1-place function h as follows. If f (x, 0), . . . , f (x, i − 1) are all defined and = 0, and f (x, i) = 0, then h(x) = i. If there is no i with these properties, either

then h(x) is undefined. The function h is called the function obtained from f by minimization. If f is abacus computable, so is h, with a flow chart as in Figure 5-17.

Initially, box 2 is empty, so that if f (x, 1) = 0, the program will halt with the correct answer, h(x) = 0, in box 2. (Box 3 will be empty.) Otherwise, box 3 will be