The formalism previously described enables us to define functions that have functions as arguments. For example,

can be regarded as a function of the numbers *m* and *n* and the
sequence . If we regard the sequence as a function *f* we can write the recursive definition

or in terms of the conventional notation

Functions with functions as arguments are called *functionals*.

Another example is the functional *least*(*p*) which gives the least integer *n*
such that *p*(*n*) for a predicate *p*. We have

where

In order to use functionals it is convenient to have a notation for naming
functions. We use Church's [1] lambda notation. Suppose we have a function *f*
defined by an equation where *e* is some expression in . The name of this function is . For example, the name
of the function *f* defined by is .

Thus we have

but

The variables occurring in a definition are dummy or bound variables and can be replaced by others without changing the function provided the replacement is done consistently. For example, the expressions

and

all represent the same function.

In the notation is represented by and the least
integer *n* for which is represented by

When the functions with which we are dealing are defined recursively, a difficulty arises. For example, consider *factorial* defined by

The expression

cannot serve as a name for this function because it is not clear that the occurrence of ``factorial'' in the expression refers to the function defined by the expression as a whole. Therefore, for recursive functions we adopt an additional convention, Namely,

stands for the function *f* defined by the equation

where any occurrences of the function letter *f* within *e* stand for the function
being defined. The letter *f* is a dummy variable. The factorial function then has
the name

and since *factorial* and *n* are dummy variables the expression

represents the same function.

If we start with a base domain for our variables, it is possible to consider a hierarchy of functionals. At level 1 we have functions whose arguments are in the base domain. At level 2 we have functionals taking functions of level 1 as arguments. At level 3 are functionals taking functionals of level 2 as arguments, etc. Actually functionals of several variables can be of mixed type.

However, this hierarchy does not exhaust the possibilities,
and if we allow functions which can take themselves as arguments we
can eliminate the use of *label* in naming recursive functions. Suppose
that we have a function *f* defined by

where is some expression in *x* and the function variable *f*. This
function can be named

However, suppose we define a function *g* by

or

We then have

since *g*(*x*,*g*) satisfies the equation

Now we can write *f* as

This eliminates *label* at what seems to be an excessive cost. Namely, the
expression gets quite complicated and we must admit functionals capable of
taking themselves as arguments. These escape our orderly hierarchy of
functionals.

Wed May 1 17:18:52 PDT 1996