Complexité de Kolmogorov et de profondeur logique de Bennett

 

Complexité de Kolmogorov
et de profondeur logique de Bennett

 
Laboratoire d'Informatique Fondamentale de Lille UMR CNRS 8022

 

Les notions de complexité, d'organisation et d'information, sont omniprésentes dans de très nombreux domaines, notamment en biologie où les deux premières sont d'usage ancien. Elles ont la propriété commune d'être mal définies, et leur emploi, en général assez flou, est pourtant indispensable.

Ces notions n'ont vraiment commencé à être comprises en mathématiques que dans le cours du vingtième siècle. En particulier, les tentatives de mathématisation de l'opposition intuitive entre le simple et le complexe n'ont réellement abouti que depuis quelques années grâce à la théorie algorithmique de l'information de Gregory Chaitin et Andreï Kolmogorov, théorie elle-même fondée sur les progrès de la théorie de la calculabilité de Alonzo Church, Kurt Gödel et Alan Turing.

Cette théorie définit la complexité d'un objet, préalablement numérisé sous la forme d'une suite finie de '0' et de '1', par la taille du plus court programme qui permet d'engendrer cet objet. Cette théorie, qui complète et précise celle de Claude Shannon, prend en compte et mesure toutes sortes de redondances et de régularités dans les objets auxquels on l'applique. Les régularités de type statistique aussi bien que les régularités de type arithmétique, algébrique ou combinatoire sont concernées et entrent dans le champ de la théorie. L'utilisation des algorithmes de compression sans pertes permet l'application de cette théorie et conduit en particulier à de nouvelles méthodes de classification.

Ces avancées ont conduit Charles Bennett à donner un sens rigoureux à la distinction naturelle entre complexité aléatoire et complexité organisée, qui jusque-là échappait à la formalisation. La notion qu'il introduit -le concept de profondeur logique- vient compléter et enrichir la théorie et résoudre plusieurs questions délicates. Ce nouveau concept est sans doute promis à jouer un rôle important dans de nombreuses disciplines.

 

Plus de détails ? Voir le livre Complexité aléatoire et complexité organisée