Extensional Set Learning
Sebastiaan A. Terwijn · 2000
We investigate the model recBC of learning of r.e. sets, where changes in hypotheses only count when there is an extensional difference. We study the learnability of collections that are uniformly r.e. We prove that, in contrast with the case of uniformly recursive collections, identifiability does not imply recursive BC-identifiability. This answers a question of D. de Jongh. In contrast to the model of recursive identifiability, we prove that the BC-model separates the notions of finite thickness and finite elasticity. 1 Introduction In this paper we consider a model of learning where two hypotheses about the data under consideration are considered equal when they denote the same object, i.e. when they are extensionally the same. This model was first defined for identification of functions in Feldman [6], Barzdin [3]. The first reference for this model in the context of set learning (learning from text) seems to be Osherson and Weinstein [14]. The model, and similar ones, ha...