INFORMATION THÉORIE DE L'

Quand on parle d'information, on pense souvent « information ayant une certaine valeur », ou « information pouvant servir à... ». Existe-t-il une théorie générale de l'information ? La théorie de l'information de Shannon (1949) a souvent été présentée comme cette théorie attendue. On admet aujourd'hui que les résultats qui en ont été tirés en biologie ou en informatique ne sont pas à la mesure des ambitions annoncées. Une seconde théorie de l'information, dite théorie algorithmique de l'information et due indépendamment à Andreï Kolmogorov et Gregory Chaitin (1965), se fonde sur la théorie du calcul d'Alan Turing (1936). Nous allons voir que ces deux théories sont liées l'une à l'autre.

Les exemples suivants de suites de caractères contenant de l'information doivent faire réfléchir : (a) la suite des caractères du texte du roman Les Misérables de Victor Hugo ; (b) la liste des emplacements des lance-missiles américains ; (c) une table de logarithmes ; (d) le génome complet d'un virus ; (e) un disque compact avec les concertos pour piano de Chopin ; (f) le programme du traitement de texte utilisé par l'auteur pour écrire cet article, tel qu'il est dans la mémoire de son ordinateur ; (g) le programme de ce même traitement de texte avant qu'il n'ait été compilé, qu'on appelle « programme source ».

Dans chaque cas, il s'agit d'objets possédant un contenu en information et ayant une certaine valeur : ils ont pu être vendus et achetés, on a dépensé de l'argent pour les produire, on continue d'en dépenser pour les conserver. Le contenu brut d'information pour chacun de ces objets est donné par le nombre de bits (éléments de mémoire binaire, 0 ou 1) nécessaires pour enregistrer la chaîne de caractères dans la mémoire d'un ordinateur quand on ne lui fait subir aucun traitement particulier. Le contenu brut d'information d'une chaîne de caractères s de longueur n est n si s ne comporte que des 0 et des 1 et c'est n log m /log 2 si la chaîne comporte des caractères pris parmi m. Dans nos exemples, l'objet ayant le contenu brut d'information le plus grand est le disque compact. Celui ayant le plus de valeur marchande est le programme non compilé de traitement de texte. Celui ayant le moins de valeur aujourd'hui est sans doute la table de logarithmes.

Bien sûr, le contenu brut d'information ne détermine pas la valeur de l'information. La valeur de l'information d'une chaîne de caractères est relative à un certain but et à une certaine situation. Nous noterons Val(s, B) la valeur de l'information contenue dans s relativement au but B. Nous allons découvrir qu'en précisant le but B on obtient différentes théories, dont la théorie de l'information de Shannon et la théorie algorithmique de l'information.

Théorie algorithmique de l'information

Si l'on se fixe pour but de compresser la chaîne de caractères s et si l'on suppose qu'on dispose pour cela d'une machine M, alors la valeur de l'information de s est la longueur du plus petit programme (écrit en binaire) qui, lorsqu'il fonctionne dans M, reconstitue la chaîne s.

La puissance des machines n'est pas sans limite. Dès qu'on a affaire à des machines d'une certaine puissance, leur puissance théorique est la même. C'est là la découverte fondamentale de Turing en 1936 : il y a des mécanismes universels de calcul et n'importe quel ordinateur contemporain est un tel mécanisme universel. Si l'on se donne un mécanisme universel de calcul, la notion de plus petit programme engendrant s ne dépend pas de la machine utilisée, ou plus précisément, ne dépend de cette machine que par une constante additive qu'on peut négliger en première approximation si on traite des[...]