Nous expliquons les bases de la théorie de la complexité de Kolmogorov ou théorie algorithmique de l'information. On analyse en particulier les différences et les ressemblances entre la complexité de Kolmogorov et sa variante dite complexité préfixe. Ensuite, nous introduisons une définition d'un mot aléatoire (finie ou infinie), celle de Per Martin-Löf et montrons qu'elle est équivalente à la notion d'incompressibilité définie via la complexité de Kolmogorov.
Le contenu de ce rapport de recherche
Ce rapport de recherche est en fait la première partie de ma thèse — écrit quelques mois avant que je ne sois appelé de façon irrévocable sous les drapeaux, ce qui a un peu cassé le rythme —, et a été écrit afin de fixer les bases de la complexité de Kolmogorov. Il a également servi de support à un cours en création à l'École normale supérieure de Lyon. Il a été recompilé pour fournir un PDF qui s'imprime et se lit correctement (des différences de mise en page existent donc avec l'original).
La complexité de Kolmogorov est une idée importante introduite par Andreï Kolmogorov qui essaye de formaliser l'idée qui est derrière la « complexité intrinsèque d'une chaîne de caractères ». Il paraît naturel qu'une répétition de 100 fois la lettre A est plus simple qu'une suite de 100 lettres plus ou moins au hasard. Certains essais ont été fait dès le début du XXe siècle pour définir cette notion, mais aucune (jusqu'à Kolmogorov) n'a résisté de façon suffisamment solides aux transformations diverses qu'on s'attend à pouvoir faire dans le cadre d'une telle théorie.
La définition de base est qu'étant donné deux mots x et y et une machine de Turing \(\psi\), la complexité conditionnelle de x sachant y est définie par \(\mathbf{KS}_\psi(x|y)=\min\{l(p),\psi\langle p,y\rangle=x\}\). Le plus important théorème est celui de Solomonoff-Kolmogorov :
Une machine additivement optimale \(\psi\) est une machine telle que la complexité de n'importe quel objet avec cette machine est aussi bonne que la complexité avec n'importe quelle autre machine, à une constante additive près : \(\forall\psi'\in C,\exists c_{{\psi'}},\forall x,y,\mathbf{KS}_\psi(x|y)\leqslant\mathbf{KS}_{{\psi'}}(x|y)+c_{{\psi'}}\). Dans tout système acceptable de programmation, il existe une telle machine \(\psi\).
On retiendra que la complexité de Kolmogorov définit assez bien l'idée d'aléatoire, puisqu'il peut être démontré qu'un chaîne c-aléatoire is équivalente à être une chaîne c-compressible (c-compressible signifie que la complexité de Kolmogorov est plus petite que la longueur d'origine d'au moins c).
Le second théorème très important est que \(\mathbf{KS}_{\psi}(x|y)\) est une fonction non-calculable, ce qui signifie qu'il n'est pas possible d'avoir un programme (au sens de Turing) de compression sans perte parfait. Pour être complet, je me dois de mentionner que Gregory Chaitin (aux États-Unis) a eu les mêmes idées à peu près au même moment (et je sais, par expérience personnelle, que les deux écoles de pensées se sont affrontées souterrainement pendant des décennies).
Comme vous pouvez le déduire de ce résumé très rapide, toutes ces notions doivent être parfaitement définies, et je donne des preuves simples des bases de la théorie de l'information algorithmique.
Les documents
Citer ce document
@TechReport{dubacq98,
author = {Jean-Christophe Dubacq},
title = {Introduction \`{a} la th{\'e}orie algorithmique de l'information},
institution = {\'Ecole normale sup\'erieure de {L}yon},
year = {1998},
type = {Rapport de recherche / Research Report},
number = {05},
month = may
}