Automatic Kolmogorov Complexity and Normality Revisited

摘要

It is well known that normality (all factors of a given length appear in an infinite sequence with the same frequency) can be described as incompressibility via finite automata. Still the statement and the proof of this result as given by Becher and Heiber (2013) in terms of "loss-less finite-state compressors" do not follow the standard scheme of Kolmogorov complexity definition (an automaton is used for compression, not decompression). We modify this approach to make it more similar to the traditional Kolmogorov complexity theory (and simpler) by explicitly defining the notion of automatic Kolmogorov complexity and using its simple properties. Other known notions (Shallit and Wang [15], Calude et al. [8]) of description complexity related to finite automata are discussed (see the last section). As a byproduct, this approach provides simple proofs of classical results about normality (equivalence of definitions with aligned occurrences and all occurrences, Wall's theorem saying that a normal number remains normal when multiplied by a rational number, and Agafonov's result saying that normality is preserved by automatic selection rules).