Complexité de Kolmogorov
Présentation informelle
Considérons une machine informatique M pouvant exécuter des programmes. On dit que cette machine est universelle lorsqu’elle peut émuler n'importe quelle autre machine informatique. La machine universelle de Turing en est un exemple.
On note PM l'ensemble des programmes écrits pour la machine M. Pour un programme 
, on note l(p) sa longueur en nombre d’instructions pour la machine M et s(p) sa sortie. La complexité de Kolmogorov KM(x), ou complexité algorithmique, d’une suite x = (xi)i pour une machine M est définie par :
-
.
C’est donc la longueur du plus petit programme écrit pour la machine M qui génère la suite x. Une suite constante a une complexité faible car les programmes qui la génèrent peuvent être très courts.
Reste à savoir dans quelle mesure la fonction KM(x) dépend de la machine M, car on peut tout à fait imaginer une machine possédant des instructions simples pour générer certaines suites complexes. La réponse est la suivante : soit U une machine universelle et M une machine, alors il existe une constante cM telle que pour toute suite x, on ait :
Intuitivement, cM est la longueur d'un interpréteur (ou d'un émulateur), écrit pour la machine U, du langage utilisé par la machine M. On parle alors d’universalité de la complexité de Kolmogorov, en ce sens qu'elle ne dépend pas, à une constante additive près, de la machine considérée.
Une suite peut alors être considérée comme d’autant plus « aléatoire » que sa complexité est grande par rapport à sa taille. De ce point de vue, les décimales des nombres π, e ou 2 ne sont pas vraiment aléatoires puisqu'il existe des algorithmes très simples pour les calculer.
Une partie de cet article (ou d'une version antérieure) est adaptée de [1], sous licence GFDL.