Mesure de l'information algorithmique d'un objet fini, définie comme la longueur de la plus courte description (programme plus entrée) sur une machine universelle de description donnée qui produit l'objet.

Principe

La complexité d'une chaîne finie individuelle est la longueur minimale, à une constante additive près dépendant de la machine universelle choisie, d'un programme qui affiche cette chaîne et s'arrête.

Démonstration

Une chaîne binaire périodique telle que '010101...0101' présente une faible complexité de Kolmogorov car un court programme peut générer la répétition, tandis qu'une longue chaîne obtenue par lancers de pièces équitables a typiquement une complexité proche du maximum.

Mauvaise application

Considérer la quantité comme calculable pour des entrées arbitraires, ou comparer des valeurs brutes entre différentes machines universelles non précisées sans tenir compte des constantes additives, conduit à des conclusions invalides.

Conséquence

Fournit une base formelle pour l'aléa individuel, les bornes inférieures de non-compressibilité et les limites théoriques de la compression algorithmique et de l'inférence.

Inversion

Passer à des mesures basées sur des ensembles (comme l'incertitude moyenne d'une distribution) inverse l'objectif : de la minimalité descriptive d'un objet unique vers l'incertitude statistique au travers d'échantillons.

Limite

Définie pour des objets discrets finis par rapport à un choix de méthode de description universelle ; elle n'est pas calculable en général et dépend d'une invariance à une constante additive dépendante de la machine.

Tension sémantique

Se distingue de l'information au sens de Shannon qui quantifie l'incertitude moyenne d'une source stochastique ; la complexité de Kolmogorov mesure la longueur descriptive d'un individu indépendamment des ensembles probabilistes.

Synthèse

La complexité de Kolmogorov formalise la longueur de description effective la plus courte d'un objet concret relative à un schéma de description universel, fondant l'aléa algorithmique et la compressibilité comme propriétés d'instances individuelles.