Chaoticité

Ici, on va se concentrer sur la notion d'aléa telle qu'elle a été formalisée par Kolmogorov en introduisant la notion de complexité. L'approche de Kolmogorov [#!Kol65!#] consiste à introduire une mesure de complexité (chaoticité) et définir ensuite comme aléatoire toute suite vérifiant un critère de chaoticité. Considérons, par exemple, deux suites finies et avec telles que tandis que contient à la fois des 0 et des 1. Intuitivement, la suite est plus complexe que . En effet, est décrite comme la suite des « mille zéros » tandis que la description de doit nécessairement être plus longue puisqu'il faut indiquer les endroits précis où se trouvent les zéros. On va rendre cette intuition rigoureuse.

Cette définition implique que toute application calculable peut être décrite à l'aide d'un algorithme fini. Intuitivement, est un algorithme; si on entre la suite , , ... au clavier d'un ordinateur qui exécute le programme , on obtient

En d'autre termes, décrire la suite finie consiste à trouver une suite finie , telle que la suite (finie ou infinie) commence par , c'est-à-dire .

On voit que la notion d'entropie dépend de l'application optimale choisie. Il existe cependant une constante telle que si et sont des entropies relatives à deux applications optimales différentes, la différence

est uniformément bornée. On note alors l'entropie à une constante près.

Si on choisit comme fonction calculable la fonction identité,  id, on observe que . On a donc la borne évidente ce qui montre que l'entropie d'une suite ne peut pas excéder sa longueur que d'une constante. Les suites où l'inégalité précédente dévient une égalité sont les suites complexes :

Ainsi, les suites chaotiques sont les suites dont la description nécessite un algorithme aussi long que la suite elle même. Les suites aléatoires doivent être chaotiques.

Revenant maintenant aux générateurs algorithmiques des nombres aléatoires, on constate que les suites produites ne sont pas chaotiques. Par exemple, l'entropie de la suite congruentielle est finie puisqu'il suffit de connaître la racine pour déterminer toute la suite.

En conclusion :