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_inline2638 . First we adjoin the universal quantifier tex2html_wrap_inline3156 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_inline2764 of truth values. Then


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

Our next step is to allow the description operator tex2html_wrap_inline1154 . tex2html_wrap_inline3200 stands for the unique x such that p(x) is true. Unless there is such an x and it is unique, tex2html_wrap_inline3200 is undefined. In the case of the integers tex2html_wrap_inline3200 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_inline3204 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 17:18:52 PDT 1996