A-Posteriori Charcterizations in Inductive Inference of Recursive Functions

Author: Thomas Zeugmann

Source: EIK 19, No. 10/11, 1983, 559 - 594.

Abstract. Problems of inductive inference of recursive functions from input-output examples concerning the characterization of identifiable function classes in terms of complexity theory are investigated. In particular, it is shown that for various formalizations of the concept of identification the functions of the classes under consideration can be characterized by uniformly having fastest programs (modulo recursive operator). Moreover, the problem is studied, whether it would even be possible to synthesize such fastest program. Finally, a conjecture is formulated under which conditions a posteriori charcterizations are impossible.

By using the results obtained and the methods developed in the context mentioned above, it is attempted to analyze, in some more detail, the capabilities of computable operators to form classes of functions having a fastest program (modulo recursive operator) in dependence on their types and on the special formalization of a fastest program (modulo recursive operator).

©Copyright 1983 Akademie Verlag.