×

A-posteriori characterizations in inductive inference of recursive functions. (English) Zbl 0542.03020

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).

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
PDFBibTeX XMLCite