2026-07-23T17:12:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10969 2024-03-06T10:46:56Z ddc:004 open_access

Random Subgroups of Rationals Gao, Ziyuan Jain, Sanjay Khoussainov, Bakhadyr Li, Wei Melnikov, Alexander Seidel, Karen Stephan, Frank Martin-Löf randomness subgroups of rationals finitely generated subgroups of rationals learning in the limit behaviourally correct learning This paper introduces and studies a notion of algorithmic randomness for subgroups of rationals. Given a randomly generated additive subgroup (G,+) of rationals, two main questions are addressed: first, what are the model-theoretic and recursion-theoretic properties of (G,+); second, what learnability properties can one extract from G and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of (G,+) coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for G with respect to any generating sequence for G is not even semi-decidable, one can build a generating sequence beta such that the word problem for G with respect to beta is co-recursively enumerable (assuming that the set of generators of G is limit-recursive). In regard to the second question, it is proven that there is a generating sequence beta for G such that every non-trivial finitely generated subgroup of G is recursively enumerable and the class of all such subgroups of G is behaviourally correctly learnable, that is, every non-trivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of G is limit-recursive). On the other hand, the class of non-trivial finitely generated subgroups of G cannot be syntactically identified in the limit with respect to any generating sequence for G. The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ziyuan Gao and Sanjay Jain and Bakhadyr Khoussainov and Wei Li and Alexander Melnikov and Karen Seidel and Frank Stephan 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.25 urn:nbn:de:0030-drops-109693 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.25 eng https://creativecommons.org/licenses/by/3.0/legalcode