Mesure numérique de la complexité organisée


Le collectionneur universel (6)

Quelle mesure numérique de complexité organisée ?

Questions sur la mesure de la complexité organisée

• Peut-on mesurer la complexité organisée ou, ce qui semble être la même chose, les contenus en calcul des objets numériques ? Si oui quelle est la bonne mesure ou quelles sont les bonnes mesures ? Que faut-il penser de la profondeur logique de Bennett présentée comme une mesure de complexité organisée ?

La complexité organisée (ou complexité structurale) est un concept philosophique utilisé de manière informelle en science, par exemple quand on dit que la complexité d'un mammifère est plus grande que celle d'une bactérie. Dans le cadre de la théorie algorithmique de l'information, des tentatives sont menées pour rendre ce concept mathématique (et donc scientifique). Charles Bennett a proposé la notion de profondeur logique, dans le but de définir mathématiquement une mesure de complexité organisée. Son article fondateur est "Logical depth and physical complexity." (in Rolf Herken A half-century survey on The Universal Turing Machine. Oxford University Press, Inc., 1988.). Il est cependant possible que la profondeur logique ne capte qu'imparfaitement le concept général, et d'ailleurs il existe plusieurs variantes de formalisation mathématique de cette complexité organisée discutées dans l'article de Charles Bennett.

Nous défendons l'idée que la complexité organisée est du contenu en calcul et nous aimons parler à son sujet de « calcul cristallisé ». Une structure non triviale, un animal par exemple, est le résultat d'un long processus d'évolution assimilable à un long calcul. Elle en est la trace et donc la mémoire. Il semble naturel d'admettre que toute structure complexe provient d'un calcul impossible à opérer rapidement et dont elle est le produit : une riche organisation ne peut survenir instantanément à partir de rien, il ne peut y avoir de « génération spontanée » rapide d'objets structurellement complexes ; c'est ce qu'on nomme parfois « la loi de la croissance lente ».

