On the Amount of Nonconstructivity in Learning Recursive Functions

摘要

Nonconstructive proofs are a powerful mechanism in mathe matics. Furthermore, nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lip-ton [17] and Freivalds [11]. They allow to regard more complicated al gorithms from the viewpoint of much more primitive computational de vices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. In the present paper, the amount of nonconstructivity in learning of recursive functions is studied. Different learning types are compared with respect to the amount of nonconstructivity needed to leaxn the whole class of general recursive functions. Upper and lower bounds for the amount of nonconstructivity needed are proved.