EUVIMEDEUVIMED entdecken
Crossref

On the Turing complexity of learning finite families of algebraic structures

Nikolay Bazhenov, Luca San Mauro

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →