Logique et ensemblesNotion · Glossaire
complexité de Kolmogorov
Pour une machine universelle U fixée, la complexité de Kolmogorov d'un objet fini est la longueur du plus court programme qui s'arrête après l'avoir produit exactement. Pour une tolérance c ≥ 0 annoncée, on dit qu'un objet x est incompressible à c bits, ou aléatoire au sens de Kolmogorov pour cette convention, lorsque K_U(x) ≥ |x| − c : aucun programme ne le produit avec plus de c bits d'économie par rapport à sa longueur.
Sommaire
Ce que vous allez apprendre
- Relier la longueur du programme minimal à la compressibilité d'une chaîne.
- Suivre l'exemple exact d'une chaîne alternée de 32 bits.
- Distinguer une borne obtenue par compression de la complexité minimale exacte.
- Identifier la dépendance à la machine et l'incalculabilité générale.
En clair
Regardez une suite de 32 zéros et uns. Si elle alterne toujours 0 et 1, une courte consigne suffit : « écrire 01 seize fois ». Pour une suite sans motif repérable, il faut parfois presque tout recopier.
La complexité de Kolmogorov mesure cette brièveté de description, mais avec des programmes plutôt qu'avec des phrases. Plus le plus court programme producteur est bref, plus l'objet est compressible.
Définition
On fixe d'abord une machine de Turing universelle, notée U, qui sert de langage de programmation de référence. Pour une chaîne finie x, sa complexité de Kolmogorov relativement à U est la longueur, en bits, du plus court programme p qui fait s'arrêter U après avoir produit exactement x. Cette définition s'écrit : .
Le choix de U compte pour les petites valeurs. Toutefois, deux machines universelles fixées donnent des complexités qui diffèrent au plus d'une constante indépendante de x : un interpréteur de taille fixe traduit les programmes de l'une vers l'autre. La mesure est donc stable à une constante additive près, et non absolument identique dans tous les systèmes de représentation.
Une chaîne est dite incompressible, ou aléatoire au sens de Kolmogorov au niveau choisi, lorsqu'aucun programme sensiblement plus court qu'elle ne la produit. La définition s'applique aussi à d'autres objets finis dès qu'un codage effectif est fixé. Elle fonde la théorie algorithmique de l'information, apparue dans les années 1960 à travers des travaux indépendants.
Un exemple, pas à pas
Considérons la chaîne x formée en répétant seize fois le bloc 01. Les données sont : un bloc de 2 bits, 16 répétitions et une longueur totale de 32 bits.
1. Écrire le bloc 01 seize fois produit x = 01010101010101010101010101010101.
2. Compter les symboles donne 2 × 16 = 32 bits. La figure matérialise les seize blocs et la consigne qui les engendre.
3. Un programme peut encoder la consigne « répéter 16 fois 01 ». Sa longueur fournit une borne supérieure pour la complexité de x sur la machine choisie.
4. Cette description ne prouve pas qu'elle est la plus courte. Affirmer la valeur exacte demanderait d'exclure tous les programmes plus brefs, ce qu'aucune recherche générale ne sait faire.
Le contrôle est refaisable : regroupez la chaîne par paires et comptez seize occurrences de 01. L'exemple établit une compression possible, pas la complexité minimale exacte.
En pratique
Pour comparer des descriptions de données, on cherche un programme court qui reproduit exactement l'objet. Un motif comme seize répétitions de 01 invite à employer une boucle plutôt qu'une copie littérale.
Pour étudier une suite qui semble aléatoire, on tente d'y trouver une règle génératrice. Avec une machine U et une tolérance c fixées, si cette règle s'encode en un programme de longueur strictement inférieure à celle de la suite moins c, la suite n'est pas incompressible à c bits ; l'absence de motif visible ne constitue toutefois pas une preuve.
Pour compresser effectivement un fichier, on utilise un algorithme de compression calculable. La complexité de Kolmogorov sert plutôt de limite théorique, car sa valeur exacte n'est pas calculable en général.
À ne pas confondre
Complexité algorithmique d'un calcul. Elle mesure des ressources comme le temps ou la mémoire nécessaires à une procédure. La complexité de Kolmogorov mesure la taille d'un programme producteur : deux programmes aussi courts peuvent avoir des durées d'exécution très différentes.
Entropie de Shannon. Elle caractérise une source probabiliste ou une distribution et une longueur moyenne de codage. La complexité de Kolmogorov porte sur un objet individuel : une seule chaîne de 32 bits peut être examinée sans modèle probabiliste.
Taux obtenu par un compresseur. Un logiciel particulier donne une description calculable, donc une borne supérieure. S'il ne raccourcit pas un fichier, cela ne prouve pas que le fichier possède une complexité de Kolmogorov élevée.
Limites et pièges
Machine non précisée. Pour un objet court, la constante liée au langage de référence peut dominer le résultat. Il faut fixer la machine universelle ou raisonner seulement à une constante additive près.
Programme trouvé, minimum supposé. Une description courte prouve uniquement une borne supérieure. Pour la chaîne alternée de 32 bits, la boucle montre qu'une compression est possible, sans certifier le plus court programme.
Calcul exact attendu. Il n'existe pas d'algorithme qui calcule la complexité de Kolmogorov de toute chaîne. On emploie donc des bornes, des arguments théoriques ou des compresseurs, en indiquant clairement ce qui a réellement été établi.
Aléatoire pris au sens absolu. On fixe une machine universelle U et une tolérance c ≥ 0 : une chaîne x est dite incompressible à c bits lorsque K_U(x) ≥ |x| − c. La qualification dépend donc de cette convention, qui doit être annoncée.
Pour aller plus loin
La machine de Turing précise le modèle de calcul sur lequel sont définis les programmes et leur exécution.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres