## Anomalous vacillatory learning.(English)Zbl 1290.68061

Summary: In 1986, D. N. Osherson, M. Stob and S. Weinstein asked whether two variants of anomalous vacillatory learning, $$\mathrm{TxtFex}^\ast_\ast$$ and $$\mathrm{TxtFext}^\ast_\ast$$, could be distinguished [Systems that learn: an introduction to learning theory for cognitive and computer scientists. MA: MIT Press University (1986), http://mitpress.mit.edu/books/systems-learn]. In both, a machine is permitted to vacillate between a finite number of hypotheses and to make a finite number of errors. $$\mathrm{TxtFext}^\ast_\ast$$-learning requires that hypotheses output infinitely often must describe the same finite variant of the correct set, while $$\mathrm{TxtFex}^\ast_\ast$$-learning permits the learner to vacillate between finitely many different finite variants of the correct set. In this paper we show that $$\mathrm{TxtFex}^\ast_\ast\neq\mathrm{TxtFext}^\ast_\ast$$, thereby answering the question posed by Osherson et al. [loc. cit.]. We prove this in a strong way by exhibiting a family in $$\mathrm{TxtFex}^\ast_2\setminus\mathrm{TxtFext}^\ast_\ast$$.

### MSC:

 68Q32 Computational learning theory
Full Text: