La complexité des petits objets

Comparer deux petits objets A et B entre eux, et dire que A est plus simple que B est naturel et nous le faisons souvent sans nous poser de questions à propos de deux mots, deux images, deux jouets, deux motifs décoratifs, etc. Il se trouve que ce n'est que récemment qu'on a pu trouver une justification théorique à cette pratique.

Personne ne contestera que 0000000000 (une petite séquence de 10 bits) est plus simple que 0101010101, qui elle-même est plus simple que 1101101101 ou 0101110101.

Entre les deux dernières séquences, nous hésitons un peu, mais s'il fallait absolument choisir de les classer nous choisirions sans doute de dire que 1101101101 est plus simple que 0101110101 car la séquence 1101101101 est composée d'une répétition (interrompue) de 110.

Comment justifier un tel classement et l'étendre à toutes les séquences de 10 bits, ou plus généralement, à toutes les séquences finies de bits, ou plus généralement encore, de symboles ?

La complexité de Kolmogorov de s (taille du plus court programme qui engendre la séquence s, (voir le blog précédent ou a b c ) ne convient pas, car pour les séquences courtes, selon le langage de programmation auquel on se réfère pour parler de « taille du plus court programme » on obtient des réponses très différentes les unes des autres.

La complexité de Kolmogorov est le meilleur concept quand on traite de longues séquences, et certains résultats mathématiques s'interprètent comme l'affirmation de son universalité. Il s'agit alors d'une mesure de la complexité comme « contenu en informations » à ne pas confondre avec la complexité comme « richesse en structures » qui, elle, est mieux mesurée par la profondeur logique de Bennett (voir le blog précédent). Ici nous ne parlerons que de complexité comme « contenu en informations ».

Pour les séquences courtes, on ne peut donc pas s'appuyer sur la complexité de Kolmogorov conçue comme taille du plus court programme donnant s. Heureusement, un théorème dû à Leonid Levin suggère une méthode permettant de donner de manière stable un sens à la complexité de Kolmogorov des séquences courtes. Ce théorème indique que la complexité de Kolmogorov de s est égale (avec une erreur majorée par une constante) à l'opposé du logarithme (en base 2) de la probabilité qu'un programme tiré au hasard donne s.

Ne vous sauvez pas ! L'idée est très simple, c'est celle-ci :

- Quand on écrit n'importe quoi dans un programme sans avoir aucun but fixé, on écrit le plus souvent quelque chose qui n'est même pas syntaxiquement correct ; ne nous intéressons donc qu'aux cas où ce qu'on écrit est vraiment un programme. On envisage donc des programmes écrits au hasard, mais syntaxiquement corrects. Il est clair — il faut réfléchir un peu, mais on se persuade assez vite — que l'on produira plus souvent des programmes donnant la séquence 0000000000 que la séquence 0101110101, car les programmes produisant 0000000000 sont plus nombreux et qu'il en existe de très courts : en procédant au hasard on tombera donc plus fréquemment sur ceux qui en calculant donneront 0000000000 que 0101110101. Plus une séquence est complexe (au sens du contenu en informations) plus la probabilité d'écrire au hasard un programme qui la produise est faible. Et réciproquement : si une séquence s'obtient très rarement comme résultat d'un programme, c'est qu'elle a un fort contenu en informations (qu'on ne met pas aisément par le simple fait du hasard dans un programme). C'est ce que dit le théorème de Levin, et il le dit d'une manière précise :

K(s) = - log(Probabilité(s)) + c(s)

où c(s) est fonction majorée par une constante, et Probabilité désigne la probabilité de trouver s comme résultat d'un programme choisi au hasard (idée qu'on sait définir avec rigueur). Cette fonction s'appelle mesure de Levin, ou mesure de Solomonoff-Levin ou probabilité algorithmique. Voir a ou b.

L'intérêt de cette autre définition de la complexité de Kolmogorov (qui, il faut y insister, est considérée comme le concept le plus général pour parler de complexité comme contenu en information) est qu'elle donne pour les séquences courtes ce qu'attend notre intuition et cela sous une forme stable.