La complexité organisée (qui s'oppose à la complexité aléatoire, par exemple d'une suite de tirages à pile ou face, mesurée par la complexité de Kolmogorov) ne survient jamais brusquement, alors que la complexité aléatoire peut survenir quasi-instantanément, par exemple quand on jette un verre de cristal au sol. La complexité organisée exige que des calculs, c'est-à-dire des interactions répétées avec échanges d'informations, se déroulent longuement. Elle survient progressivement au cours d'une période d'élaboration où des éléments intermédiaires de structures ont été mémorisés (un calcul utile n'oublie pas ce qu'il produit au fur et à mesure qu'il se déroule) et soigneusement assemblés, sélectionnés, coordonnés, transformés pour produire le résultat.

Si on tente de formaliser l'idée avec l'espoir d'obtenir un concept scientifique, il semble inévitable de s'appuyer sur la théorie de la calculabilité née dans des années 1930 des travaux de Kurt Gödel, Alan Turing et qui depuis poursuit son développement en particulier avec la théorie algorithmique de l'information.

La profondeur logique de Bennett d'une suite finie s (en première approximation, le temps de calcul du programme le plus court qui produit s) est une option pour formuler une notion formelle de complexité organisée. Elle permet, en théorie, d'associer une valeur numérique au contenu en calcul d'un objet numérique donné, voire d'un objet physique numérisé. Pour des raisons liées aux phénomènes d'incomplétude et d'indécidabilité, cette mesure numérique est difficile à évaluer, autrement dit à mesurer de manière effective et robuste. Nous soutenons qu'il ne faut cependant pas renoncer à s'y intéresser et que les difficultés qu'il y a à l'évaluer sont sans doute un argument indirect suggérant qu'elle vise juste. Une notion aussi fondamentale est inévitablement difficile à mesurer numériquement : peut-on imaginer mesurer un important contenu en calcul sans avoir à effectuer soi-même une importante quantité de calculs ? Il faut s'attendre à ce que toute définition satisfaisante implique qu'on ne pourra pas mesurer la complexité organisée exactement, ou qu'on ne pourra pas le faire sans aucun risque d'erreur, et que lorsqu'on le fera, cela coûtera cher en calcul.

Plutôt que discuter les détails techniques des définitions de Bennett, il est plus intéressant de suivre la démarche générale qui conduit aux formulations possibles qu'il propose, en explicitant les modes de raisonnement et d'analyse qui sont mis en œuvre. Voici les étapes d'une telle démarche présentée ici comme une analyse sans préjugés et sans précipitation, tentant d'aller au cœur du problème.

(a) On se place dans un cadre mathématiquement bien spécifié et clair : des suites finies de '0' et de '1' ; ce sont ces suites dont nous recherchons à définir la complexité organisée. Cette numérisation ne fait probablement rien perdre d'essentiel — nous n'en discuterons pas ici — et les développements de l'informatique nous aident à comprendre pourquoi : tout semble se numériser et, à la condition de ne pas le faire trop grossièrement, on réussit à disposer de modèles numériques satisfaisants de tout ce qui existe physiquement. Si on refuse ce point, il ne restera qu'une théorie de la complexité organisée des suites finies de '0' et de '1'.

(b) On se demande donc : comment mesurer la complexité organisée — la richesse en structures — d'une suite finie s de '0' et de '1' ?

(c) La théorie de la calculabilité et les arguments évoqués ci-dessus suggèrent de se référer au temps nécessaire à un programme (écrit dans un langage universel) ou à une machine de Turing (ce qui revient au même) pour produire la suite s à laquelle on s'intéresse.

(d) Il faut exiger que les programmes envisagés soient assez courts. Cette condition sur la taille du programme s'impose, car pour toute suite s il existe des programmes longs produisant rapidement s, par exemple les programmes de type print s. Ils sont cependant improbables. Ils ne peuvent raisonnablement pas être à l'origine d'une séquence d'un million de chiffres de Pi présents dans le monde physique sur une feuille ou n'importe où. Si vous rencontrez une telle suite, vous l'attribuerez à un programme assez court ayant calculé Pi ; vous ne trouverez pas envisageable de considérer que c'est par hasard, qu'un programme de type print s a produit ce million de chiffres ; d'ailleurs pour écrire ce programme, il aurait fallu connaître un million de chiffres de Pi, donc l'avoir calculé ; comment ? ; on est revenu au point de départ. Ne considérer que des programmes relativement courts est donc bien une exigence naturelle, autrement dit, l'idée de privilégier les programmes courts provient non pas d'un choix arbitraire, mais d'une analyse préalable fondée sur le bon sens, ou, dit autrement encore, sur une évidence philosophique fondamentale.

(e) Par ailleurs, si s contient du calcul de valeur, c'est qu'un processus de calcul non trivial en est l'origine. Ce calcul — en un certain sens qu'il faut trouver — ne pouvait pas être mené sensiblement plus rapidement. Nous avons donc à concilier deux idées : le calcul qui a donné s a été mené assez rapidement, et il a été mené par un programme assez court.

(f) Il y a plusieurs programmes (machines) qui produisent s (en fait, il y en a toujours une infinité). L'idée a priori assez naturelle de se référer brutalement au plus rapide des programmes donnant s (ou à la plus rapide des machines de Turing produisant s) est mauvaise pour deux raisons :

- (raison technique) parce que le temps de calcul du plus rapide des programmes — ce sera un programme du type print s — sera toujours en gros directement déterminé par la longueur de s indépendamment des détails de s.

- (raison intuitive) parce qu'obtenir s avec un programme ou une machine très longue a moins d'intérêt que l'obtenir avec une machine courte et qu'il faut en tenir compte. L'idée ici est que si on énumère tous les programmes, le temps d'énumération pour arriver aux longs programmes augmente exponentiellement en fonction de leur longueur. Les programmes longs ont donc « moins de valeur », surtout quand on sait qu'en en prenant de très longs on est certain d'en trouver de très rapides qui donneront s (ceux du type print s, nous l'avons déjà dit). Il faut donc, dans la prise en compte du temps de calcul, pénaliser les programmes longs : ils sont improbables quand on procède par hasard, ils sont longs à venir quand on procède par énumération ordonnée.

(g) Autre argument pour justifier encore le privilège à accorder aux des programmes courts donnant s dans une définition du contenu en calcul. Considérer comme acceptable comme origine d'une longue suite s, une autre longue suite s, c'est considérer comme acceptable une explication scientifique d'une courbe f de valeurs numériques mesurées expérimentalement, qui dirait que la loi qui fixe la courbe se définit par la liste des couples (x, f(x)) mesurés. Exprimer la loi demanderait autant d'espace mémoire que les données mesurées ! Procéder ainsi provoquerait le jugement unanime que rien n'a été expliqué. On parlerait d'explication ad hoc, donc sans valeur.

(h) Encore un argument dans le même sens. Il semble nécessaire d'accorder plus de valeur à un calcul fait par un programme court (plus probable) qu'au calcul d'un programme long. La machine qui exécute un programme print s se contente de recopier ce qui est présent dans le programme ; en un sens, elle ne fait rien. Ce type de programmes démontre que certains calculs n'en sont pas vraiment : recopier une donnée écrite dans le texte même du programme n'est pas réellement mener un calcul ; cela n'élabore rien, ne construit rien. Les données ne doivent pas être présentes explicitement dans le programme pour que son temps de calcul possède un sens. Pour qu'un programme compte dans une mesure de contenu en calcul, il est nécessaire qu'il soit assez court.

(i) L'idée première de Charles Bennett est de considérer le temps de calcul du plus court programme qui donne s. C'est une assez bonne idée, mais c'est seulement une des idées possibles pour concevoir une mesure de contenu en calcul. Pour éviter d'accorder trop d'importance au programme le plus court — qui pourrait par malchance être très lent alors qu'un programme légèrement plus long serait très rapide, c'est le point faible de la première définition de Bennett —, il vaut mieux prendre en compte le temps de calcul de plusieurs machines ou programmes produisant s, et cela en donnant plus d'importance aux temps de calcul des programmes courts qu'au temps de calcul des programmes longs. Cette conclusion provisoire est le résultat d'une analyse rationnelle de ce que peut être une mesure de contenu en calcul et donc de complexité organisée. Nous y insistons un peu lourdement car elle est le cœur de problème et qu'elle n'est pas perçue comme allant de soi dans certaines analyses proposées à propos des mesures de complexité organisée (par exemple Cris Adami et and Nicolas Cerf, "Physical complexity of symbolic sequences." Physica D: Nonlinear Phenomena 137.1, 62-69, 2000.)

(j) Les mises en œuvre de cette conclusion sont des essais. Ils sont indispensables pour avancer et arriver à des concepts opérationnels, mais il ne faut pas oublier que l'on introduit alors des éléments plus ou moins arbitraires qui vont au-delà de l'analyse initiale et donc ne peuvent se prévaloir de la même nécessité logique.

(k) Voici quelques possibilités pour mettre en œuvre l'idée générale tirée de l'analyse conceptuelle générale, sans se limiter à retenir seulement le temps de calcul du programme le plus court.

- Prendre les k programmes les plus courts qui produisent s (k fixé) et calculer la moyenne de leurs temps de calcul, ou prendre en compte le temps de calcul du programme le plus rapide parmi les k.

- Même chose en considérant tous les programmes produisant s dont la longueur ne dépassent pas de plus de k bits, la longueur du plus court.

- Même chose en considérant tous les programmes produisant s dont la longueur ne dépasse pas de plus de k bits (k fixé), la longueur de leur version compressée optimale (c'est une idée dont Bennett prouve l'importance en réussissant à démontrer pour elle un résultat d'invariance, c'est-à-dire en établissant que la mesure obtenue ne varie pas trop quand on change de langage de référence, ou de machine de référence).

- Même chose en considérant tous les programmes dont la longueur est inférieure à longueur(s)/2 (ou longueur(s)/k pour un k fixé).

Attention toutefois aux idées séduisantes qui ne marchent pas, comme celle-ci : faire la moyenne pondérée par 1/2longueur(pr) des temps de calcul des programmes pr qui produisent s. Cela ne convient pas car certains programmes longs (qu'on ne voudrait donc pas trop compter) ont des temps de calcul tellement longs qu'ils vont dominer la somme pondérée, somme qui en fait sera toujours infinie (problème des machines dites "busy beaver", https://en.wikipedia.org/wiki/Busy_beaver).

(l) Même, si au bout du compte, mesurer la complexité organisée d'une séquence s en considérant le temps de calcul de certaines machines assez courtes qui calculent s est une idée qui s'impose, il se trouve que malheureusement toutes les formalisations qu'on peut imaginer de l'idée présentent des imperfections et peut-être un certain arbitraire. Il n'est pas certain qu'on puisse trouver une formalisation qui règle proprement et définitivement les difficultés rencontrées dans chaque cas particulier. Cela ne doit pas faire renoncer : ce n'est pas la première fois en science qu'une notion s'impose sans qu'aucune formalisation naturelle satisfaisante ne se présente clairement. L'émergence du concept d'énergie fut longue et difficile par exemple.

(m) Parmi les difficultés rencontrées pour passer de l'idée générale abstraite à une mesure précise concrètement utilisable, il y a le choix des machines qu'on prend comme référence pour mesurer les temps de calcul. Pour qu'elles soient équivalentes ou approximativement équivalentes (de manière à pouvoir disposer d'un théorème d'invariance affirmant que changer de machine ne change pas trop le résultat mesuré) il faut leur imposer des caractéristiques particulières. Charles Bennett utilise ce qu'il nomme des machines de Turing universelles rapides dans son article de 1988. Chaque définition précise aura aussi à opérer un choix limitatif des mécanismes de calcul pris en compte.

(n) De tout cela il résulte qu'il est difficile de défendre l'idée qu'il existe une mesure de complexité organisée de la même nature exactement que les variables physiques fondamentales que sont la longueur, le temps, la masse, l'énergie, etc. (qui ne sont cependant pas sans présenter de difficultés elles aussi). Une mesure définitive de la complexité organisée se présentera sans doute plus comme les mesures rencontrées en thermodynamique (l'entropie est par exemple le log d'un nombre de configurations, et en même temps bien d'autres choses difficiles à ajuster avec la définition combinatoire). Dans notre cas, il se peut que la solution soit encore plus délicate à mettre au point, mais doit-on s'en étonner ?

Conclusions

Cette situation n'empêche pas l'existence d'un domaine scientifique construit sur le concept de complexité organisée comme contenu en calcul. Ce domaine est peut-être d'une nature différente des savoirs scientifiques antérieurs, comme déjà la thermodynamique l'était avec ses concepts, méthodes et résultats fonctionnant assez différemment de ceux de la mécanique newtonienne, ou même de l'électricité. La mécanique quantique a elle aussi contraint à revoir et repenser ce qu'est une théorie scientifique. La théorie de la complexité organisée ne deviendra scientifique que moyennant peut-être la révision de certains de nos préjugés concernant ce que doit être une variable physique, et une échelle de mesure. Les nombres entiers et les nombres réels sont de bons outils pour définir et mesurer les variables physiques rencontrées jusqu'ici. Peut-être faudra-t-il concevoir la notion de variable physique sous une autre forme et sa mesure à l'aide d'outils différents.

Il ne fait cependant aucun doute que s'impose une science de la complexité organisée comme calcul non trivial mémorisé. Cette science est essentielle pour comprendre notre monde sur les longues périodes de temps et plus généralement tous les systèmes computationnellement universels fonctionnant pendant de longues durées. Cette science sera une science à la fois mathématique et physique, même si elle se construit sur des concepts difficilement définissables par des variables traditionnelles (assimilées à des nombres réels), et même si elle est directement concernée par les résultats d'indécidabilité logique (c'est le cas). Il se peut aussi que certains de résultats mathématiques qu'elle formulera ne puissent l'être que sous la forme de conjectures (parce qu'ils sont liés ou du même type que la fameuse conjecture P≠NP)

Reste, et c'est évidemment le plus important, qu'il existe déjà une théorie du calcul, plusieurs méthodes précises pour formaliser la notion de contenu en calcul (présentées par exemple dans l'article de Bennett de 1988), et que les bases d'une théorie du contenu en calcul sont donc aujourd'hui assez solides pour qu'on parle d'une théorie de la complexité organisée et de la mesure de la complexité organisée.

En conclusion, temporairement et en suivant en cela l'article fondamental de Charles Bennett de 1988, il semble raisonnable d'admettre deux points.

(1) Le temps de calcul du plus court programme qui donne s est en première approximation une mesure de son contenu en calcul, et

(2) si on souhaite se placer dans un contexte disposant d'un théorème d'invariance, on introduit une paramètre k (un entier) et on considère que le contenu en calcul mesuré avec la précision k d'une suite s est le temps de calcul du plus rapide des programmes pr pour une machine universelle rapide ayant la propriété d'être impossible à comprimer de plus de k bits. Ce temps de calcul se nomme la k-profondeur logique de s et est le plus avancé et le plus raisonnable de concepts mathématiques pour définir et mesurer la notion de richesse en structures, de complexité organisée ou structurelle, de contenu en calcul.

 


2 commentaires pour “Mesure numérique de la complexité organisée”

  1. Claude Chaunier Répondre | Permalink

    Je sens aussi qu'il ne faille pas se contenter du plus court programme. Et comme vous le suggérez, introduire des moyennes ou imposer une limite de k bits en plus, ou toute autre limite linéaire, multiplicative voire même exponentielle ne résout pas les problèmes. Par exemple un programme dont la longeur est le carré de celle du plus court programme pourrait bien avoir une valeur explicative formidablement supérieure, s'il restait un milliard de fois plus court que la suite qu'il engendre, et si le temps de calcul s'en trouvait ainsi astronomiquement réduit.

    Par ailleurs, la profondeur logique de Bennett n'attribue aucun coût à l'obtention du plus court programme. Alors qu'une idée vague mais intuitive de la complexité organisée pourrait estimer le temps nécessaire à un objet pour qu'il emerge à partir de rien, ou au moins à partir d'un début commun à toutes nos mesures, le big bang par exemple. Par opposition à une mesure de temps qu'il faut à l'objet pour se constituer à partir de l'obtention miraculeuse gratuite et instantanée de conditions initiales minimales variables.

    Il me semble ainsi qu'on souhaite en fait mesurer la valeur minimale d'une expression où la longueur du programme et son temps de calcul entrent simultanément en jeu.

    Que pensez-vous alors de l'alternative suivante : mesurer le temps qu'il faut pour énumérer simplement les 2^L programmes (bien ou mal formés) de longueur L et pour les exécuter en parallèle, ou en alternance de façon entremelée (le 1er pas de chacun des 2^L programme, puis le 2ème pas de chacun, etc.) jusqu'à ce que l'un d'eux produise la suite cherchée s. Nous obtenons ainsi, pour L fixé, le temps de calcul du programme le plus rapide de longueur L produisant s, augmenté ou multiplié par ce qu'il en coûte de sortir ce programme du chapeau, disons 2^L. Appelons f(L) ce temps qui prends en compte à la fois la durée pure de calcul de s une fois son programme choisi, aussi bien qu'un coût pour obtenir ce programme. Est-ce que la valeur minimale que prend f(L), quand L prend toutes les valeurs entières possibles, ne serait pas une meilleur définition de la complexité organisée ?

    • Claude Chaunier Répondre | Permalink

      Il me semble n'avoir fait qu'énoncer la valeur esthétique de Vladik Kreinovich, Luc Longpré et Misha Koshelev (1998) que vous mentionnez dans "La beauté mise en formules" (Pour la Science n°455 septembre 2015), ou du moins son inverse. Fait nouveau peut-être, on peut constater qu'elle serait calculable (en temps fini certes considérable), contrairement à ce que laisse penser votre article, puisqu'aucun programme plus long que la suite s plus une petite constante ne battra le simple programme "print s".

Publier un commentaire