General Recursive Functions

Publisher Summary

This chapter focuses on primitive recursiveness and search, which give the class of general recursive partial functions. It develops tools for showing that certain functions are in this class. These tools are used to study computability by register-machine programs. The search operator provides a useful way of defining a function in terms of a “search” for the first time a given condition is satisfied. Earlier the collection of primitive recursive functions cannot contain all of the effectively calculable total functions. This chapter presents theorem to show that the constructions preserve primitive recursiveness. That is, when applied to primitive recursive relations, they produce primitive recursive relations. This theorem is useful in extending the supply of primitive recursive relations and functions. The class of general recursive partial functions is obtained that allows functions to be built up by use of search.

In the preceding chapter, we saw an overview of several possible formalizations of the concept of effective calculability. In this chapter, we focus on one of those: primitive recursiveness and search, which give us the class of general recursive partial functions. In particular, we develop tools for showing that certain functions are in this class. These tools will be used in Chapter 3, where we study computability by registermachine programs.

2.1 Primitive Recursive Functions

The primitive recursive functions have been defined in the preceding chapter as the functions on that can be built up from zero functions

(x1,…,xk)=0,

the successor function

(x)=x+1,

and the projection functions

nk(x1,…,xk)=xn

by using (zero or more times) composition

(x→)=f(g1(x→),…,gn(x→))

and primitive recursion

(x→,0)=f(x→)h(x→,y+1)=g(h(x→,y),x→,y),

where → can be empty:

(0)=mh(y+1)=g(h(y),y).

It should be pretty clear that given any number m and any two-place function g, there exists a unique function h obtained by primitive recursion from g by using m. It is the function h that we calculate as in the preceding example. Similarly, given a k-place function f and a k+2)-place function g, there exists a unique k+1)-place function h that is obtained by primitive recursion from f and g. That is, h is the function given by the pair of equations

(x→,0)=f(x→)h(x→,y+1)=g(h(x→,y),x→,y).

Moreover, if f and g are total functions, then h will also be total.

More generally, for any primitive recursive function h, we can use a labeled tree (“construction tree”) to illustrate exactly how h is built up, as in the example of addition. At the top (root) vertex, we put h. At each minimal vertex (a leaf), we have an initial function: the successor function, a zero function, or a projection function. At each other vertex, we display either an application of composition or an application of primitive recursion.

An application of composition

(x→)=f(g1(x→),…,gn(x→))

can be illustrated in the tree by a vertex with n+1)-ary branching:

Here f must be an n-place function, and 1,…,gn must all have the same number of places as h.

An application of primitive recursion to obtain a k+1)-place function h

h(x→,0)=f(x→)h(x→,y+1)=g(h(x→,y),x→,y)

can be illustrated by a vertex with binary branching:

Note that g must have two more places than f, and one more place than h (e.g., if h is a two-place function, then g must be a three-place function and f must be a one-place function).

The =0 case, where a one-place function h is obtained by primitive recursion from a two-place function g by using the number m

h(0)=mh(x+1)=g(h(x),x),

can be illustrated by a vertex with unary branching:

In both forms of primitive recursion (>0 and =0), the key feature is that the value of the function at a number +1 is somehow obtainable from its value at t. The role of g is to explain how.

Every primitive recursive function is total. We can see this by “structural induction.” For the basis, all of the initial functions (the zero functions, the successor function, and the projections functions) are total. For the two inductive steps, we observe that composition of total functions yields a total function, and primitive recursion applied to total functions yields a total function. So for any primitive recursive function, we can work our way up its construction tree. At the leaves of the tree, we have total functions. And each time we move to a higher vertex, we still have a total function. Eventually, we come to the root at the top, and conclude that the function being constructed is total.

Next we want to build up a catalog of basic primitive recursive functions. These items in the catalog can then be used as “off the shelf” parts for later building up of other primitive recursive functions.