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

摘要

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.