**Authors: Frank Stephan and Sebastiaan A. Terwijn**

**Source: ***Information & Computation* Vol. **154**, No. 2,
1999, 149 - 166.

**Abstract.**
The present work deals with language learning from text. It considers universal learners for classes of languages
in models of additional information and analyzes their complexity in terms of Turing degrees. The following is
shown: If the additional information is given by a set containing at least one index for each language from the
class to be learned but no index for any language outside the class, then there is a universal learner having the
same Turing degree as the inclusion problem for recursively enumerable sets. This result is optimal in the sense
that any other successful learner has the same or higher Turing degree. If the additional information is given by
the index set of the class of languages to be learned then there is a computable universal learner. Furthermore, if
the additional information is presented as an upper bound on the size of some grammar that generates the
language, then a high oracle is necessary and sufficient. Finally, it is shown that for the concepts of finite
learning and learning from good examples, the index set of the class to be learned gives insufficient information
due to the restrictive convergence constraints, these criteria need the jump of the index set instead of the index
set itself. So, they have infinite access to the information of the index set in finite time.

©Copyright 1999, Academic Press