On s'en est aperçu non pas grâce à une démonstration, mais grâce à des calculs massifs ayant demandé plusieurs semaines de travail à des ordinateurs assez puissants.

-1- On a considéré la notion la plus fondamentale de langage de programmation (basée sur ce qu'on nomme les machines de Turing).

-2- On a énuméré des milliards de programmes (précisément  : toutes les machines de Turing à 5 états).

-3- On a examiné leurs productions en comptant pour chaque séquence finie obtenue le nombre de fois qu'elle a été obtenue.

-4- Cela a donné une version approchée de la probabilité de Levin associée à chaque séquence binaire finie (en fait seulement pour les séquences assez courtes).

-5- On en a tiré une mesure approchée de la complexité de Kolmogorov.

Miracle ! Ce que donne cette façon de s'y prendre est bien stable et conforme à ce qu'intuitivement on attendait :

- la séquence 0000000000 est plus simple que 0101010101, qui elle-même est plus simple que 1101101101 qui elle-même est plus simple que 0101110101.

Dur nos exemples on trouve dans l'ordre : 22,78 ;  23,93 ; 25,79 ;  26,66.

(le calcul ne donne pas un entier, mais cela est sans importance et permet même une meilleure discrimination des complexités).

Un calculateur de cette complexité résultant de l'énumération de toutes les machines de Turing à 5 états est proposé par le Algorithmic Nature groupLa page internet où ces évaluations sont faisables est complexitycalculator.

On dispose donc aujourd'hui d'une méthode permettant d'attribuer une complexité aux séquences courtes et cela de manière parfaitement objective et stable, en utilisant un procédé dont la théorie nous indique qu'il est universel. Ce que nous faisons depuis toujours — attribuer du sens à la comparaison de la complexité d'objets assez petits — et que la théorie mathématique de la complexité ne réussissait pas à justifier et à comprendre, a maintenant un sens et une base sérieuse.

Reste que pour l'instant la connaissance objective des petites complexités est limitée aux séquences très courtes (jusqu'à 12 bits). Il faudrait aller plus loin. Pour cela, la méthode est connue et assez facile à mettre en œuvre : il faut calculer les productions des machines de Turing en ne se limitant pas à celle de 5 états. Il faudrait par exemple calculer toutes les productions des machines de Turing de 6 états, ou plus. C'est une question de puissance de calcul. Plus nous pourrons en disposer plus nous aurons une vision précise de cette complexité des petites séquences (de bits, mais aussi de symboles quelconques, car la méthode n'est pas limitée aux séquences de 0 et de 1).

Voici les 147 séquences finies de 0 et de 1 les plus fréquentes, classées à partir de la plus fréquente (bien sûr 0 est ex aequo avec 1, de même 1110, 1000, 0111 et 0001 (qui ont la même structure) sont ex aequo), etc.

 

 

D5 most frequent - copie

On trouvera des informations plus détaillées dans les articles suivants :


2 commentaires pour “La complexité des petits objets”

  1. Léo Gerville-Réache Répondre | Permalink

    Merci pour cet article très intéressant. En vous lisant, j'ai repensé au paradoxe de Penney sur la probabilité de premières apparitions d'une séquence définie, dans une suite aléatoire binaire. En prenant par exemple les 8 séquences possibles de 3 éléments et en calculant la probabilité que chacune d'elle sorte avant une autre choisie au hasard, on est en mesure de hiérarchiser les séquences selon cette probabilité. On obtient alors, en tenant compte de la symétrie des 1 et 0, l'ordre croissant (strict) suivant : 000 - 010 - 001 - 011...

    • Jean-Paul Delahaye Répondre | Permalink

      Le paradoxe de Penney ( voir http://www.lifl.fr/~delahaye/pls/213.pdf ) permet certaines comparaisons entre suites finies de 0 et de 1. La relation créée n'est cependant pas une relation d'ordre (c'est justement le paradoxe, car on s'attend à une relation d'ordre), cela contrairement au classement par les machines de Turing. Je ne pense pas que les deux choses soient vraiment liées (sinon on pourrait calculer assez rapidement le classement par complexité croissante).

Publier un commentaire