Le plus petit entier positif non définissable en moins de quinze mots.
Cette phrase a l’air inoffensive. Elle contient pourtant de quoi ruiner l’un des plus beaux rêves de l’informatique théorique : celui d’un algorithme capable de faire de la science à notre place.
Le français compte un nombre fini de mots. Il n’existe donc qu’un nombre fini de phrases de moins de quinze mots, et seulement un nombre fini d’entiers que ces phrases permettent de définir (« douze », « le carré de mille », « le nombre de secondes dans un siècle »…). Les entiers, eux, sont en nombre infini : certains échappent forcément à toute définition aussi courte. Et parmi ceux-là, il y en a un plus petit que tous les autres.
Appelons-le $n$. C’est, par construction, le plus petit entier positif non définissable en moins de quinze mots. Sauf que cette expression en italique compte douze mots… et qu’elle définit $n$. L’entier $n$ est donc à la fois définissable et non définissable en moins de quinze mots.
Bertrand Russell publie ce paradoxe au début du XXe siècle, en l’attribuant à G. G. Berry, bibliothécaire à Oxford.
Où est l’entourloupe ? Dans le mot « définissable », qui ne veut rien dire tant qu’on n’a pas précisé dans quel langage et selon quelles règles. Le français est assez souple pour parler de lui-même, et c’est cette autoréférence qui fait tout dérailler, comme dans « cette phrase est fausse ».
On pourrait s’arrêter là et ranger Berry parmi les jeux de mots. Mais que se passe-t-il si on remplace le français par un langage qui ne laisse aucune place à l’ambiguïté ?
Remplaçons « phrase » par « programme » et « définir un entier » par « l’afficher ».
Complexité de Kolmogorov
La complexité de Kolmogorov $K(x)$ d’un objet $x$ (un entier, un texte, une image…) est la longueur du plus court programme qui affiche $x$ puis s’arrête.
$K(x)$ mesure la quantité d’information réellement contenue dans $x$, une fois toute redondance éliminée :
abababab... longue de deux millions de caractères s’obtient avec print("ab" * 10**6). Une vingtaine de caractères suffisent : sa complexité est minuscule.print("0110100..."). Sa complexité vaut à peu près sa longueur. On dit que la suite est incompressible, et c’est d’ailleurs une très bonne définition du mot « aléatoire ».Et le choix du langage ? Il compte peu. Traduire un programme Python en C ne coûte qu’un nombre fixe de caractères (la taille d’un interpréteur Python écrit en C), quel que soit $x$. D’un langage à l’autre, $K(x)$ ne change donc que d’une constante.
Supposons qu’on dispose d’une fonction Python K(n) qui calcule la complexité de n’importe quel entier. On peut alors écrire :
def berry():
n = 0
while K(n) <= 1000000000:
n += 1
return n
print(berry())
Ce programme passe les entiers en revue jusqu’à trouver le premier dont la complexité dépasse le milliard. Il finit forcément par en trouver un, puisqu’il n’existe qu’un nombre fini de programmes d’au plus un milliard de caractères, donc qu’un nombre fini d’entiers de complexité aussi basse.
Appelons $n$ l’entier affiché. Par construction, $K(n)$ dépasse le milliard. Mais regardons la taille du programme qui vient de l’afficher : ces quelques lignes, plus le code de la fonction K. Quelques milliers de caractères, quelques millions peut-être, en tout cas bien moins qu’un milliard1. Donc $K(n)$ est inférieure au milliard. Contradiction.
Notre programme n’est rien d’autre que la phrase de Berry, « le plus petit entier non affichable par un programme d’au plus un milliard de caractères », écrite en bien moins d’un milliard de caractères. Sauf que cette fois, il n’y a plus d’ambiguïté derrière laquelle se réfugier. Une seule hypothèse a été faite, et c’est elle qui doit tomber :
La complexité de Kolmogorov n’est pas calculable : aucun programme ne peut, pour tout $x$, renvoyer $K(x)$.
On peut toujours majorer $K(x)$ : il suffit d’exhiber un programme qui affiche $x$, et c’est ce que fait un logiciel de compression. Mais on ne peut jamais certifier qu’il n’en existe pas de plus court. L’idée naïve, essayer un par un tous les programmes plus courts, échoue : certains ne s’arrêtent jamais, et rien ne permet de savoir lesquels à l’avance. C’est le problème de l’arrêt de Turing, et la même mécanique d’autoréférence que dans les théorèmes d’incomplétude de Gödel.
Au tournant des années 1960, Ray Solomonoff, l’un des participants de la conférence de Dartmouth qui a fondé l’intelligence artificielle, poursuit une idée folle : mécaniser l’induction. Autrement dit, automatiser ce que fait un scientifique quand il observe des données, devine la loi qui les produit et prédit la suite.
Sa recette marie deux principes :
Reste à dire ce que « simple » veut dire, et c’est là le trait de génie. Pour Solomonoff, une hypothèse est un programme qui engendre les données, et sa simplicité est sa longueur. Un programme de $\ell$ bits reçoit le poids a priori $2^{-\ell}$ : chaque bit supplémentaire divise sa plausibilité par deux. C’est la probabilité de tomber exactement sur ce programme en tirant ses bits à pile ou face.
La probabilité a priori d’observer une suite $x$ est alors la somme des poids de tous les programmes $p$ dont la sortie commence par $x$ :
$$M(x)=\sum_{p \text{ affiche } x\ldots} 2^{-\ell(p)}$$
où $\ell(p)$ désigne la longueur en bits du programme $p$. Pour prédire le bit suivant, il suffit de comparer $M(x0)$ et $M(x1)$.
En 1978, Solomonoff démontre que cette méthode est d’une efficacité stupéfiante. Si les données sont produites par n’importe quel mécanisme calculable, ses prédictions convergent vers les bonnes, et le cumul de ses erreurs est borné par une quantité proportionnelle à la complexité de Kolmogorov de ce mécanisme. En clair : plus la loi cachée est simple, plus vite elle est apprise, et aucune loi calculable n’échappe à la méthode. Un seul algorithme pour toute la science.
Sauf que $M$ n’est pas calculable. La somme est dominée par les programmes les plus courts, si bien que $M(x)$ est de l’ordre de $2^{-K(x)}$, et pour la calculer il faudrait savoir quels programmes affichent $x$, donc en particulier lesquels s’arrêtent. Le paradoxe de Berry, qui avait l’air d’un simple jeu de mots, se dresse en travers du chemin et tue dans l’œuf le rêve du jeune Ray Solomonoff : son super algorithme existe bel et bien sur le papier, mais aucun ordinateur ne pourra jamais l’exécuter 😢
Tout n’est pas perdu pour autant. L’idée survit sous des formes approchées et calculables : le principe de longueur de description minimale en statistique, les estimations de complexité par compression et, plus largement, l’intuition très présente en apprentissage automatique qu’apprendre, c’est compresser.
La chaîne Up and Atom raconte toute cette histoire (en anglais) :
Et si le code de K dépassait le milliard de caractères, il suffirait de relever le seuil : chaque chiffre qu’on lui ajoute le multiplie par dix en n’allongeant le programme que d’un caractère. Le seuil finit donc toujours par dépasser la taille du programme. ↩︎