From undecidability of non-triviality and finiteness to undecidability of learnability

DOI10.1016/j.ijar.2023.109057arXiv2106.01382OpenAlexW4387521408MaRDI QIDQ6064265

Matthias C. Caro

Publication date: 12 December 2023

Published in: International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2106.01382

zbMATH Keywords

undecidabilityVC-dimensiononline learningPAC learningteaching dimensionincomputabilityLittlestone dimension

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Undecidability and degrees of sets of sentences (03D35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Results on learnability and the Vapnik-Chervonenkis dimension
• Some undecidable determined games
• Central limit theorems for empirical measures
• Optimal mistake bound learning is hard
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
• On limited nondeterminism and the complexity of the V-C dimension
• On the complexity of approximating the VC dimension.
• On the complexity of teaching
• Universal Bayes consistency in metric spaces
• Turing Computability
• Undecidable problems: a sampler
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Vapnik-Chervonenkis Classes of Definable Sets
• Recursively enumerable sets and degrees
• 10.1162/153244302760200704
• Machine learning and the Continuum Hypothesis
• Incompleteness Ex Machina
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Convergence of stochastic processes
• A theory of universal learning

This page was built for publication: From undecidability of non-triviality and finiteness to undecidability of learnability