Ce qui vient au hasard est-il complexe ?

La question posée est bien sûr imprécise, et nous allons en donner plusieurs interprétations qui conduiront à plusieurs réponses. Aucune n'est la réponse, mais leur ensemble est utile et répond à l'interrogation initiale d'une manière intéressante, nous apprenant quelque chose sur la surprise que nous ressentons quand nous découvrons que notre univers est riche et structuré. Que les théories du calcul et de l'information soient en mesure de proposer des réponses à de telles questions semblera étrange, c'est pourtant le cas. Cela nous indique que ces théories ont une portée philosophique qui n'a peut-être pas encore été bien perçue et dont il faudrait tenter l'approfondissement.

La question comporte deux éléments qu'il faut préciser (« au hasard » et « complexe ») pour arriver à produire des réponses.

Pour chacun des deux éléments, nous n'allons envisager que deux options que nous croyons être les principales. Il y aura donc quatre versions précises de la question initiale. Bien sûr, vous êtes libre d'en imaginer d'autres qui vous conduiront à d'autres réflexions et réponses. L'important ici n'est pas principalement la réponse, mais le  travail fait sur la question et le cheminement de pensée qu'elle suscite.

Pour donner un sens à la question, nous allons nous limiter aux objets finis, qu'en bon citoyen de notre monde numérique, nous assimilerons à des suites de '0' et de '1' de longueur n (un entier).

Première réponse

« Au hasard » aura pour sens « tiré uniformément ».

« Ce qui vient au hasard est-il complexe ? » à donc pour sens : « Une suite de '0' et de '1' quelconque de longueur n choisie sans en favoriser aucune (probabilité uniforme sur les 2ⁿ suites envisagées) est-elle complexe ? »

Le mot « complexe » d'après la théorie la plus générale s'appliquant à des suites numériques signifie « ayant une grande complexité de Kolmogorov ». Rappelons que la complexité de Kolmogorov d'une suite binaire s est la taille du plus petit programme qui produit s.

(pour plus de précisions sur cette notion, voir a ou b ou c)

La complexité de Kolmogorov d'une suite s est son contenu incompressible d'information. C'est la quantité minimale d'informations (mesurée en bits) qu'il faut transmettre à quelqu'un à qui on veut décrire la suite s sans la dégrader. C'est la taille du fichier compressé au mieux permettant de retrouver s, quand il sera décompressé.

La question a maintenant un premier sens mathématique précis :

Version 1 - Une suite de '0' et de '1' quelconque de longueur n choisie sans en favoriser aucune (probabilité uniforme sur les 2ⁿ suites possibles) a-t-elle une grande complexité de Kolmogorov ?

La réponse est connue et facile à démontrer : oui, sauf cas exceptionnels, une suite tirée au hasard aura une grande complexité de Kolmogorov. En effet, parmi les suites de '0' et de '1' de longueur n, presque toutes ont une complexité de Kolmogorov de l'ordre de n, ce qui est proche du maximum possible pour une suite de n bits. Dit autrement : sauf dans des cas très rares, une suite s prise uniformément est incompressible. L'article de la rubrique Logique et calcul du mois d'août 2014 de la revue Pour la science détaille en langage simple la preuve de ce résultat  (voir page 77, encadré 2).

Cette première réponse est la plus naturelle et elle signifie quelque chose d'important : si les objets du monde sont assimilables à des objets tirés uniformément (autrement dit à des arrangements parfaitement aléatoires d'atomes et de molécules), alors leurs descriptions brutes sont incompressibles et donc d'une certaine façon inconnaissables. En effet chaque partie d'un tel monde demanderait pour qu'on la représente une mémoire aussi grande qu'elle-même ; rien ne pourrait être réduit, compressé, rien ne pourrait donner prise à de la connaissance : la connaissance ne serait que de la recopie coûteuse.

Seconde réponse

Heureusement, le monde n'est pas « aléatoire » dans le sens de la probabilité uniforme : ses composants sont regroupés et plus ou moins rangés en structures que nous percevons. La matière n'est pas également répartie dans l'espace, les atomes de fer qu'on trouve dans un bloc de matière sont le plus souvent collés les uns aux autres, les molécules d'ADN d'un organisme vivant sont toutes les mêmes à très peu de choses près, etc.

Ce qu'on rencontre dans notre monde n'est donc pas aléatoire au sens de la mesure uniforme ; ce n'est pas le désordre total. Se poser la question « Ce qui vient au hasard est-il complexe ? » doit donc envisager une autre mesure sur les objets (pour nous des suites de longueur n de '0' et de '1' dans nos tentatives de modélisation mathématique).

