Learning Theory in the Arithmetic Hierarchy
This work addresses foundational problems in computational learning theory for researchers in mathematical logic and theoretical computer science, providing precise complexity classifications.
The paper determines the exact arithmetic complexity of index sets for uniformly computably enumerable families under various learning criteria, including proving a Σ₅⁰-completeness result for behaviorally correct learning and showing that non-learnable families have a Δ₂⁰ enumeration witnessing failure for any computable learner.
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 $Σ_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 $Δ_2^0$ enumeration witnessing failure.