# From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 58 references that are in the map.
- First posted on arXiv 2 Jun 2021.

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

- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [PAC Learning, VC Dimension, and the Arithmetic Hierarchy](https://mlsanity.com/paper/1406.1111/) (2014)
- [Undecidability of Underfitting in Learning Algorithms](https://mlsanity.com/paper/2102.02850/) (2021)
- [A Computability Perspective on (Verified) Machine Learning](https://mlsanity.com/paper/2102.06585/) (2021)
- [Decidability of Sample Complexity of PAC Learning in finite setting](https://mlsanity.com/paper/2002.11519/) (2020)
- [Incompleteness Ex Machina](https://mlsanity.com/paper/1909.04569/) (2019)
- [Learnability Can Be Independent of ZFC Axioms: Explanations and Implications](https://mlsanity.com/paper/1909.08410/) (2019)

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

- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)
- [Computable learning of natural hypothesis classes](https://mlsanity.com/paper/2407.16663/) (2024)
- [Proper Learnability and the Role of Unlabeled Data](https://mlsanity.com/paper/2502.10359/) (2025)
- [Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning](https://mlsanity.com/paper/2511.02644/) (2025)

## Abstract (arXiv)

Machine learning researchers and practitioners steadily enlarge the multitude of successful learning models. They achieve this through in-depth theoretical analyses and experiential heuristics. However, there is no known general-purpose procedure for rigorously evaluating whether newly proposed models indeed successfully learn from data. We show that such a procedure cannot exist. For PAC binary classification, uniform and universal online learning, and exact learning through teacher-learner interactions, learnability is in general undecidable, both in the sense of independence of the axioms in a formal system and in the sense of uncomputability. Our proofs proceed via computable constructions that encode the consistency problem for formal systems and the halting problem for Turing machines into whether certain function classes are trivial/finite or highly complex, which we then relate to whether these classes are learnable via established characterizations of learnability through complexity measures. Our work shows that undecidability appears in the theoretical foundations of artificial intelligence: There is no one-size-fits-all algorithm for deciding whether a machine learning model can be successful. We cannot in general automatize the process of assessing new learning models.