La seule mesure naturelle générale envisageable pour remplacer la distribution uniforme est, je pense, la mesure universelle de Levin, ou distribution de Solomonoff-Levin, ou encore probabilité algorithmique. Dit très simplement, cette distribution de probabilité entre suites de '0' et de '1' de même longueur est ce qu'on obtient quand on assimile le monde au produit d'une sorte de grand système de calcul (une multitude d'ordinateurs ou de systèmes menant des calculs) dont les programmes seraient tirés au hasard. Le monde engendré par cet immense mécanisme effectuant des calculs parallèles n'est pas un monde uniforme, mais un monde où les suites simples sont bien plus fréquentes que les suites complexes (0000000000 sera plus souvent présents par exemple que 0100101011).

On trouvera ici des résultats attestant de ces affirmations : on a fait calculer un très grand nombre de machines élémentaires, et on a observé la distribution de ce qu'elles produisaient, retrouvant expérimentalement un résultat annoncé par Leonid Levin : les séquences les plus simples (au sens de Kolmogorov) sont les plus probables quand on examine de manière systématique des productions d'algorithmes.

Il n'est pas absurde, et c'est, je pense, l'hypothèse la plus raisonnable, de considérer qu'en l'absence d'informations plus précises sur ce que pourraient être des données quelconques provenant de notre univers, qu'elles suivent cette mesure de Levin (plutôt que la mesure uniforme). L'idée que les composants de l'univers mènent une sorte de calcul, que leurs interactions sont équivalentes à l'exécution d'une multitude de processus algorithmiques simultanés, et que ce qu'on voit donc de l'univers est assimilable à la production d'un grand ordinateur parallèle faisant fonctionner tous les programmes possibles est une idée meilleure que l'idée que tout dans l'univers est décrit par un hasard uniforme (dont la première conséquence serait l'impossibilité de toute connaissance).

Pour en savoir plus sur cette mesure de Levin consulter a ou b.

La seconde façon de comprendre la question « Ce qui vient au hasard est-il complexe ? » et qu'on doit considérer bien plus naturelle que la version 1 est donc :

Version 2 - Une suite de '0' et de '1' de longueur n choisie en se basant sur la mesure de Levin, a-t-elle une grande complexité de Kolmogorov ?

La réponse là encore est donnée par la théorie : les suites simples (de faible complexité de Kolmogorov) de longueur n, sont bien plus probables (pour la mesure de Levin) que les autres. Contrairement, à ce qu'on observe dans un monde régi par la loi uniforme, ce que nous observons dans un monde régi par la mesure de Levin est de la simplicité relative. Cette réponse de la théorie confirme que l'assimilation de notre monde à un grand système de calcul n'est pas absurde : ce que nous voyons dans le monde est le plus souvent, du point de vue de l'information, simple (comparé à un mélange uniforme) : espace vide ; matière homogène (les molécules d'eau, de fer, etc. sont assez peu mélangées, etc.).

C'est cette possibilité de comprimer l'information perçue qui permet la connaissance, la formulation de lois scientifiques, l'action, et donc aussi la vie, la culture, la civilisation, le progrès technique.

Troisième et quatrième réponses

Ce que je viens d'écrire vous aura peut-être choqué, car il est commun de dire que notre monde est complexe et que la complexification progressive de l'univers a engendré aujourd'hui un univers d'une extrême et merveilleuse complexité dont la vie terrestre est les plus bel exemple. La simplicité dont la seconde réponse nous dit qu'elle est la règle semble en contradiction avec cette complexité observée et souvent considérée comme croissante.

Une telle réaction est légitime, mais elle provient d'une confusion dans les termes. En effet, la complexité dont on parle quand on dit qu'un organisme vivant est complexe n'est pas celle que mesure la complexité de Kolmogorov. Il y a deux sortes de complexités. Il y a la complexité aléatoire mesurée par la complexité de Kolmogorov (liée à un contenu incompressible d'information), et la complexité structurelle qui est liée à un contenu en organisations (ou une richesse en structures) ce contenu étant lui-même lié à un contenu en calculs. Cette seconde complexité (celle à laquelle on se réfère sans le préciser et même sans le savoir quand on parle de complexification) est plus difficile à mesurer que le contenu incompressible d'information (la complexité de Kolmogorov). Charles Bennett a proposé de mesurer cette complexité par ce qu'il nomme la profondeur logique (c'est le temps de calcul d'un programme court produisant s). Voir plus de précision sur cette notion en a ou b ou c ou d ou e.

Si on prend en compte cette notion de complexité d'organisation, alors les deux façons envisagées plus haut de comprendre la question « Ce qui vient au hasard est-il complexe ? » conduisent à deux nouvelles versions de cette question :

Version 3 - Une suite de '0' et de '1' quelconque de longueur n choisie sans en favoriser aucune (probabilité uniforme sur les 2ⁿ suites envisagées) a-t-elle une grande profondeur logique Bennett ?

Version 4 - Une suite de '0' et de '1' de longueur n choisie en se basant sur la mesure de Levin a-t-elle une grande profondeur logique Bennett ?

Les réponses est non à la fois pour V3 et pour V4 : les suites choisies uniformément au hasard, ou choisies selon la mesure de Levin ont peu de chance d'être complexes au sens de la complexité organisée.

Dans le cas de la mesure de Levin (donc celle pertinente pour notre monde si on accepte l'idée d'un univers-ordinateur) être structuré simplement est très probable, mais être fortement structuré est très peu probable. C'est bien ce que nous voyons !

Il y a là, je crois, une explication profonde du fait que dans notre univers nous observons des objets complexes au sens de très organisés comme les êtres vivants, mais qu'ils sont rares, très rares en regard de l'étendu du cosmos, qui lui est en gros assez simple.

Bien sûr ces réponses fournies par la théorie de la calculabilité sont sommaires. Elles ne dispensent pas d'y regarder de plus près pour tenter de comprendre ce qu'est le cosmos, la vie sur terre, comment elle apparaît, se développe, ni les diverses formes de complexités organisées qu'on observe dans les objets produits par nos civilisations (livres, organisations sociales, œuvres d'art, voitures, ordinateurs, réseaux, etc.).

Il semble bon cependant de disposer de concepts généraux abstraits compatibles au niveau le plus général avec ce que nous observons de notre univers. Ce sont, je crois, ceux évoqués dans les quatre versions de la question initiale. Ce sont les plus pertinents parmi ceux dont nous disposons aujourd'hui pour comprendre les problèmes généraux de la complexité. Ils nous disent : notre monde n'est pas uniforme, il est organisé un peu comme le serait le produit d'une multitude de calculs. C'est pour cela qu'il est connaissable, la simplicité (comme faible contenu en information) y est dominante, et la grande complexité structurelle y est naturellement rare.