Inductive inference of recursive functions: Complexity bounds

Abstract

This survey includes principal results on complexity of inductive inference for recursively enumerable classes of total recursive functions. Inductive inference is a process to find an algorithm from sample computations. In the case when the given class of functions is recursively enumerable it is easy to define a natural complexity measure for the inductive inference, namely, the worst-case mindchange number for the first n functions in the given class. Surely, the complexity depends not only on the class, but also on the numbering, i.e. which function is the first, which one is the second, etc. It turns out that, if the result of inference is Goedel number, then complexity of inference may vary between log₂n+o(log₂n) and an arbitrarily slow recursive function. If the result of the inference is an index in the numbering of the recursively enumerable class, then the complexity may go up to const·n. Additionally, effects previously found in the Kolmogorov complexity theory are discovered in the complexity of inductive inference as well.

The time complexity of prediction strategies (the value f(m+1) is predicted from f(0),..., f(m)) is investigated. It turns out that, if a prediction strategy F is "error-optimal" (i.e. it makes at most log₂n+O(log₂log₂n) errors on the n-th function of the class), then the time complexity of computation of F(<f(0),..., f(m)>) (i.e. a candidate for f(m+1)) may go up, in some sense, to 2^2cm.

Special attention is paid to inductive inference by probabilistic algorithms. It turns out that arbitrary recursively enumerable class of total recursive functions can be identified with ln n + o(log n) mind- changes in an arbitrary numbering of the class.