Pangrammes autodescriptifs
Ce titre contient quatre 'a', un 'b', cinq 'c', cinq 'd', dix-neuf 'e', deux 'f', un 'g', deux 'h',treize 'i', un 'j', un 'k', un 'l', un 'm', seize 'n', trois 'o', quatre 'p', sept 'q', sept 'r', sept 's', quinze 't', dix-huit 'u', un 'v', un 'w', six 'x', un 'y' et quatre 'z'.
Comptez les lettres dans la phrase suivante : "Cinq c, cinq i, cinq n, cinq q..".
Vous constatez que "ça tombe juste", c'est à dire qu'il y a bien 5 "c", 5 "i", etc. On appelle ce genre de phrases un peu particulières des "phrases autodescriptives". La question que je pose ici est : peut-on créer des phrases autodescriptives qui contiennent toutes les lettres de l'alphabet, c'est à dire qui soient aussi des pangrammes, comme "Portez ce vieux whisky au juge blond qui fume" ? La réponse est oui !
Considérez la phrase suivante : « Cette phrase autodescriptive contient exactement dix a, un b, huit c, dix d, trente-trois e, un f, cinq g, six h, vingt-sept i, un j, un k, deux l, deux m, vingt-cinq n, dix o, huit p, six q, treize r, quinze s, trente-deux t, vingt-deux u, six v, un w, quatorze x, un y, quatre z, six traits d'union, une apostrophe, trente virgules, soixante-huit espaces, et un point. » qui est due à Gilles Esposito-Farèse.
Je précise que bien sur elle est « juste », c’est à dire que bien sûr elle comporte dix a, un b, etc. Il est bien évident que cette phrase remarquable n’est pas sortie de la cuisse de Jupiter. Elle a été composée, à partir du squelette suivant :
« Cette phrase autodescriptive contient exactement…a,…b,…c,…d, …e,…f,…g,…h,…i,…j,…k,…l,…m,…n,…o,…p,…q,…r,…s,…t,…u,…v,…w,…x,…y,…z,… traits d'union, une apostrophe, …virgules, … espaces, et un point. »
Notons que l’apostrophe n’apparaît que dans «
trait d’union » et dans aucun nombre écrit en
français, de sorte que l’on sait d’avance
qu’il n’y en a qu’une, de même pour
l’unique point final.
Le problème consiste donc à remplacer les points de
suspension … par des nombres écrits en français.
On appelle ce genre de « phrase réflexive » des pangrammes antodescriptifs. Chercher de tels pangrammes est un sport pas très répandu (!), mais qui a ses aficionados.
Imaginions que vous soumettiez ce problème à une intelligence artificielle véritable, comme cele que je décris dans mon livre "L'esprit et la machine". Alors, comment notre IA s’y prendrait-elle pour résoudre ce problème en cinq dixièmes de seconde ? Ecoutons ce que pense notre IA :
Premier dixième de seconde :
Humm, voyons voir. Il suffit de compter les lettres et d’écrire les nombres correspondants en bon français bien de chez nous. J’aurais préféré en binaire, mais bon…Donc je pars du « squelette », et si je compte le nombre de ‘a’ il y en a six, un seul ‘b’, bon, six ‘c’, trois ‘d’, treize ‘e’… Ah mais ça ne colle pas, il y a un ‘e’ dans ‘treize’, donc en fait il y en a quatorze, ouf, il y a aussi un seul ‘e’ dans quatorze, oui mais il y a un ‘a’, donc il y en fait sept ‘a’, ah mais ça fait un ‘e’ de plus, flûte ! Je n’y arriverai jamais ! Chaque changement semble détruire ce qui était correct auparavant !
Deuxième dixième de seconde :
Bon, et bien il n’y a qu’à explorer une à une toutes les possibilités, en essayant toutes les combinaisons possibles de 26 lettres. Oui… Ça pourrait marcher mais le nombre de combinaison est trop grand. Même si on se limite à un maximum d’une vingtaine d’apparitions pour la même lettre dans la phrase, ce qui semble raisonnable, il y a 26 puissance 20 combinaisons possibles… Ça prendrait des milliards d’années à tester, hum… a peu près dix puissance 19 milliards d’années, en testant un milliard de combinaisons par secondes, ce qui est déjà au delà du raisonnable… Flûte !
Troisième dixième de seconde :
Voyons voir si on peut réduire cet espace : en français il y a des lettres qui n’apparaissent dans aucun nombre. C'est le cas des cinq lettres suivantes : 'b', 'j', 'k', 'w' et 'y'. Nous pouvons y ajouter les lettres 'l' et 'm' qui n'apparaissent que dans "mille", "million" et "milliard", que l'on a peu de chances de rencontrer comme nombre de caractères figurant dans une phrase normale. Cela fait donc 19 lettres que l'on peut rencontrer dans la partie mobile d'une telle phrase. Ce serait la taille du nombre de tirages qu'il faudrait faire pour définir une phrase, mais en réalité nous pouvons diminuer ce nombre d'une unité. En effet, les lettres 'g' et 'v' n'apparaissent que dans le nombre "vingt". Elles sont toujours ensemble, donc le nombre de 'g' et de 'v' qui apparaissent dans les nombres sont toujours les mêmes. Il suffit alors de considérer que nous avons dix-huit nombres à déterminer. Ça laisse donc 18 puissance 20 combinaisons, ça ne prendra plus que quatre cent milliards d’années pour les tester toutes… bof, bof bof. Il faut trouver autre chose !
Quatrième dixième de seconde :
Revoyons le problème. Ce qui ne va pas, c’est que pour chaque lettre de ‘a’ à ‘z’, le nombre d’occurrence réel dans la phrase (celui que je peux compter) est très souvent différent du nombre « affiché » dans la phrase. Si la phrase contient le terme « quatre ‘a’ » et qu’en réalité, en comptant, il y en a dix, on dira que pour la lettre ‘a’ le nombre affiché est 4 et le nombre réel est 10. Le problème est donc de trouver une séquence d’opérations qui réduisent les différences entre ces nombres réels et affichés, et ce pour chaque lettre. La difficulté du problème vient de ce si l’on remplace le nombre affiché par le nombre réel, on a toutes les chances de modifier les différences pour les autres lettres. Par exemple si je remplace « quatre » par « dix », je change les différences pour les lettres q,u,a,t,r,e,d,i, et x !
Il n’empêche que cette opération « remplacer le nombre affiché par le nombre réel » est intéressante : si je fais cela simultanément pour toutes les lettres, puis que je recommence, on a des chances de tomber sur une solution... Ou pas ?
Cinquième dixième de seconde :
Je vais donc partir du squelette, je vais mettre un chiffre au hasard entre zéro et vingt pour chaque lettre, puis je vais répéter indéfiniment la séquence suivante : « vérifier si l’on tient une solution, et si non remplacer pour toutes les lettres le nombre affiché par le nombre réel » C’est toujours mieux qu’une recherche au hasard : si l’espace du problème possède des « attracteurs » (ce qui n’est pas sûr, mais bon), on pourra converger rapidement vers une solution avec cette méthode. Le risque, par contre, c’est de boucler : il se peut que pour certains squelettes, on retombe au bout d’un certain nombre de transformations sur une phrase que l’on avait déjà vue. Il faudrait donc mémoriser toutes les phrases intermédiaires. Mais ça risque de demander pas mal de mémoire et surtout de temps pour faire toutes ces vérifications ; donc pour l’instant je ne le fais pas, et je lance l’algorithme pour dix mille itérations max….Allez, GO ! …
Victoire ! Au bout de 3900 essais seulement, j’ai trouvé !
On voit que pour trouver la solution, il a fallu faire preuve d’invention et de créativité. Les deux étapes cruciales sont l’invention de l’opération de remplacement, et l’idée d’itérer (répéter) cette opération. Pour la petite histoire, cet algorithme est du à Raphaël Robinson et Douglas Hosftadter (décrite dans son merveilleux livre "Gödel, Escher, Bach : les Brins d'une Guirlande Eternelle"). Jacques Pitrat en a proposé une amélioration, qui est plus compliquée mais plus efficace, et surtout plus générale car elle trouve des solutions que la méthode d’Hofstadter ne voit pas dans certains cas. (téléchargez le fichier .doc ici)
Je ne m’étendrai pas plus sur le sujet. Si ce genre de perle vous passionne, en voici un, du même auteur, qui aurait sûrement plus à Georges Perec : il ne comporte aucun ‘e’ !
« Trois a, un b, trois plus un c, trois plus un d, un f, cinq g, trois plus un h, vingt-six i, un j, un k, huit l, trois m, vingt-trois n, dix o, huit plus un p, trois plus un q, huit plus un r, vingt-trois moins un s, dix plus six t, vingt-cinq u, cinq v, un w, six x, un y, un z, mais pas d' ... »
Ah vraiment, c’est une merveille !
Nous allons quitter maintenant notre tour d’horizon de l’IA classique pour faire un peu de prospective. Car il y a deux questions, sous-tendues depuis le début par les sujets abordés dans ce livre, et qui méritent une réponse : Est-il vraiment possible d’arriver à créer une intelligence artificielle vraie (IAV), c’est à dire une intelligence au moins aussi générale que l’intelligence humaine, et si oui, que peux-t-on en attendre ?
La réponse dans mon livre "L'esprit et la machine",d'où ce texte a été extrait !
A voir aussi :
- Mes pages "maths"
- Un programme autoréplicateur
- L'émergence des structures et la création de l'univers
Partagez / votez pour cette page :
Jeu de briques
Snake
Pacman
Bubble