# On characterizations of learnability with computable learners

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 27 references that are in the map.
- First posted on arXiv 10 Feb 2022.

## Builds on (most cited first, 4 of 4)

- [PAC Learning, VC Dimension, and the Arithmetic Hierarchy](https://mlsanity.com/paper/1406.1111/) (2014)
- [A learning problem that is independent of the set theory ZFC axioms](https://mlsanity.com/paper/1711.05195/) (2017)
- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)
- [On computable learning of continuous features](https://mlsanity.com/paper/2111.14630/) (2021)

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

- [On Computable Online Learning](https://mlsanity.com/paper/2302.04357/) (2023)
- [Find a witness or shatter: the landscape of computable PAC learning](https://mlsanity.com/paper/2302.04731/) (2023)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [Statistical learning theory and Occam's razor: The core argument](https://mlsanity.com/paper/2312.13842/) (2023)
- [Hallucinations are inevitable but can be made statistically negligible](https://mlsanity.com/paper/2502.12187/) (2025)
- [Computable learning of natural hypothesis classes](https://mlsanity.com/paper/2407.16663/) (2024)
- [Effective Littlestone Dimension](https://mlsanity.com/paper/2411.15109/) (2024)
- [Proper Learnability and the Role of Unlabeled Data](https://mlsanity.com/paper/2502.10359/) (2025)
- [On the Computability of Multiclass PAC Learning](https://mlsanity.com/paper/2502.06089/) (2025)
- [Computable universal online learning](https://mlsanity.com/paper/2510.18352/) (2025)
- [Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning](https://mlsanity.com/paper/2511.02644/) (2025)
- [When Is Inductive Inference Possible?](https://mlsanity.com/paper/2312.00170/) (2023)
- [Identifying Information from Observations with Uncertainty and Novelty](https://mlsanity.com/paper/2501.09331/) (2025)
- [On statistical learning of graphs](https://mlsanity.com/paper/2507.13054/) (2025)
- [Samplability makes learning easier](https://mlsanity.com/paper/2512.01276/) (2025)
- [Uniform Computability of PAC Learning](https://mlsanity.com/paper/2601.18663/) (2026)

## Abstract (arXiv)

We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of strong CPAC learning, and provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable VC classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple general argument to exhibit such ndecidability, and initiate a study of the arithmetical complexity of learnability. We briefly discuss the relation to the undecidability result of Ben-David et al. (2019), that motivated the work of Agarwal et al.