Suites pseudo-aléatoires et complexité de Kolmogorov

Pour simplifier la discussion, on va se limiter au cas des suites composées de zéros et de uns. On veut étudier dans quelles conditions ces suites peuvent être considérées comme de réalisations de suites de Bernoulli avec probabilité 1/2.

On note

l'ensemble de toutes les suites de longueur arbitraire et la longueur de chaque suite , i.e. si alors . Pour tout on note la restriction de à ces premiers éléments.

Pour qu'une telle suite ait des chances de correspondre à notre intuition de l'aléatoire, elle doit être

• stochastique, dans le sens qu'elle vérifie certaines propriétés de stabilité fréquentielle,
• chaotique, dans le sens qu'elle soit désordonnée avec une entropie de Kolmogorov (mesure de l'information contenue) proportionnelle à sa longueur et
• typique, dans le sens que les suites non-typiques sont dans un ensemble effectivement négligeable