LEARNING RECURSIVE FUNCTIONS FROM APPROXIMATIONS

This article investigates algorithmic learning, in the limit, of corre ct programs for recursive functions f from both input/output examples of f and several interesting varieties of approximate additional ( alg orithmic) information about f, Specifically considered, as such approx imate additional information about f, are Rose's frequency computation s for land several natural generalizations from the literature, each g eneralization involving programs for restricted trees of recursive fun ctions which have las a branch. Considered as the types of trees are t hose with bounded variation, bounded width, and bounded rank. For the case of learning final correct programs for recursive functions, EX-le arning, where the additional information involves frequency computatio ns, an insightful and interestingly complex combinatorial characteriza tion of learning power is presented as a function of the frequency par ameters. For EX-learning (as well as for BC-learning, where a final se quence of correct programs is learned), for the cases of providing the types of additional information considered in this paper, the maximal probability is determined such that the entire class of recursive fun ctions is learnable with that probability. (C) 1997 Academic Press.