Complexité de Kolmogorov

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.

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.