2026-07-21T19:38:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20628 2024-08-23T05:50:30Z ddc:004 open_access

Algorithmic Dimensions via Learning Functions Lutz, Jack H. Migunov, Andrei N. algorithmic dimensions learning functions randomness We characterize the algorithmic dimensions (i.e., the lower and upper asymptotic densities of information) of infinite binary sequences in terms of the inability of learning functions having an algorithmic constraint to detect patterns in them. Our pattern detection criterion is a quantitative extension of the criterion that Zaffora Blando used to characterize the algorithmically random (i.e., Martin-Löf random) sequences. Our proof uses Lutz’s and Mayordomo’s respective characterizations of algorithmic dimension in terms of gales and Kolmogorov complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jack H. Lutz and Andrei N. Migunov 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.72 urn:nbn:de:0030-drops-206282 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.72 eng https://creativecommons.org/licenses/by/4.0/legalcode