Dans la vie j'aime écrire. Et j'aime les maths. Bon, ça dépend quels domaines en particuliers (détails à venir).
Les maths sont pleines de choses bizarres. Vraiment bizarres. Donc marrantes. Intrigantes. Stupéfiantes. Renversantes. Bouleversifiant...
CN : tiens, Gudule, voilà les clés du placard. On a besoin de Charlot. Remets-lui de l'huile s'il en a besoin. Et vérifie que Zorlax est bien enfermé.
Gudule part vers le fond de la pièce en ronchonnant, tandis que CN se penche sur l'annuaire des vendeurs de tomates en Nouvelle-Calédonie.
Zorlax : libérez-mouaaaaaa !
Gudule : silence !
Un inconcevable tintamarre émane du fond de la pièce. CN lève un œil distrait du bottin, pour apercevoir Gudule aux prises avec une betterave.
Celle-ci parvient à vaincre le larbin et se dresse de toute sa hauteur (environ 20 centimètres) en clamant fièrement :
Rodolphe-Albert : je suis le maître du mooooonde !
CN : saperlipopette, encore un autre légume qui parle.
Rodolphe-Albert : je suis une betterave !
Gudule : et moi un rutabaga, mais j'ai acquis de nombreuses formes, misérable avorton.
Rodolphe-Albert : et je parle !
CN : mouais.
Rodolphe-Albert : je suis le maître du moooooon...
Tout à coup, Charlot lui roule dessus sans faire exprès. Gudule regarde Rodolphe-Albert incrusté entre les lames du parquet ; on jurerait que la betterave essaie encore d'articuler :
Rodolphe-Albert : je suis le maîiiiitre du mooooooonde.
La complexité de Kolmogorov, c'est typiquement ce dont j'ai envie de parler dans PJAM. J'aime ça, il y a des machines de Turing, et je ne suis pas certain que ça ait un intérêt (hors informatique théorique, bien sûr).
Il a été vu précédemment dans ces pages qu'en informatique, on disposait de tout un tas d'outils et de concepts théoriques pour caractériser la complexité d'un algorithme. Mais la complexité n'est pas l'apanage des algorithmes. Prenons des objets du quotidien, par exemple des suites infinies d'entiers.
Gudule : mouais.
Voici différentes suites d'entiers :
111111111111111111111111111...
42424242424242424242424242...
123456789101112131415161718...
3141592653589793238462643383279...
235711131719232931374143475359616771...
457681957231246761237216756124157...
Votre intuition dit que la première est très simple. Que la deuxième l'est aussi. On répète de nombreuses fois 42, qui comme chacun le sait, est le nombre de minutes que dure un aller simple de Paris à New York à travers un tunnel creusé de façon rectiligne dans un globe terrestre homogène, placé sous vide, et où vous vous déplacez à la seule force de la gravitation (vous tombez, quoi).
Gudule : calcul fait en cours de physique, il y a très, très longtemps.
La troisième est simple aussi, pas vrai ? La quatrième ? N'en parlons pas : ce sont les décimales de pi. La cinquième ? Je ne le mentionne même pas. Mais la dernière est juste, moche.
Et justement, que dit votre intuition quand vous êtes face à quelque chose de moche ? D'aléatoire ? De random ?
Gudule : mon intuition est que ça vient de CN.
Votre intuition est que ce n'est pas une machine de Turing, ou un humain (qui n'est peut-être qu'une très grosse machine de Turing), qui vous a écrit ce truc. Ou mieux encore : que le seul moyen d'écrire ce truc, c'est de dire à la machine de l'écrire, point barre.
Donc voici la définition de la complexité de Kolmogorov d'une chaîne de caractères (un texte) :
Définition (Gudule) : La longueur du plus petit programme qui permet d'écrire ce texte.
C'est une belle notion, intuitive, et justement comme nous avons un formalisme mathématique de ce qu'est un « programme », a.k.a les machines de Turing, nous pouvons remplacer « programme » par « machine de Turing » dans la définition, et tout est bien qui finit bien.
Gudule : sauf que ce n'est pas calculable.
Alors, en effet, il n'existe pas de programme pour calculer la complexité de Kolmogorov (vous qui avez lu et survécu au problème de l'arrêt, vous imaginez la teneur de la preuve par contradiction qu'on peut faire). Autrement dit, ce n'est qu'une notion théorique.
Gudule : mais ça ne dérange pas CN.
On peut lui trouver différentes applications. Celle que je trouve la plus amusante est une notion spécifique d' « aléatoire » : une suite de 0 et de 1 aléatoire sera plus courte que n'importe quel programme / machine de Turing permettant de l'écrire.
Pour ça il faut encore spécifier une machine universelle, autrement dit un ordinateur : une machine de Turing capable d'émuler n'importe quelle machine de Turing. Ça existe. Fin.
Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.
La complexité de Kolmogorov se situe un peu dans le prolongement de la théorie de l'information.
En théorie de l'information, vous souhaitez quantifier la quantité d'information qui circule sur un canal de communication. L'idée est que par exemple, compresser une chaîne de caractères de la forme :
aaaaaaaaaaaaaaaaaaaaa... splart. (cri de la betterave qui tombe)
sera facile, tandis que :
sdqlkhclkxwbwxjnwdglkjwfd. (cri de la tête de Gudule heurtant mon clavier)
sera difficile.
Vous modélisez alors ce canal de communication par une source qui produit des lettres avec certaines probabilités, et le calcul de l'entropie de Shannon vous donne la solution (sous réserve de cette modélisation), notamment le maximum de compression possible.
J'aime la théorie de la complexité (de Kolmogorov), et la théorie de l'information.
