2. La complexité algorithmique
Les difficultés mathématiques rencontrées sont peut-être liées aux résultats logiques d'incomplétude (démontrés par Gödel en 1930) et dont la compréhension n'a cessé de s'approfondir, en particulier grâce à la théorie de la complexité d'Andreï Kolmogorov (1903-1987), formulée simultanément en 1965 par Kolmogorov et Gregory Chaitin. Cette théorie dite de la complexité algorithmique développe mathématiquement l'idée qu'est complexe ce qui ne peut pas s'exprimer brièvement. Plus précisément, la complexité de Kolmogorov K(s) de la suite de caractères s est la taille du plus petit programme P qui engendre s. Cette théorie a connu des développements remarquables, conduisant en particulier à l'élucidation du problème de la définition mathématique des suites aléatoires, posé au début du xxe siècle. Cette solution formalise l'idée qu'est aléatoire ce qui est incompressible, c'est-à-dire ce qui ne peut se définir par une séquence de caractères plus courte que l'objet lui-même (une suite répétant mille fois les caractères 01 n'est pas aléatoire car on peut la définir par une séquence de caractères de longueur bien plus petite qu'elle-même, la séquence « mille fois 01 »). Un autre résultat de cette théorie est la découverte de la famille des nombres oméga de Chaitin. Ces nombres de complexité maximale concentrent en eux des propriétés étonnantes : ils sont transcendants, aléatoires et non calculables.
Autre succès de la théorie de la complexité de Kolmogorov : elle a établi des liens profonds avec la physique et pourrait bien être une clé de la thermodynamique statistique, comme Charles Bennett et Wojciech Zurek l'ont suggéré. Non seulement la compréhension du problème du coût énergétique minimum du calcul et des calculs réversibles s'appuie sur la théorie algorithmique de l'information, mais celle-ci joue un rôle clé dans une révolution dont tout laisse prévoir qu'elle occupera une place considérable dans l'avenir : l'introduction de la mécanique quantique e […]
… pour nos abonnés, l'article se prolonge sur 2 pages…
