Learning theory in the arithmetic hierarchy

DOI10.1017/JSL.2014.23zbMATH Open1355.03033arXiv1302.7069OpenAlexW2964267194MaRDI QIDQ2933682FDOQ2933682

Authors: Achilles A. Beros 

Publication date: 5 December 2014

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of these sets for the standard notions of finite learning, learning in the limit, behaviorally correct learning and anomalous learning in the limit. In proving the $Sigm{a}_5^0$-completeness result for behaviorally correct learning we prove a result of independent interest; if a uniformly computably enumerable family is not learnable, then for any computable learner there is a $Delt{a}_2^0$ enumeration witnessing failure.

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

Recommendations

• Learning theory in the arithmetic hierarchy. II.
• Learning Theory and Descriptive Set Theory
• PAC learning, VC dimension, and the arithmetic hierarchy
• Inductive inference and computable numberings
• Numberings and learnability

zbMATH Keywords

learning theoryinductive inferencearithmetic hierarchy

Mathematics Subject Classification ID

Computational learning theory (68Q32) Applications of computability and recursion theory (03D80)

Cites Work

• Language identification in the limit
• Title not available (Why is that?)

Cited In (8)

• Infinitary self-reference in learning theory
• PAC learning, VC dimension, and the arithmetic hierarchy
• Learning theory in the arithmetic hierarchy. II.
• Computable PAC learning of continuous features
• Learning families of closed sets in matroids
• Learning Theory and Descriptive Set Theory
• An algebra of human concept learning
• Classifying the Arithmetical Complexity of Teaching Models

This page was built for publication: Learning theory in the arithmetic hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933682)