# Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 4 Nov 2025.

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

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)
- [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)
- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)
- [Measurability in the Fundamental Theorem of Statistical Learning](https://mlsanity.com/paper/2410.10243/) (2024)
- [Computable learning of natural hypothesis classes](https://mlsanity.com/paper/2407.16663/) (2024)
- [Effective Littlestone Dimension](https://mlsanity.com/paper/2411.15109/) (2024)
- [On computable learning of continuous features](https://mlsanity.com/paper/2111.14630/) (2021)
- [On the Computability of Multiclass PAC Learning](https://mlsanity.com/paper/2502.06089/) (2025)

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

- [Uniform Computability of PAC Learning](https://mlsanity.com/paper/2601.18663/) (2026)

## Abstract (arXiv)

We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Statistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Fundamental Theorem in the computable setting, for instance by introducing an effective VC-dimension. Guided by this, we investigate the connection between CPAC learning and recursively enumerable representable (RER) classes, whose members can be algorithmically listed. Our results show that the effective VC-dimensions can take arbitrary values above the traditional one, even for RER classes, which creates a whole family of (non-)examples for various notions of CPAC learning. Yet the two dimensions coincide for classes satisfying sufficiently strong notions of CPAC learning. We then observe that CPAC learnability can also be characterized via containment of RER classes that realize the same samples. Furthermore, it is shown that CPAC learnable classes satisfying a unique identification property are necessarily RER. Finally, we establish that agnostic learnability can be guaranteed for RER classes, by considering the relaxed notion of nonuniform CPAC learning.