next up previous
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 tex2html_wrap_inline551 . First we adjoin the universal quantifier tex2html_wrap_inline1069 to the operations used to define new functions. Suppose e is a form in a variable x and other variables associated with the space tex2html_wrap_inline675 of truth values. Then


is a new form in the remaining variables also associated with tex2html_wrap_inline675 . tex2html_wrap_inline1081 has the value T for given values of the remaining variables if for all values of x,e has the value T. tex2html_wrap_inline1081 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, tex2html_wrap_inline1081 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 tex2html_wrap_inline1095 which may well be called the class of functions hyper-arithmetic over tex2html_wrap_inline491 since in the case where tex2html_wrap_inline491 = tex2html_wrap_inline1101 on the integers, tex2html_wrap_inline1095 consists of Kleene's hyper-arithmetic functions.

Our next step is to allow the description operator tex2html_wrap_inline1105 . tex2html_wrap_inline1107 stands for the unique x such that p(x) is true. Unless there is such an x and it is unique, tex2html_wrap_inline1107 is undefined. In the case of the integers tex2html_wrap_inline1107 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 tex2html_wrap_inline1119 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 up previous
Next: Ambiguous Functions Up: Formalisms For Describing Computable Previous: Computable Functionals

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