On the Turing complexity of learning finite families of algebraic structures
Journal of Logic and Computation · 22.10.2021 · 31 (7) · 1891-1900
DOI: 10.1093/logcom/exab044 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Logic and Computation, online erschienen am 19.07.2021. Verfasst von Nikolay Bazhenov und 1 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 25 Literaturangaben. Gefördert von: Mathematical Center in Akademgorodok, Austrian Science Fund.
Abstract (Originalsprache)
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.
Förderung
- Mathematical Center in Akademgorodok
- Austrian Science Fund
Zitieren
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