next up previous
Next: Recursive Functions of the Up: Formalisms For Describing Computable Previous: Formalisms For Describing Computable

Functions Computable in Terms of Given Base Functions


Suppose we are given a base collection tex2html_wrap_inline2578 of functions (including predicates) having certain domains and ranges. In the case of the non-negative integers, we may have the successor function and the predicate of equality, and in the case of the S-expressions discussed in reference 7, we have the five basic operations. Our object is to define a class of functions tex2html_wrap_inline2580 { tex2html_wrap_inline2578 } which we shall call the class of functions computable in terms of tex2html_wrap_inline2578 .

Before developing tex2html_wrap_inline2580 { tex2html_wrap_inline2578 } formally, we wish to give an example, and in order to give the example, we first need the concept of conditional expression. In our notation a conditional expression has the form


which corresponds to the ALGOL 60 reference language (12) expression


Here tex2html_wrap_inline2610 are propositional expressions taking the values T or F standing for truth and falsity respectively.

The value of tex2html_wrap_inline2612 is the value of the e corresponding to the first p that has value T. Thus

(4 < 3 tex2html_wrap_inline2620 7, 2 > 3 tex2html_wrap_inline2620 8, 2 < 3 tex2html_wrap_inline2620 9, 4 < 5 tex2html_wrap_inline2620 7) = 9.

Some examples of the conditional expressions for well known functions are


and the triangular function whose graph is given in figure 1 is represented by the conditional expression



Now we are ready to use conditional expressions to define functions recursively. For example, we have


Let us evaluate 2! according to this definition. We have


The reader who has followed these simple examples is ready for the construction of tex2html_wrap_inline2638 which is a straightforward generalization of the above together with a tying up of a few loose ends.

Some notation. Let tex2html_wrap_inline2578 be a collection (finite in the examples we shall give) of functions whose domains and ranges are certain sets. tex2html_wrap_inline2638 will be a class of functions involving the same sets which we shall call computable in terms of tex2html_wrap_inline2578 .

Suppose f is a function of n variables, and suppose that if we write tex2html_wrap_inline2650 , each tex2html_wrap_inline2652 takes values in the set tex2html_wrap_inline2654 and y takes its value in the set V. It is customary to describe this situation by writing


The set tex2html_wrap_inline632 of n-tuples tex2html_wrap_inline636 is called the domain of f, and the set V is called the range of f.

Forms and functions. In order to make properly the definitions that follow, we will distinguish between functions and expressions involving free variables. Following Church [1] the latter are called forms. Single letters such as f, g, h, etc. or sequences of letters such as sin are used to denote functions. Expressions such as f(x,y), tex2html_wrap_inline2688 are called forms. In particular we may refer to the function f defined by tex2html_wrap_inline2692 . Our definitions will be written as though all forms involving functions were written f(,...,) although we will use expressions like x + y with infixes like + in examples.

Composition. Now we shall describe the ways in which new functions are defined from old. The first way may be called (generalized) composition and involves the use of forms. We shall use the letters x,y,... (sometimes with subscripts) for variables and will suppose that there is a notation for constants that does not make expressions ambiguous. (Thus, the decimal notation is allowed for constants when we are dealing with integers.)

The class of forms is defined recursively as follows:

(i) A variable x with an associated space U is a form, and with this form we also associate U. A constant in a space U is a form and we also associate U with this form.

(ii) If tex2html_wrap_inline2712 are forms associated with the spaces tex2html_wrap_inline2714 respectively, then tex2html_wrap_inline2716 is a form associated with the space V. Thus the form f(g(x,y),x) may be built from the forms g(x,y) and x and the function f.

If all the variables occurring in a form e are among tex2html_wrap_inline2730 , we can define a function h by writing tex2html_wrap_inline2734 . We shall assume that the reader knows how to compute the values of a function defined in this way. If tex2html_wrap_inline2736 are all the functions occurring in e we shall say that the function h is defined by composition from tex2html_wrap_inline2736 . The class of functions definable from given functions using only composition is narrower than the class of function computable in terms of these functions.

Partial functions. In the theory of computation it is necessary to deal with partial functions which are not defined for all n-tuples in their domains. Thus we have the partial function minus, defined by minus (x,y) = x-y, which is defined on those pairs (x,y) of positive integers for which x is greater than y. A function which is defined for all n-tuples in its domain is called a total function. We admit the limiting case of a partial function which is not defined for any n-tuples.

The n-tuples for which a function described by composition is defined is determined in an obvious way from the sets of n-tuples for which the functions entering the composition are defined. If all the functions occurring in a composition are total functions, the new function is also a total function, but the other processes for defining functions are not so kind to totality. When the word ``function'' is used from here on, we shall mean partial function.

Having to introduce partial functions is a nuisance, but an unavoidable one. The rules for defining computable functions sometimes give computation processes that never terminate, and when the computation process fails to terminate, the result is undefined. It is well known that there is no effective general way of deciding whether a process will terminate.

Predicates and propositional forms. The space tex2html_wrap_inline2764 of truth values whose only elements are T (for truth) and F (for falsity) has a special role in our theory. A function whose range is tex2html_wrap_inline2764 is called a predicate. Examples of predicates on the integers are prime defined by


and less defined by


We shall, of course, write x < y instead of less(x,y). For any space U there is a predicate tex2html_wrap_inline2782 of two arguments defined by


