Deux complexités

Pour comprendre la nature profondément différente de ces deux types d'émergenceémergence, il faut cesser d'opposer trop naïvement simplicité et complexité. Car au simple s'oppose en fait deux sortes de complexité que la théorie algorithmiquealgorithmique de l'information a réussi à définir proprement --c'est-à-dire mathématiquement-- mettant fin à une confusion ancienne et désastreuse. Il s'agit de la complexité aléatoire et de la complexité organisée.

Cet éclaircissement résulte des progrès de la théorie du calcul --ou théorie de la calculabilité-- née dans la décennie 1930 des travaux de Kurt GödelKurt Gödel, Alonso Church, et Alan TuringAlan Turing. En proposant une définition mathématique claire de la notion d'algorithme, non seulement la logique mathématique s'est donné l'outil qui lui a permis de démontrer l'insolubilité de certaines questions par un procédé fini (c'est l'indécidabilité de l'arrêt d'un programme, et la multitude de résultats analogues qui ont suivi), mais de plus, elle a fondé une science théorique de l'information qui s'est révélée d'une efficacité surprenante pour l'élucidation de questions aussi délicates que celle de l'opposition simple/complexe ou celle plus délicate encore de l'opposition complexité aléatoire/complexité organisée.

Andrei Kolmogorov. © Domaine public

Andrei Kolmogorov (en URSS) bien informé des avancées de la nouvelle science du calcul, en même temps que Gregory Chaitin (aux États-Unis) propose au milieu des années 1960 de définir la complexité d'un objet fini Ob (par exemple un nombre entier, une suite finie de 0 et de 1, un fichier informatique, une image numérisée) par la taille du plus petit programme capable de le produire :

K(Ob) = taille en nombre de chiffres binairesbinaires du plus court programme Pr qui, lorsqu'il calcule, produit (par exemple en l'imprimant à l'écran) l'objet Ob.

Une telle définition, dont on démontre moyennant quelques précautions, qu'elle est peu sensible au langage utilisé pour écrire les programmes permet d'une façon parfaitement rigoureuse et cohérente de dire qu'une image toute blanche d'un million de pixelspixels est plus simple que l'image d'un million de pixels d'un arbrearbre, ou d'un paysage urbain. L'image toute blanche est produite par un court programme du type «pour chaque numéro de ligne i, pour chaque numéro de colonne j, imprimer un pixel blanc en position (i, j)». En revanche l'image de l'arbre ne peut être produite que par un programme qui contient en lui la donnée des diverses branches, feuilles, aspérités du tronc, etc. ce qui en fait un programme long : pour un million de pixels noirs ou blancs, il faudra au moins un programme de 10 000 chiffres binaires. Le pire des cas est l'image parfaitement mélangée de points noirs ou blancs, car alors le programme minimal en longueur pour produire l'image d'un million de pixels aura lui-même une longueur d'un million de chiffres binaires : le hasard ne se résume pas.

Calculer K(Ob) est souvent très difficile et l'on démontre même que la fonction Ob-->K(Ob) n'est pas calculable (aucun algorithme ne sera jamais en mesure, pour tout objet Ob d'en déterminer exactement la complexité de Kolmogorov K(Ob)). En pratique, cela ne signifie pourtant pas qu'on ne fait rien du concept de complexité de Kolmogorov, mais qu'il faut accepter de mesurer cette complexité de manière approchée. Les algorithmes de compression de données sont pour cela d'excellents outils : la taille de la version comprimée d'une image est une valeur approchée de la complexité de Kolmogorov de cette image. Ce sont d'ailleurs les algorithmes de compression sans perte (c'est-à-dire permettant la reconstitution exacte de l'objet initial) qui sont utilisés avec un succès étonnant par divers chercheurs, dont Paul Vitanyi, dans les méthodes de classification automatique (de textes, de musiques, de séquences génétiquesgénétiques, etc.) fondées sur la complexité de Kolmogorov.