La longueur (en bits) de la plus courte description effective ou du plus court programme qui, exécuté sur une machine de Turing universelle fixée, produit une chaîne finie donnée, considérée à une constante additive près dépendant du choix de la machine universelle.

Principe

Prendre la longueur minimale d'une description sur une machine de référence universelle comme mesure objective de l'information algorithmique et de l'aléa d'un objet fini individuel.

Démonstration

Pour la suite binaire S = '0101010101', un petit programme qui produit le motif répétitif a une faible complexité de Kolmogorov, tandis que pour une suite R issue de lancers de pièce sans motif court, tout programme produisant R a une longueur voisine de celle de R ; de plus la complexité de Kolmogorov n'est généralement pas calculable, si bien que l'on ne peut fournir que des bornes supérieures effectives en exhibant des programmes.

Mauvaise application

Considérer la complexité de Kolmogorov comme une quantité calculable pour des chaînes arbitraires, ou l'identifier directement à l'entropie de Shannon d'une distribution sans tenir compte que la complexité de Kolmogorov est une propriété d'objets individuels et ne dépend que d'une constante additive du choix de la machine universelle.

Conséquence

Une utilisation correcte classe les chaînes (à une constante près) par leur compressibilité, formalise la notion d'aléa pour des objets individuels, et met en évidence les limites de la compression algorithmique ainsi que l'existence de chaînes incompressibles.

Inversion

En inversant la perspective et en recherchant la longueur de description maximale plutôt que minimale, on met l'accent sur l'incompressibilité : la plupart des chaînes d'une longueur donnée ont une complexité de Kolmogorov proche de cette longueur, de sorte que l'énoncé inversé souligne la typicalité plutôt que la compressibilité.

Limite

La définition s'applique aux chaînes finies par rapport à une machine de Turing universelle fixée ; elle n'est définie qu'à une constante additive, n'est pas calculable en général et ne quantifie pas directement l'information en moyenne ou au sens distributionnel sans modèle probabiliste additionnel.

Tension sémantique

Il y a tension entre la complexité de Kolmogorov (propriété d'objets uniques, non calculable, dépendante de la machine à une constante près) et l'entropie de Shannon (mesure statistique calculable d'une variable aléatoire) : elles coïncident parfois dans des limites stochastiques mais remplissent des rôles distincts.

Synthèse

La complexité de Kolmogorov réunit la longueur de description algorithmique et une notion formelle d'aléa en prenant la taille du plus court programme sur une machine universelle fixée comme mesure canonique de l'information d'une chaîne finie individuelle, tout en reconnaissant la dépendance à la machine et l'incomplétude calculatoire.