Affiliations: [a] University of Maryland Department of Computer Science and the University of Maryland Institute for Advanced Computer Studies | [b] Princeton University Department of Computer Science, Princeton, USA | [c] Georgetown University Department of Computer Science, Georgetown, USA
Note: [1] A preliminary version of this work appeared at the Workshop on Computational Learning Theory, Cambridge MA, 1988.
Note: [*] Supported, in part, by National Science Foundation Grant CCR 8803641.
Note: [**] Much of this work was done while the second author was affiliated with the University of Maryland Department of Computer Science.
Note: [***] Supported, in part, by National Science Foundation Grant CCR 870110. Much of this work was done while the third author was on leave at the National Science Foundation. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.
Abstract: Within the study of inductive inference a recurring theme has been to investigate the learning of programs that are not exactly correct. Previous work attempted to quantify the difference between the function to be learned and the one computed by the result of a learning process. In this paper we study a qualitative measure of approximate correctness of the result of attempting to learn a program for a given function. What we require is that the set of errors be somehow easy to describe.
