Information aléatoire

La complexité de Kolmogorov K(Ob) d'un objet Ob mesure son contenu incompressible d'information, son désordre, son "aléatoirité".

Grâce à cette notion mathématique parfaitement précise dès qu'on s'est fixé le langage de référence pour écrire les programmes, les notions vaguesvagues d'objets simples et celle d'objets complexes prennent un sens technique dépourvu de toute ambiguïté, qui a d'ailleurs été utilisé pour l'élaboration de certaines démonstrations mathématiques et la formulation d'une nouvelle analyse de l'entropie en physique statistique (par W. Zurek en 1990).

Cependant la complexité qui est considérée ici n'est que celle donnée par le désordre d'un mélange qui ne produit rien de nouveau : c'est la complexité du détail d'un tas de sablesable, c'est la complexité des résultats d'une suite de tirages à pile ou face, ce n'est pas la complexité d'un organisme vivant, ni celle d'une ville ou d'une puce électronique, ni celle d'ailleurs des décimales d'un nombre comme PiPi ou √ qui suivent des règles précises ne devant rien au hasard. La complexité aléatoire (mesurée par K(Ob)) est la complexité d'un désordre sans règle, elle ne dit rien de l'autre complexité : la complexité organisée, la richesse en structures et sous-structures que l'on trouve dans les organismes vivants, les organisations sociales et les machines de toutes sortes inventées par l'homme. Comment formuler une définition mathématique qui soit pour la complexité organisée ce que la complexité de Kolmogorov est pour la complexité aléatoire ?

Pendant un moment la chose parut impossible, jusqu'à ce que Charles Bennett un physicienphysicien (bien informé des théories du calcul et connaissant le concept de Complexité de Kolmogorov) propose une définition complémentaire de celle de Kolmogorov.

Dans la définition de K(Ob) on ne s'occupe pas du temps de calcul des programmes considérés mais seulement de leur taille (en nombre de symboles binairesbinaires). L'idée de Bennett est de prendre en compte cette durée de calcul (mesurée par le nombre de pas élémentaires de calcul). L'idée la plus naturelle est de regarder le programme le plus rapide qui produit un objet Ob, comme on a considéré le programme le plus court qui produit Ob. Cette idée ne fonctionne pas à cause des programmes triviaux du type print "00100010011" qui très rapidement produisent leurs résultats et sont donc, à de rares exceptions près, toujours les programmes les plus rapides. Pour que le temps de calcul d'un programme ait un sens, il faut que le programme soit bien ajusté à son objet et en exploite les structures et les régularités, ce qui n'est pas le cas des programmes du type print "00100010011" qui s'appliquent à tout, trivialement. La solution de Bennett, dont il a démontré de manière satisfaisante qu'elle est celle attendue, consiste à considérer le temps de calcul du plus court programme qui produit Ob. Ce temps de calcul s'appelle la profondeur logique de Ob. On la note P(Ob) :

P(Ob) = temps de calcul, mesuré en nombre de pas de calcul, du plus court programme Pr qui, lorsqu'il fonctionne, produit (par exemple en l'imprimant à l'écran) l'objet Ob.

La profondeur logique d'une image toute blanche et celle de l'image d'un nuagenuage de points aléatoires sont toutes les deux faibles : ce sont des images d'objets sans richesse de structure, sans contenu authentique en information. En revanche, la profondeur logique d'un objet finement organisé comme les chiffres de Pi ou une puce d'ordinateurordinateur est sensiblement plus élevée : en effet, le plus court programme exploite les propriétés particulières de l'objet que l'exécution du plus court programme "déplie" ce qui demande de nombreuses étapes de calcul.

Dans de tels cas, le passage du plus court programme à l'objet n'est pas la simple exécution d'un print mais le parcours d'un chemin computationnel, riche en boucles récursives, en appel à sous-procédures, etc.