La Complexité de Kolmogorov (2)

Cette complexité de Kolmogorov a un impact certain au niveau de la compression. Effectivement, suivant une description, on peut réduire de manière significative les informations.

La complexité d'une chaine n'est pas calculable, on l'a vu. Mais on peut calculer une valeur approchée supérieure de la complexité de cette chaine : il suffit de compresser la chaine suivant un algorithme, de coder la fonction de décompression, et de concatener la chaine de bits correspondant à cette fonction au reste de la chaine, et la longueur totale est notre valeur approchée.
 
Donc, on dit qu'une chaine s est compressible par n si K(s) <= | s | - n, sinon on dit qu'elle est incompressible par n. Une chaine incompressible par 1 est une chaine incompressible (tout court).

On dit qu'une chaine est complexe quand sa valeur de complexité n'est pas de beaucoup inférieure à sa valeur. Les chaines complexes ne sont donc pas compressibles en général, ce qui explique pourquoi il n'existe toujours pas d'algorithme de compression qui s'applique uniformément à toutes les chaines et qui compresse sans pertes.

On sait qu'une chaine est complexe si elle ne peut pas etre décrite d'une manière significativement compressée. Mais, il se trouve qu'on ne peut pas prouver qu'une chaine est complexe au dela d'une certaine longueur de chaine. C'est le théorème de l'incompletude de Chaitin-Kolmogorov :

Il existe une constante C (qui ne dépend que du langage de description choisi) telle qu'il n'existe pas de chaine s pour laquelle on peut prouver que K(s) >= C