We shall write x = y instead of tex2html_wrap_inline2788 , but some of the remarks about functions might not hold if we tried to consider equality a single predicate defined on all spaces at once.

A form with values in tex2html_wrap_inline2764 such as x < y, x = y, or prime(x) is called a propositional form.

Propositional forms constructed directly from predicates such as prime(x) or x < y may be called simple. Compound propositional forms can be constructed from the simple ones by means of the propositional connectives tex2html_wrap_inline766 and tex2html_wrap_inline2804 . We shall assume that the reader is familiar with the use of these connectives.

Conditional forms or conditional expressions. Conditional forms require a little more careful treatment than was given above in connection with the example. The value of the conditional form


is the value of the e corresponding to the first p that has value T; if all p's have value F, then the value of the conditional form is not defined. This rule is complete provided all the p's and e's have defined values, but we need to make provision for the possibility that some of the p's or e's are undefined. The rule is as follows:

If an undefined p occurs before a true p or if all p's are false or if the e corresponding to the first true p is undefined, then the form is undefined. Otherwise, the value of the form is the value of the e corresponding to the first true p.

We shall illustrate this definition by additional examples:


The truth value T can be used to simplify certain conditional forms.

Thus, instead of


we shall write


The propositional connectives can be expressed in terms of conditional forms as follows:


Considerations of truth tables show that these formulae give the same results as the usual definitions. However, in order to treat partial functions we must consider the possibility that p or q may be undefined.

Suppose that p is false and q is undefined; then according to the conditional form definition tex2html_wrap_inline798 is false and tex2html_wrap_inline800 is undefined. This unsymmetry in the propositional connectives turns out to be appropriate in the theory of computation since if a calculation of p gives F as a result q need not be computed to evaluate tex2html_wrap_inline798 , but if the calculation of p does not terminate, we never get around to computing q.

It is natural to ask if a function tex2html_wrap_inline2848 of 2n variables can be defined so that


This is not possible unless we extend our notion of function because normally one requires all the arguments of a function to be given before the function is computed. However, as we shall shortly see, it is important that a conditional form be considered defined when, for example, tex2html_wrap_inline2854 is true and tex2html_wrap_inline2856 is defined and all the other p's and e's are undefined. The required extension of the concept of function would have the property that functions of several variables could no longer be identified with one-variable functions defined on product spaces. We shall not pursue this possibility further here.

We now want to extend our notion of forms to include conditional forms. Suppose tex2html_wrap_inline2862 are forms associated with the space of truth values and tex2html_wrap_inline2712 are forms each of which is associated with the space V. Suppose further that each variable tex2html_wrap_inline2652 occurring in tex2html_wrap_inline2862 and tex2html_wrap_inline2712 is associated with the space U. Then tex2html_wrap_inline2876 is a form associated with V.

We believe that conditional forms will eventually come to be generally used in mathematics whenever functions are defined by considering cases. Their introduction is the same kind of innovation as vector notation. Nothing can be proved with them that could not also be proved without them. However, their formal properties, which will be discussed later, will reduce many case-analysis verbal arguments to calculation.

Definition of functions by recursion. The definition


is an example of definition by recursion. Consider the computation of 0!


We now see that it is important to provide that the conditional form be defined even if a term beyond the one that gives the value is undefined. In this case (0 - 1)! is undefined.

Note also that if we consider a wider domain than the non-negative integers, n! as defined above becomes a partial function, since unless n is a non-negative integer, the recursion process does not terminate.

In general, we can either define single functions by recursion or define several functions together by simultaneous recursion, the former being a particular case of the latter.

To define simultaneously functions tex2html_wrap_inline2888 , we write equations


The expressions tex2html_wrap_inline2890 must contain only known functions and the functions tex2html_wrap_inline2888 . Suppose that the ranges of the functions are to be tex2html_wrap_inline2894 respectively; then we further require that the expressions tex2html_wrap_inline2890 be associated with these spaces respectively, given that within tex2html_wrap_inline2890 the f's are taken as having the corresponding V's as ranges. This is a consistency condition.

tex2html_wrap_inline868 is to be evaluated for given values of the x's as follows.

1. If tex2html_wrap_inline2908 is a conditional form then the p's are to be evaluated in the prescribed order stopping when a true p and the corresponding e have been evaluated.

2. If tex2html_wrap_inline2908 has the form tex2html_wrap_inline2918 , then tex2html_wrap_inline2920 are to be evaluated and then the function g applied.

3. If any expression tex2html_wrap_inline2924 occurs it is to be evaluated from the defining equation.

4. Any subexpressions of tex2html_wrap_inline2908 that have to be evaluated are evaluated according to the same rules.

5. Variables occurring as subexpressions are evaluated by giving them the assigned values.

There is no guarantee that the evaluation process will terminate in any given case. If for particular arguments the process does not terminate, then the function is undefined for these arguments. If the function tex2html_wrap_inline2928 occurs in the expression tex2html_wrap_inline2908 , then the possibility of termination depends on the presence of conditional expressions in the tex2html_wrap_inline2908 's.

The class of functions tex2html_wrap_inline2638 computable in terms of the given base functions tex2html_wrap_inline2578 is defined to consist of the functions which can be defined by repeated applications of the above recursive definition process.

next up previous
Next: Recursive Functions of the Up: Formalisms For Describing Computable Previous: Formalisms For Describing Computable

John McCarthy
Wed May 1 17:18:52 PDT 1996