On the Turing complexity of learning finite families of algebraic structures
Journal of Logic and Computation · 2021-10-22 · 31 (7) · 1891-1900
DOI: 10.1093/logcom/exab044 ↗At a glance
Journal article in Journal of Logic and Computation, published online on 2021-07-19. Written by Nikolay Bazhenov and 1 co-authors. Cited 7 times so far (Crossref); 25 references. Funded by: Mathematical Center in Akademgorodok, Austrian Science Fund.
Abstract (original language)
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.
Funding
- Mathematical Center in Akademgorodok
- Austrian Science Fund
Cite
APA
Bazhenov, N., & Mauro, L. S. (2021). On the Turing complexity of learning finite families of algebraic structures. Journal of Logic and Computation, 31(7), 1891-1900. https://doi.org/10.1093/logcom/exab044
Vancouver
Bazhenov N, Mauro LS. On the Turing complexity of learning finite families of algebraic structures. Journal of Logic and Computation. 2021;31(7):1891-1900. doi:10.1093/logcom/exab044
BibTeX
@article{Bazhenov2021,
author = {Bazhenov, Nikolay and Mauro, Luca San},
title = {On the Turing complexity of learning finite families of algebraic structures},
journal = {Journal of Logic and Computation},
year = {2021},
volume = {31},
number = {7},
pages = {1891--1900},
doi = {10.1093/logcom/exab044}
}
EUVIMED