Automatic Kolmogorov complexity, normality, and finite-state dimension revisited (Q2656172)

The paper might be viewed as a survey of concepts related to and results on normal sequences and finite-state dimension. Moreover, it compares new with previous results relating finite automata and complexity. As new concepts the authors introduce automatic Kolmogorov complexity and finite-state a priori probability, which are the natural counterparts of Kolmogorov complexity and Solomonoff-Levin a priori probability in algorithmic information theory. It is shown 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 a normal number and its modifications, equivalences between different definitions of finite-state dimension, Agafonov's and Schnorr's results about finite-state selection rules, can be proved using the new concepts. In connection with (automatic) Kolmogorov complexity a machine-independent characterisation of normality and finite-state dimension in terms of superadditive calibrated functions is given.