MFCS Conference 2024 Conference Paper
Algorithmic Dimensions via Learning Functions
- Jack H. Lutz
- Andrei N. Migunov
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.