Next: Ambiguous Functions Up: Formalisms For Describing Computable Previous: Computable Functionals

## Non-Computable Functions and Functionals

It might be supposed that in a mathematical theory of computation one need only consider computable functions. However, mathematical physics is carried out in terms of real valued functions which we not computable but only approximable by computable functions.

We shall consider several successive extensions of the class . First we adjoin the universal quantifier to the operations used to define new functions. Suppose e is a form in a variable x and other variables associated with the space of truth values. Then

is a new form in the remaining variables also associated with . has the value T for given values of the remaining variables if for all values of x,e has the value T. has the value F if for at least one value of x,e has the value F. In the remaining case, i.e. for some values of x,e has the value T and for all others e is undefined, is undefined.

If we allow the use of the universal quantifier to form new propositional forms for use in conditional forms, we get a class of functions which may well be called the class of functions hyper-arithmetic over since in the case where = on the integers, consists of Kleene's hyper-arithmetic functions.

Our next step is to allow the description operator . stands for the unique x such that p(x) is true. Unless there is such an x and it is unique, is undefined. In the case of the integers can be defined in terms of the universal quantifier using conditional expressions, but this does not seem to be the case in domains which are not effectively enumerable, and one may not wish to do so in domains where enumeration is unnatural.

The next step is to allow quantification over functions. This gets us to Kleene's [5] analytic hierarchy and presumably allows the functions used in analysis. Two facts are worth noting. First refers to all functions on the domain and not just the computable ones. If we restrict quantification to computable functions, we get different results. Secondly, if we allow functions which can take themselves as arguments, it is difficult to assign a meaning to the quantification. In fact, we are apparently confronted with the paradoxes of naive set theory.

Next: Ambiguous Functions Up: Formalisms For Describing Computable Previous: Computable Functionals

John McCarthy
Wed May 1 20:03:21 PDT 1996