# Computable learning of natural hypothesis classes

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 31 references that are in the map.
- First posted on arXiv 23 Jul 2024.

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

- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)
- [Find a witness or shatter: the landscape of computable PAC learning](https://mlsanity.com/paper/2302.04731/) (2023)
- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)

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

- [On The Statistical Limits of Self-Improving Agents](https://mlsanity.com/paper/2510.04399/) (2025)
- [Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning](https://mlsanity.com/paper/2511.02644/) (2025)
- [Uniform Computability of PAC Learning](https://mlsanity.com/paper/2601.18663/) (2026)

## Abstract (arXiv)

This paper is about the recent notion of computably probably approximately correct learning, which lies between the statistical learning theory where there is no computational requirement on the learner and efficient PAC where the learner must be polynomially bounded. Examples have recently been given of hypothesis classes which are PAC learnable but not computably PAC learnable, but these hypothesis classes are unnatural or non-canonical in the sense that they depend on a numbering of proofs, formulas, or programs. We use the on-a-cone machinery from computability theory to prove that, under mild assumptions such as that the hypothesis class can be computably listable, any natural hypothesis class which is learnable must be computably learnable. Thus the counterexamples given previously are necessarily unnatural.