EUVIMEDObjevte EUVIMED
Crossref

On the Turing complexity of learning finite families of algebraic structures

Nikolay Bazhenov, Luca San Mauro

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.

AbstraktBibliografické údajeCiteRelated studies

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}
}
Start for free →