Learning Recursive Functions Refutably Authors: Sanjay Jain*, Efim Kinber, Rolf Wiehagen, and Thomas Zeugmann Source: Algorithmic Learning Theory, 12th International Conference, ALT 2001, Washington, DC, USA, November 25-28, 2001, Proceedings,'' (Naoki Abe, Roni Khardon and Thomas Zeugmann, Eds.), Lecture Notes in Artificial Intelligence 2225, pp. 283 - 298, Springer 2001. Abstract. Learning of recursive functions refutably means that for every recursive function, the learning machine has either to learn this function or to refute it, i.e., to signal that it is not able to learn it. Three modi of making precise the notion of refuting are considered. We show that the corresponding types of learning refutably are of strictly increasing power, where already the most stringent of them turns out to be of remarkable topological and algorithmical richness. All these types are closed under union, though in different strengths. Also, these types are shown to be different with respect to their intrinsic complexity; two of them do not contain function classes that are ``most difficult'' to learn, while the third one does. Moreover, we present characterizations for these types of learning refutably. Some of these characterizations make clear where the refuting ability of the corresponding learning machines comes from and how it can be realized, in general. For learning with anomalies refutably, we show that several results from standard learning without refutation stand refutably. Then we derive hierarchies for refutable learning. Finally, we show that stricter refutability constraints cannot be traded for more liberal learning criteria. * Supported in part by NUS grant number RP3992710. ©Copyright 2001, Springer