Alexander Shen (LIRMM, Montpellier)

A classical notion of Borel normality of a sequence (all substrings of given length appear with the same frequency) can be considered as the minimal requirement for an individual random sequence. Most definitions of algorithmic randomness (Martin-Löf, Schnorr and others; Kurtz randomness is an exception) imply normality. Algorithmic randomness theory says, roughly speaking, that randomness is equivalent to incompressibility (the prefixes of a sequence do not have a description that is significantly shorter than the prefix itself; the formal definition of incompressibility uses the notion of Kolmogorov complexity). So it is natural to expect that normality is equivalent to “weak incompressibility” (when only very restricted class of description is considered). Indeed, this is the case: many results (Schnorr, Stimm, Agafonov, Becher, Heiber…) show that normality is closely related to finite automata.

In this talk we will suggest a reformulation of this connection between normaility and incompressibility via finite automata that follows the general scheme for Kolmogorov complexity and allows us to give simple proofs for classical results about normal numbers (e.g., Wall’s theorem: normal real remains normal if multiplied by a rational number).

The talk is based on the preprint: https://arxiv.org/pdf/1701.09060.pdf