Complexité de Kolmogorov (Complexité Algorithmique)

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.