# Learning Theory in the Arithmetic Hierarchy

arXiv: https://arxiv.org/abs/1302.7069 · HTML: https://mlsanity.com/paper/1302.7069/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2013.

## Built on by (most cited first, 2 of 2)

- [On computable learning of continuous features](https://mlsanity.com/paper/2111.14630/) (2021)
- [On statistical learning of graphs](https://mlsanity.com/paper/2507.13054/) (2025)

## Abstract (arXiv)

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 Sigma50-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 Delta20 enumeration witnessing failure.