Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 16 Mai 2017

Normal numbers and automatic complexity

par 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:

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30