Classes with easily learnable subclasses

Abstract

In this paper we study the question of whether identifiable classes have subclasses which are identifiable under a more restrictive criterion. The chosen framework is inductive inference, in particular the criterion of explanatory learning (Ex) of recursive functions as introduced by Gold [Inform. Comput. 10 (1967) 447]. Among the more restrictive criteria is finite learning where the learner outputs, on every function to be learned, exactly one hypothesis (which has to be correct). The topic of the present paper are the natural variants (a) and (b) below of the classical question whether a given learning criterion like finite learning is more restrictive than Ex-learning, (a) Does every infinite Ex-identifiable class have an infinite finitely identifiable subclass? (b) If an infinite Ex-identifiable class S has an infinite finitely identifiable subclass, does it necessarily follow that some appropriate learner Ex-identifies S as well as finitely identifies an infinite subclass of S? These questions are also treated in the context of ordinal mind change bounds. © 2004 Elsevier Inc. All rights reserved.