2021/06/28 by Nikolay Bazhenov, Bazhenov, Nikolay, Luca San Mauro +1
Mathematics · #03D45 #68Q32 #FOS: Mathematics #Logic (math.LO) #math.LO #msc:03D45 #msc:68Q32
paper · pdf · doi:10.48550/arxiv.2106.14515
11 pages, 1 figure, accepted for publication in the Journal of Logic and Computation
arxiv created 2021/06/28 · arxiv updated 2021/06/29
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.