Skip to Main content Skip to Navigation
Journal articles

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited

Abstract : In this paper we characterize normal sequences and finite-state dimension in terms of the automatic Kolmogorov complexity and finite-state a priori probability. We show that many known results about normal sequences and finite-state dimension, including the equivalence between aligned and non-aligned normality, Wall's theorem, Piatetski–Shapiro's theorem, Champernowne's example of normal number and its modifications, equivalences between different definitions of finite-state dimension, Agafonov's and Schnorr's results about finite-state selection rules, become easy corollaries of this characterization. For that we use notions of automatic (finite-state) complexity and finite-state a priori probability that are the natural counterparts of the notions of Kolmogorov complexity and Solomonoff–Levin a priori probability in the algorithmic information theory. We also give a machine-independent characterization of normality and finite-state dimension in terms of superadditive calibrated functions. We compare our approach with previous results and notions relating finite automata and complexity.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03371116
Contributor : Alexander Shen Connect in order to contact the contributor
Submitted on : Friday, October 8, 2021 - 1:24:10 PM
Last modification on : Tuesday, October 12, 2021 - 3:35:18 AM

Links full text

Identifiers

Collections

Citation

Alexander Kozachinskiy, Alexander Shen. Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. Journal of Computer and System Sciences, Elsevier, 2021, 118, pp.75-107. ⟨10.1016/j.jcss.2020.12.003⟩. ⟨lirmm-03371116⟩

Share

Metrics

Record views

4