Zeugmann, Thomas A-posteriori characterizations in inductive inference of recursive functions. (English) Zbl 0542.03020 Elektron. Inform.-verarb. Kybernetik 19, 559-594 (1983). 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 function classes under consideration can be characterized by uniformly having a fastest program (modulo recursive operator). Moreover, the problem is studied, whether it would even be possible to synthesize such a fastest program. Finally, a conjecture is formulated under which conditions a-posteriori characterizations 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 its types and on the special formalization of a fastest program (modulo recursive operator). Cited in 8 Documents MSC: 03D15 Complexity of computation (including implicit computational complexity) 03D20 Recursive functions and relations, subrecursive hierarchies 68T05 Learning and adaptive systems in artificial intelligence 68Q25 Analysis of algorithms and problem complexity Keywords:identifiability of recursive functions; inductive inference of recursive functions; fastest program; computable operators PDFBibTeX XMLCite \textit{T. Zeugmann}, Elektron. Informationsverarbeitung Kybernetik 19, 559--594 (1983; Zbl 0542.03020)