Pour une chaîne binaire finie, la complexité de Kolmogorov est la longueur (en bits) du plus court programme sur une machine de Turing universelle fixée qui produit cette chaîne puis s'arrête ; elle formalise la compressibilité algorithmique.

Principe

La complexité dépend de la machine à une constante additive près (théorème d'invariance) et est généralement non calculable ; les chaînes qui n'admettent pas de description plus courte qu'elles-mêmes sont considérées comme aléatoires au sens algorithmique.

Démonstration

Une chaîne composée de 10 000 répétitions de '01' a une faible complexité de Kolmogorov car un court programme peut générer le motif, tandis qu'une chaîne de 10 000 tirages indépendants aura probablement une complexité proche de 10 000.

Mauvaise application

Considérer la complexité de Kolmogorov comme une mesure calculable pour la compression pratique ou la confondre directement avec l'entropie de Shannon d'une source sans tenir compte de la dépendance au modèle et à la machine.

Conséquence

Fournit une notion rigoureuse d'aléa et une borne inférieure absolue sur la compression sans perte pour des objets individuels ; sous-tend la théorie de l'information algorithmique et les limites de l'inférence par descriptions finies.

Inversion

Reformuler l'incertitude en termes probabilistes (information de Shannon) donne des mesures calculables en moyenne dérivées de distributions plutôt que la mesure de Kolmogorov, non calculable et centrée sur l'instance individuelle.

Limite

S'applique aux objets discrets finis par rapport à une machine universelle choisie ; elle n'est pas calculable en général, dépend des conventions d'encodage de programmes à une constante additive près, et des variantes (complexité préfixe, monotone) ajustent les détails techniques.

Tension sémantique

Souvent confondue avec les ratios de compression pratiques ou avec le taux d'entropie d'une source stochastique ; la tension porte sur l'irréductibilité algorithmique centrée sur l'instance versus les mesures moyennes d'information d'ensemble.

Synthèse

La complexité de Kolmogorov quantifie la longueur de la plus courte description algorithmique d'un objet individuel relative à un modèle de calcul universel, formalisant la compressibilité et l'aléa algorithmique malgré son caractère non calculable.