arXiv:2106.14515 Abstract | arXiv Analytics

arXiv:2106.14515 [math.LO]Abstract References Reviews Resources

On the Turing complexity of learning finite families of algebraic structures

Published 2021-06-28Version 1

In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the other hand, we construct a pair of structures which is learnable but no computable learner can learn it.

Comments: 11 pages, 1 figure, accepted for publication in the Journal of Logic and Computation

Categories: math.LO

Subjects: 68Q32, 03D45

Keywords: learning finite families, algebraic structures, turing complexity, learn finite families, algorithmic learning theory

Related articles: Most relevant | Search more

arXiv:1905.01601 [math.LO] (Published 2019-05-05)

Learning families of algebraic structures from informant

Nikolay Bazhenov, Ekaterina Fokina, Luca San Mauro

arXiv:1410.8298 [math.LO] (Published 2014-10-30)

Scalar extensions for algebraic structures of Lukasiewicz logic

Serafina Lapenta, Ioana Leustean

arXiv:2005.07829 [math.LO] (Published 2020-05-15)