LEARNING THEORY IN THE ARITHMETIC HIERARCHY
- 1 March 2014
- journal article
- research article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 79 (3) , 908-927
Abstract
We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of these sets for the standard notions of finite learning, learning in the limit, behaviorally correct learning and anomalous learning in the limit. In proving the ${\rm{\Sigma }}_5^0$ -completeness result for behaviorally correct learning we prove a result of independent interest; if a uniformly computably enumerable family is not learnable, then for any computable learner there is a ${\rm{\Delta }}_2^0$ enumeration witnessing failure.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Recursively Enumerable Sets and Degrees1987
- Criteria of language learningInformation and Control, 1982
- Inductive inference of formal languages from positive dataInformation and Control, 1980
- Toward a mathematical theory of inductive inferenceInformation and Control, 1975
- Language identification in the limitInformation and Control, 1967