One-sided error probabilistic inductive inference and reliable frequency identification (Q803119)

The paper deals with the inductive synthesis of programs for recursive functions. An inference machine is a recursive device which, when given more and more ordered pairs from the graph of some function, outputs more and more hypotheses, i.e. programs. There are many possible requirements on the sequence of these created programs. The paper deals with ``explanatory'' inference, where the sequence has to converge to a single program correctly computing the given function, as well as ``behaviorally correct'' inference, where all but finitely many programs have to satisfy the relevant correction criterion. Furthermore, the situation is considered where the sequence of programs is required to contain a correct hypothesis with a certain frequency only. A new notion of probabilistic inference, as well as a new concept of reliable identification are introduced. These two types of inference are related to each other and to previously defined modes of identification. One- sided error probabilistic inference is shown to coincide with reliable frequency identification. Four new infinite hierarchies of inferable functions are established and compared with known hierarchies. Although the paper is overburdened with results and is not completely self- contained, it reflects the present state of the theory of inductive inference. The paper may be also useful for those working with machine learning and abstract theory of program synthesis.