{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T12:26:57Z","timestamp":1768480017612,"version":"3.49.0"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Mathematical Center in Akademgorodok","award":["075-15-2019-1613"],"award-info":[{"award-number":["075-15-2019-1613"]}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["M 2461"],"award-info":[{"award-number":["M 2461"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,10,22]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1093\/logcom\/exab044","type":"journal-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T19:20:51Z","timestamp":1624908051000},"page":"1891-1900","source":"Crossref","is-referenced-by-count":6,"title":["On the Turing complexity of learning finite families of algebraic structures"],"prefix":"10.1093","volume":"31","author":[{"given":"Nikolay","family":"Bazhenov","sequence":"first","affiliation":[{"name":"Laboratory of Computability Theory and Applied Logic, Sobolev Institute of Mathematics, Novosibirsk 630090, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"San Mauro","sequence":"additional","affiliation":[{"name":"Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Wiedner Hauptstra\u00dfe 8-10\/104, 1040 Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"key":"2021102214134806200_ref1","doi-asserted-by":"crossref","first-page":"891","DOI":"10.2307\/2275058","article-title":"Inductive inference and unsolvability","volume":"56","author":"Adleman","year":"1991","journal-title":"Journal of Symbolic Logic"},{"key":"2021102214134806200_ref2","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1023\/A:1025053225562","article-title":"Constructive and non-constructive infinite formulas in computable structures","volume":"42","author":"Alaev","year":"2003","journal-title":"Algebra and Logic"},{"key":"2021102214134806200_ref3","volume-title":"Computable Structures and the Hyperarithmetical Hierarchy","author":"Ash","year":"2000"},{"key":"2021102214134806200_ref4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/COM-190289","article-title":"Degrees of bi-embeddable categoricity","volume":"10","author":"Bazhenov","year":"2021","journal-title":"Computability"},{"key":"2021102214134806200_ref5","doi-asserted-by":"crossref","first-page":"104590","DOI":"10.1016\/j.ic.2020.104590","article-title":"Learning families of algebraic structures from informant","volume":"275","author":"Bazhenov","year":"2020","journal-title":"Information and Computation"},{"key":"2021102214134806200_ref6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0304-3975(83)90061-0","article-title":"Comparison of identification criteria for machine inductive inference","volume":"25","author":"Case","year":"1983","journal-title":"Theoretical Computer Science"},{"key":"2021102214134806200_ref7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-4305-3","volume-title":"Constructive Models","author":"Ershov","year":"2000"},{"key":"2021102214134806200_ref8","first-page":"383","article-title":"Limit learning equivalence structures","volume-title":"Proceedings of the 30th International Conference on Algorithmic Learning Theory","author":"Fokina","year":"2019"},{"key":"2021102214134806200_ref9","doi-asserted-by":"crossref","first-page":"73","DOI":"10.3233\/COM-140027","article-title":"Degrees that are low for isomorphism","volume":"3","author":"Franklin","year":"2014","journal-title":"Computability"},{"key":"2021102214134806200_ref10","first-page":"120","article-title":"Learning families of closed sets in matroids","volume-title":"Computation, Physics and Beyond\u2014International Workshop on Theoretical Computer Science, WTCS 2012","author":"Gao","year":"2012"},{"key":"2021102214134806200_ref11","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF00269958","article-title":"Inductive inference in the limit","volume":"22","author":"Glymour","year":"1985","journal-title":"Erkenntnis"},{"key":"2021102214134806200_ref12","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","article-title":"Language identification in the limit","volume":"10","author":"Gold","year":"1967","journal-title":"Information and Control"},{"key":"2021102214134806200_ref13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.jcss.2006.09.001","article-title":"On the learnability of vector spaces","volume":"73","author":"Harizanov","year":"2007","journal-title":"Journal of Computer and System Sciences"},{"key":"2021102214134806200_ref14","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6610.001.0001","volume-title":"Systems that Learn: An Introduction to Learning Theory","author":"Jain","year":"1999"},{"key":"2021102214134806200_ref15","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(93)90229-3","article-title":"On the non-existence of maximal inference degrees for language identification","volume":"47","author":"Jain","year":"1993","journal-title":"Information Processing Letters"},{"key":"2021102214134806200_ref16","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1006\/jcss.1996.0018","article-title":"On the structure of degrees of inferability","volume":"52","author":"Kummer","year":"1996","journal-title":"Journal of Computer and System Sciences"},{"key":"2021102214134806200_ref17","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/j.tcs.2008.02.030","article-title":"Learning indexed families of recursive languages from positive data: a survey","volume":"397","author":"Lange","year":"2008","journal-title":"Theoretical Computer Science"},{"key":"2021102214134806200_ref18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316855560","volume-title":"Lectures on Infinitary Model Theory","author":"Marker","year":"2016"},{"key":"2021102214134806200_ref19","volume-title":"Elements of Scientific Inquiry","author":"Martin","year":"1998"},{"key":"2021102214134806200_ref20","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.jcss.2003.08.001","article-title":"Trees and learning","volume":"68","author":"Merkle","year":"2004","journal-title":"Journal of Computer and System Sciences"},{"key":"2021102214134806200_ref21","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/j.aim.2004.10.006","article-title":"Lowness properties and randomness","volume":"197","author":"Nies","year":"2005","journal-title":"Advances in Mathematics"},{"key":"2021102214134806200_ref22","first-page":"379","article-title":"When oracles do not help","volume-title":"Proceedings of the Fourth Annual Workshop on Computational Learning Theory","author":"Slaman","year":"1991"},{"key":"2021102214134806200_ref23","volume-title":"Turing Computability. Theory and Applications","author":"Soare","year":"2016"},{"key":"2021102214134806200_ref24","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0304-3975(00)00272-3","article-title":"Learning algebraic structures from text","volume":"268","author":"Stephan","year":"2001","journal-title":"Theoretical Computer Science"},{"key":"2021102214134806200_ref25","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1016\/j.tcs.2008.02.021","article-title":"Learning recursive functions: a survey","volume":"397","author":"Zeugmann","year":"2008","journal-title":"Theoretical Computer Science"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/7\/1891\/40820270\/exab044.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/31\/7\/1891\/40820270\/exab044.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T14:27:02Z","timestamp":1634912822000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/31\/7\/1891\/6323191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,19]]},"references-count":25,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2021,7,19]]},"published-print":{"date-parts":[[2021,10,22]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exab044","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,10]]},"published":{"date-parts":[[2021,7,19]]}}}