deftab709
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'.

This title containsthree a's, one b, two c's,
 two d's, thirty-three e's, five f's, two g's,
 nine h's, eleven i's, one j, one k, three l's,
 one m, twenty-one n's, sixteen o's, one p,
 one q, nine r's, twenty-three s's, 
twenty-four t's, three u's, four v's, 
eight w's, two x's, five y's and one z.

Jacques Pitrat

Résumé : Ce rapportprésente un programme qui engendre des phrases indiquant le nombred'occurrences des caractères qu'elle contiennent. Après avoirdécrit le problème, nous détaillerons la méthode proposée, dérivée d'une méthodeproposée par D.Hofstadter. Nous donnerons les résultats obtenus etnous monterons que cette méthode s'inspire d'une méthode bien connueen IA, mais qu'elle est appliquée dans une situation où elle devrait échouer. Pourtant, elle obtientd'excellents résultats.
Mots-Clés : auto-référence,réflexivité.

Abstract: This report describes aprogram creating self-reflective sentences, which indicate the number ofoccurrences of their letters. After defining the problem, we present the method, derived from a method describedby D.Hofstadter. We analyze the results found by the system and we showthat this method can be considered as an application of the means-endsanalysis. Although it is used in a situation where it must fail, it has very good results.
Key-words: self-reference, reflexivity.

Rapport  LAFORIA 96/26. Septembre 1996. Université Pierre et MarieCurie.
Quelques modifications mineures ont étéapportées au rapport initial.

1. Introduction	1
1.1. Le problème	1
1.2. Difficulté du problème	1
1.2. Les caractéristiques du français	2
1.3. Les caractéristiques de l'anglais	4
2. Une méthode de résolution	5
2.1. La méthode d'Hofstadter	5
2.2. Une modification de la méthode	7
2.3. Comparaison des résultats des deux méthodes	8
2.4. Principe de la recherche de plusieurs phrases	9
2.5. Une petite cousine d'Epiménide	11
2.6. Une autre méthode de création des phrases réflexives	11
3. Les solutions multiples	12
3.1. Existence de plusieurs solutions pour le même corps	12
3.2. Le couple onze–douze	13
4. Les solutions	15
4.1 Fréquence des solutions	15
4.2 Influence des divers paramètres	16
4.2.1 Le nombre d'itérations	16
4.2.2 Le nombre de points de départ	18
4.2.3 La condition de test	18
4.3. Les meilleurs choix de paramètres	19
5. Réflexion sur le means-ends	20
6. Conclusion	22
Références	24
Annexe 1 
Glossaire	25
Annexe 2 
Le programme	27
Annexe 3 
Une phrase avec de nombreuses solutions	34

1. Introduction
1.1. Le problème
Le but est de réaliser une phrase quidécrive son contenu. Si elle n'en décrit qu'une faible partie, celaest assez facile par exemple :
Cette phrase contient exactementcinq 'n' et trois 'o'.
Les difficultés commencent quand ladescription du contenu est plus complète. Nous étudions dans cerapport la réalisation de phrases qui décrivent le nombre desoccurrences dans ces mêmes phrases des vingt-six lettres de l'alphabet. Le titre de ce rapport est un exemple d'une telle phrase. Il est possible d'avoir des variantesde ce type de phrases. Par exemple, elles pourraient aussi indiquer lenombre de blancs, le nombre de signes de ponctuation, le nombre de traitsd'union ou même le nombre total de leurs lettres. Les méthodes utilisées dans tous ces cassont les mêmes, mais certains d'entre eux peuvent conduire à desproblèmes plus difficiles à résoudre.
Pour être précis, nousdéfinirons plusieurs termes, qui sont rappelés dans l'annexe 1. Unephrase qui décrit son contenu est dite "correcte" quand tous les nombresde caractères qu'elle déclare sontégaux aux nombres de ces caractères qu'elle contient effectivement.Nous appelons "corps" d'une telle phrase l'ensemble des caractères qui yfigurent, que l'on veut compter et qui ne sont pas dans les nombresassociés aux caractères. Si l'on ne s'intéresse qu'aux vingt-six lettres de l'alphabet, lecorps du titre est :
cetitrecontientabcdefghijklmnopqrstuvwxyetz
La partie "nombre" est formée descaractères que l'on veut compter et qui appartiennent aux nombresliés aux caractères que l'on compte. Pour le titre, elle contient lescaractères suivants :
quatreuncinqcinqdixneufdeuxundeuxtreizeununununseizetroisquatreseptseptseptquinzedixhuitununsixunquatre
1.2. Difficulté duproblème
Trouver de telles phrases est unproblème très difficile si l'on n'utilise pas d'ordinateur. Mêmela vérification de la correction d'une solution prend du temps et l'ons'y trompe souvent.
Il est facile de voir que cette phrase contient six 'a', un 'b', sept 'c',quatre 'd', dix-huit 'e', quatre 'f', cinq 'g', cinq 'h', vingt-deux 'i', un 'j', un 'k', trois 'l', un 'm', vingt et un 'n', cinq 'o', quatre 'p', huit 'q', neuf 'r', huit 's', vingt et un 't', vingt 'u', six 'v', un 'w', six 'x', un 'y' et pour finir un'z'.
Cette phrase est à la fois correcte etfausse. Les nombres de lettres qu'elle indique sont exacts, mais il n'estcertainement pas facile de faire une telle vérification.
La découverte d'une telle phrase estencore bien plus difficile que sa vérification. Supposons par exempleque la phrase énonce qu'il y a sept 'p' alors qu'il y en a enréalité huit. Si nous changeons le "sept" lié à 'p' en "huit", nous allonsperturber le nombre de 'h', de 'u', de 'i', de 's', de 'e' et de 'p'. Lenombre de 't' est le seul à rester inchangé. De plus nous n'avons pasrésolu le problème pour les 'p' : il y en avait huit et nous indiquions sept. Maintenant,nous avons enlevé un 'p' en remplaçant "sept" par "huit". Nonseulement nous avons modifié les nombres de 'e', 'h', 'i', 's', 'u',mais nous n'avons pas résolu le problème des 'p' ; nous avons seulement inversé l'erreur, car la phraseénonce qu'il y a huit 'p' alors qu'il n'y en a plus que sept.
Nous sommes dans un univers très cahotique oùle moindre changement a de nombreuses répercussions en détruisant cequi était correct auparavant. Il n'est pas facile a priori de penserà une méthode qui ait des chances de réussir. On peut essayersystématiquement tous les ensembles possibles de 26 lettres ; onvérifie ensuite pour chacun s'il a conduit à une phrase qui décrit correctement son contenu. Elle est impraticable pour des raisons detemps ordinateur, le nombre de situations à envisager étant beaucouptrop grand.

Il existe des cas où ce problème n'a pas desolution pour un corps donné. Prenons le cas extrême où l'ons'intéresse aux occurrences d'une seule lettre et considérons laphrase :
Cette courte phrase contient entout six 'e'.
Elle est incorrecte puisqu'elle contient sept'e'. Changeons alors le "six" en "sept" :
Cette courte phrase contient entout sept 'e'.
Cela ne va toujours pas puisqu'il y en amaintenant huit. Changeons le "sept" en "huit" :
Cette courte phrase contient entout huit 'e'.
Et nous revenons à sept 'e'. Nous voyonsfacilement qu'il ne peut y avoir de solution ; si l'on met "neuf", on auraseulement huit 'e'.
Aussi, il n'est pas évident qu'ilexiste au moins une phrase décrivant correctement les nombres de toutesles lettres qu'elle contient.
1.2. Lescaractéristiques du français
La difficulté du problème dépendde la langue où on le pose. En français, certaines lettres n'interviennent pas dans la combinatoire, parcequ'elles n'apparaissent dans aucun nombre. C'est le cas des cinq lettressuivantes : 'b', 'j', 'k', 'w' et 'y'. Nous pouvons y ajouter les lettres 'l' et 'm' quin'apparaissent que dans "mille", "million" et "milliard", que l'on a peu dechances de rencontrer comme nombre de caractères figurant dans une phrase normale. Cela fait donc 19 lettres que l'onpeut rencontrer dans la partie mobile d'une telle phrase. Ce serait lataille du nombre de tirages qu'il faudrait faire pour définir unephrase, 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 toujoursensemble, donc le nombre de 'g' et de 'v' qui apparaissent dans les nombressont toujours les mêmes. Il suffit alors de considérer que nous avons dix-huit nombres àdéterminer. Nous l'appelerons "degré déterminant le problème",car si l'on connaît en français le corps de la phrase et la valeur deces 18 nombres, on peut vérifier si la phrase correspondante est correcte.

La partie "fixe" d'une phrase est formée du corpset des caractères des nombres liés aux caractères quin'apparaissent dans aucun nombre. En effet, ces nombres ne changent jamaisquand on remplace un nombre lié à un caractère par un autre. Pour le titre, la partie fixe est :
Cetitrecontientaunbcdefghiunjunkunlunmnopqrstuvunwxunyetz
La partie "mobile" d'une phrase estformée des caractères des nombres qui sont liés aux caractèrespouvant figurer dans des nombres. Notons qu'en français, le nombreassocié au 'g' et celui associé au 'v' figurent tous deux dans la partie mobile. En effet, ils peuventtous les deux changer, bien que ces changements soient liés. Toujourspour le titre, elle est formée des caractères suivants :
quatrecinqcinqdixneufdeuxundeuxtreizeseizetroisquatreseptseptseptquinzedixhuitunsixquatre

Comme dans toutes les langues, changer un nombre enson successeur ou son prédécesseur peut avoir des conséquences sur de nombreux autres nombres. Par exemple, remplacer "deux" par"trois" va augmenter ou diminuer d'une unité les nombres liés à 9lettres : 'd', 'e', 'i', 'o', 'r', 's', 't', 'u' et 'x'. La moitié des18 nombres qui définissent une solution est touchée. Remarquons que, dans le cas dutitre, la partie fixe est de taille inférieure à la partie mobile.C'est la majeure partie d'une phrase qui change quand on remplace desnombres par d'autres nombres.

Le problème des signes diacritiques, comme lesaccents ou la cédille, se pose en français. Doit -on considérercomme une seule lettre les caractères 'e', 'é', 'è', 'ê','ë' ou comme cinq lettres différences ? En réalité, que l'on prenne l'une ou l'autre solution n'apas grande importance et ne change pas le degré déterminant leproblème. Considérer comme distinctes des lettres avec un signediacritique différent ne fait qu'alourdir la partie fixe de la phrase avec des nombres quine changeront jamais. En effet, il se trouve qu'aucun nombre ne contient enfrançais de signes diacritiques, à l'exception du "zéro", mais iln'intervient jamais : si l'on indique qu'il y a zéro fois tel caractère, du même coupce caractère apparaît une fois et le "zéro" disparaît !
Si nous considérons les variantes dont nous avonsparlé précédemment, ce degré peut être parfois augmenté.Il ne change pas si l'on considère les signes de ponctuation qui restentles mêmes si l'on change les nombres. Par contre, le nombre de traits d'union vaaugmenter d'une unité le degré déterminant le problème, carcertains nombres ont un trait d'union et d'autres pas. Il en est de même si l'on fait intervenir le nombre des blancs : des nombres comme"trente et un" ont deux blancs alors que la plupart des nombres n'en ontpas. Enfin, si l'on veut indiquer le nombre total de lettres, ce nombrechange évidemment souvent quand on modifie un nombre : les nombres decaractères des nombres inférieurs à 100 varient déjà de 2("un") à 19 ("quatre-vingt-quatorze"). Dans ces derniers cas, il fautajouter une unité à la valeur du degré de 18 que nous venons de voir pour chaque caractéristiquesupplémentaire que l'on introduit dans la phrase et qui dépend desnombres. Cela augmente ainsi la taille de l'espace de recherche.
1.3. Lescaractéristiques de l'anglais
La situation de l'anglais est un peu plussimple. En effet, les lettres 'c', 'j', 'k', 'p' et 'q' n'apparaissent dansaucun nombre. 'z' n'apparaît que dans "zero" qui ne peut figurer commenombre dans une phrase réflexive comme nous l'avons vu plus haut. 'b' et 'm' n'apparaissent que dans"billion" et "million" que l'on ne risque pas de trouver comme nombresd'occurrence d'un caractère dans une phrase. Il reste donc 18 lettres.Mais on a peu de chance de trouver des phrases qui contiennent au moins 100occurrences d'un certain caractère. Cela élimine alors deux lettressupplémentaires, 'a' et 'd' ; 'd' et, dans la plupart des cas, 'a' se trouvent dans les nombres entre100 et un million : "a hundred", "two hundred and one", "ten thousand", mais jamais avant100. Si l'on a donc des phrases "raisonnables", nous n'y trouverons que 16nombres susceptibles de varier ce qui réduit donc la combinatoire parrapport au cas du français. Le degré déterminant le problème pour l'anglais n'est que de16 pour des phrases normales.
Il est bien évidemment hors de question detraduire une phrase réflexive française directement en anglais ! Ilne faut surtout pas traduire «quatre 'a'» par «four 'a'». Jene suis pas très bon en anglais, mais j'ai réussi à traduire correctement le titrede ce rapport, ce que peu d'anglophones seraient capables de faire.
2. Une méthodede résolution
2.1. La méthoded'Hofstadter
Dans les chapitres 2, 3 et 16 de Metamagical Themas, Douglas Hofstadter a donné plusieurs exemples dephrase réflexive. Dans le chapitre 16, il propose une méthode pourcréer de telles phrases.
Nous dirons que, pour une lettre d'une phrase, lenombre "réel" est celui des occurrences de cette lettre dans la phraseet le nombre "affiché" est celui qui figure dans la phrase lié à cette lettre. Si la phrase contient «quatre 'a'» et s'il y aeffectivement 5 'a' dans cette phrase, le nombre affiché pour 'a' est 4et le nombre réel est 5.
Dans la méthode proposée par Hofstadter, oncommence par affecter au hasard des valeurs aux nombres liés aux 26lettres. Si, pour toutes les lettres, le nombre ainsi affiché correspondau nombre réel, on a trouvé une solution. Si ce n'est pas le cas, on remplace pour chaque lettre sonnombre affiché par son nombre réel qui devient ainsi le nouveaunombre affiché. On repart en vérifiant si l'on a bien obtenu lasolution et en remplaçant tous les nombres différents du nombre réel. Hofstadter espèreainsi tomber sur un point fixe qui est la solution. On appelle"itération" chacune de ces étapes où l'on remplace les valeursaffichées par les valeurs réelles.
Deux cas peuvent se produire : on arrive à unesolution ou l'on retrouve une situation déjà rencontrée auquel cason boucle. On peut détecter les bouclages en gardant les situationsdéjà rencontrées, mais cela fait beaucoup de situations. Il est plus simple de limiter lenombre d'itérations permises : si l'on dépasse cette limite, onarrête d'itérer. Pour augmenter les chances d'obtenir une solution, on peut refaire un tirage et recommencer lesitérations à partir de là. On appelle "point de départ" cetirage des valeurs initiales liées à tous les caractères. Làencore, il faut définir une limite pour le nombre de points de départ que l'on a le droitde considérer. Si on le dépasse, on arrête les essais pour lecorps proposé. Les nombres maximaux d'itérations et de points dedépart sont des paramètres importants pour le succès de la méthode.
Cette méthode a été programmée etappliquée aussi au français. Elle a trouvé une solution qui auraitété parfaite si celui qui a implémenté l'idée d'Hofstadter n'avait fait une erreur en croyant que "trois" s'écrivait"troix". Selon l'expression d'Hofstadter, il a malheureusement donné unesolution pour le "françaix" ! Cela a néanmoins montré que cetteméthode trouvait effectivement des solutions. A priori son succèsparaît surprenant, car elle bouleverses complétement la phrase ; lavaleur de la plupart des nombres appartenant à la partie mobile estmodifiée à chaque étape.

Cette méthode a un important avantage. Quand l'onarrive à une situation où l'ensemble des lettres des nombres réelsest la même que l'ensemble des lettres des nombres affichés, onarrive directement à la solution à l'étape suivante. S'il n'existe que de raressolutions, il existe par contre beaucoup plus de situations qui sont ainsià une étape de la solution. Prenons la phrase suivante :
Vous avez bien raison de comptertoutes les lettres de cette phrase avant de la croire quand elle vous affirme qu'elle contient seize 'a', deux 'b', huit 'c', huit'd', quarante-trois 'e', quatre 'f', cinq 'g', trois 'h', vingt-deux 'i',un 'j', un 'k', huit 'l', quatre 'm', vingt-quatre 'n', treize 'o', cinq'p', douze 'q', vingt et un 'r', quatorze 's', trente-trois 't', vingt-quatre 'u', neuf 'v', un 'w', cinq 'x',un 'y' et pour terminer six 'z'.
Cette phrase ne décrit absolument passon contenu. Les valeurs affichées sont différentes des valeursréelles pour dix de ces nombres. Ces différences sont en général de une en plus ou en moins, mais dans deux de ces cas elles sontégales à deux :
	lettre	valeur affichée	valeur réelle
	e	quarante-trois	quarante et un
	h	trois	cinq
	i	vingt-deux	vingt-trois
	n	vingt-quatre	vingt-trois
	o	treize	quatorze
	p	cinq	quatre
	r	vingt et un	vingt-deux
	s	quatorze	treize
	u	vingt-quatre	vingt-cinq
	x	cinq	quatre

Nous pouvons vérifier que l'ensemble des lettresdes valeurs affichées est exactement identique à celui des valeursréelles. Toutes deux ont un "quarante", quatre "vingt", un "et", un "quatorze", un "treize", deux "cinq", deux"quatre", deux "trois", un "deux" et un "un". Aussi la méthoded'Hofstadter conduit-elle directement à une solution en remplaçantles valeurs affichées par les valeurs réelles. Cela donne la phrase correcte suivante :
Vous avez bien raison de compter toutes les lettres de cette phrase avantde la croire quand elle vous affirme qu'elle contient seize 'a', deux 'b',huit 'c', huit 'd', quarante et un 'e', quatre 'f', cinq 'g', cinq 'h', vingt-trois 'i', un 'j', un 'k', huit 'l', quatre 'm', vingt-trois 'n',quatorze 'o', quatre 'p', douze 'q', vingt-deux 'r', treize 's',trente-trois 't', vingt-cinq 'u', neuf 'v', un 'w', quatre 'x', un 'y' etpour terminer six 'z'.
Bien que la différence entre la situationprécédente et le but était très importante, on obtient en uneseule étape la solution. Il existe beaucoup de situations de ce type, cequi augmente considérablement la chance de trouver les solutions bien qu'elles soient trèsrares dans un espace de recherche énorme.
Un autre avantage de la méthode est dedéterminer à la première étape toute lapartie fixe. En effet,les nombres associés aux caractères ne figurant pas dans les nombressont calculés exactement et mis à la place des nombres initiaux. Ils le resterontpendant toutes les étapes suivantes.
2.2. Une modification dela méthode
La méthode précédente conduiteffectivement à trouver des solutions. Il est pourtant possible del'améliorer, car chaque étape conduit à une modification considérable de la situation, la plupart des nombres étant modifiéssimultanément à chaque étape. J'ai programmé une variante decette méthode en ne changeant qu'un nombre à la fois. On prend unseul des nombres dont la valeur affichée est différente de la valeur réelle et on construit la phrase oùl'on remplace la valeur affichée de ce nombre par la valeur réelleque l'on a déterminé, sans changer les autres nombres. Cela demandedeux précautions.
La première précaution porte sur ladétermination du nombre pour lequel on va remplacer la valeuraffichée par la valeur réelle. Il faut prendre garde de ne pascommencer chaque fois au même endroit la recherche d'une lettre pour laquelle ces deux nombres sontdifférents : en opérant ainsi, on aurait souvent des bouclages.Supposons que l'on commence systématiquement par 'a' et que la valeuraffichée pour 'a' soit "cinq" alors que la valeur réelle serait "quatre". Onremplace donc "cinq" par "quatre", mais alors il y aura un 'a' de plus,donc la valeur réelle sera "cinq" juste au moment où la valeuraffichée est devenue "quatre". En recommençant au début, comme ces deuxvaleurs ne sont pas les mêmes, on remplace cette fois "quatre" par"cinq" et on est revenu à la situation initiale. Le programme remédieà cela en commençant la recherche d'un désaccord entre valeur affichée et valeurréelle pour une autre lettre que celle pour laquelle on a fait ledernier changement. Remarquons qu'après un premier parcours de l'ensemble des lettres, la valeur de la partiefixe de la phrase est correctement établie.
La deuxième précaution consiste à donnerà cette nouvelle méthode une qualité essentielle de laprécédente : quand l'ensemble des lettres des nombres réels estle même que l'ensemble des lettres des nombres affichés, on doit obtenir lasolution à l'étape suivante. Sans cela, on risque de passer àcôté d'une solution évidente. Aussi ajoute-t-on à la fin decertaines étapes cette vérification. On détermine l'ensemble des lettres des valeurs réelleset celui des lettres des valeurs affichées pour les cas où ces deuxvaleurs sont différentes. Si ces deux ensembles sont les mêmes,l'ensemble des valeurs réelles est une solution. Pour ne pas perdre du temps, on ne le fait que s'ily a des chances raisonnables de réussite. Les détails sur cettelimitation sont donnés à la section 4.2.3.
Remarquons que l'on a un bouclage si l'on retrouvele même ensemble de nombres et si l'on décide de changer lamême lettre que dans la situation précédente. Cela est uneimportant différence avec la méthode d'Hofstadter où il y a bouclage dès que la première de cesconditions est satisfaite. Cela conduit à 19 fois plus de situationsdifférentes puisqu'il y a 19 lettres qui sont susceptibles de changer enfrançais ; on a beaucoup moins de chances d'arriver à un bouclage.
2.3. Comparaison desrésultats des deux méthodes
Cette amélioration est effectivementrentable. Trois expériences donnent une idée de la valeur de cetteamélioration.

— 1. J'ai choisi un corps pour lequel lenombre de fois où l'on trouve une solution est anormalement élevé,quelle que soit la méthode utilisée. Dans les deux cas, on a pris10.000 points de départ et 10.000 itérations pour chaque point de départ. Il existe aumoins deux solutions :
Vous avez bien raison de compter les lettres de cette phrase bizarre avantde la croire quand elle vous affirme qu'elle contient onze 'a', trois 'b',sept 'c', huit 'd', trente-cinq 'e', cinq 'f', quatre 'g', sept 'h',vingt-sept 'i', un 'j', un 'k', huit'l', trois 'm', vingt et un 'n', douze 'o', huit 'p', six 'q', seize 'r',dix-sept 's', vingt-huit 't', dix-neuf 'u', huit 'v', un 'w', six 'x', un'y' et pour finir six 'z'.
et
Vous avez bien raison de compter les lettres de cette phrase bizarre avantde la croire quand elle vous affirme qu'elle contient douze 'a', trois 'b',six 'c', dix 'd', trente-trois 'e', quatre 'f', trois 'g', six 'h',vingt-sept 'i', un 'j', un 'k', huit'l', trois 'm', dix-sept 'n', quatorze 'o', huit 'p', six 'q', vingt 'r',dix-huit 's', trente 't', dix-sept 'u', sept 'v', un 'w', huit 'x', un 'y'et pour finir cinq 'z'.

Les résultats sont les suivants :

	méthode d'Hofstadter	méthode modifiée
nombred'obtentions	3008	6726
de la première phrase
nombre d'obtentions	0	2
de la deuxième phrase
tempsordinateur	900 minutes	237 minutes

Le temps ordinateur, sur une station de travail SunSparc 1+, est inférieur avec la modification pour deuxraisons. Les deux méthodes arrêtent immédiatement lesitérations en cas de succès, mais cela arrive plus souvent avec la deuxième. Par ailleurs, ladétermination des nombres de lettres se fait plus rapidement avec ladeuxième méthode puisqu'il y a moins de caractères modifiéschaque fois.

— 2. Les programmes ont engendré toutesles solutions qu'ils pouvaient dans les mêmes conditions : 2.000itérations, le nombre de point de départ étant normalement de1.000 et étant augmenté pour chaque découverte d'une nouvelle solution. Ils ont ététestés avec les mêmes 122 corps. La méthode proposée parHofstadter a eu un succès pour 4 de ces corps et n'a jamais eu desuccès multiple ce qui fait donc 4 solutions au total. La méthodeaméliorée a eu au moins un succès pour 60 de ces corps et a eu autotal 93 solutions différentes ; en effet, elle a trouvé souventplusieurs solutions différentes pour le même corps.

— 3 Après 40.000 points de départ et5.000 itérations pour chaque point de départ, la méthodeaméliorée avait trouvé dix solutions différentes pour le corpsdécrit dans l'annexe 3. Avec également 5.000 itérations pour chaque point de départ, la méthodeinitiale n'a trouvé aucune solution après 82.000 points de départpour ce même corps.

La méthode d'Hofstadter est une excellenteméthode qui donne effectivement des solutions au problème de larecherche de phrases réflexives. Mais elle ne les trouve que pour unefaible partie des corps proposés et, dans les expériences qui ont été faites, elle n'a pasréussi a engendré de solutions multiples pour le même corps.
Je pense qu'il y a deux raisons possibles pour cetteamélioration des performances avec la méthode modifiée. Lapremière est que les changements sont moins brutaux puisque l'on nechange qu'un nombre affiché à chaque fois. La deuxième est que l'on peut faire plus d'essais avant derencontrer un bouclage puisqu'il y a 19 fois plus de situationsdifférentes ; comme nous l'avons remarqué, deux situations ne sontles mêmes que si l'on décide aussi dans les deux cas de changer le nombre affecté à lamême lettre.
2.4. Principe de larecherche de plusieurs phrases
Il peut être intéressant dechercher successivement des phrases réflexives construites sur des corpsvariés pour avoir un nombre suffisant de succès pour essayer detrouver des phénomènes intéressants. Nous pouvons aussi avoir besoin d'avoir une phrase qui despropriétés particulières ; comme il n'y a pas toujours desolution, il est utile d'en prévoir quelques variantes. Comme il est souhaitable que toutes ces phrasesaient un sens, on introduit un générateur de corps. D'une part, ondéfinit un "noyau", suite de symboles qui sera commun à tous cescorps ; d'autre part, on définit N places où l'on pourra mettre à la ième de ces places un"ajout", suite de symboles prise parmi Ki possibilités. Cesajouts sont définis de telle façon qu'ils soient indépendants lesuns des autres.
Prenons pour exemple le noyau suivant, où, pouren faciliter la compréhension j'ai mis, ainsi que dans les ajouts, lesblancs et les symboles de ponctuation. Les places des ajouts sont indiquées par des majuscules entre parenthèses :
(A) vous avez (B) raison de compter (C) (D) (E) les lettres de cette (F1) phrase (F2) avant de la croirequand elle (G) affirme qu'elle contient (H) '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' et (I) 'z'.
Les ajouts sont les suivants :
A : "","cher lecteur", "ami lecteur", "chers lecteurs"
B : "", "bien", "parfaitement"
C : "", "et de recompter"
D : "", "soigneusement", "avec soin", "avec beaucoup de soin"
E : "", "toutes"
F : "", "longue","curieuse","bizarre"
G : "", "vous"
H : "", "exactement"
I : "finalement", "pour finir", "enfin", "pour terminer"

"" indique la suite de symboles vide. Les symboles de place n'apparaissentpas dans le programme que je donne en annexe 2, mais il serait facile d'entirer parti pour que l'ordinateur imprime directement les phrasessolutions. F est mis à deux emplacements car l'adjectif correspondant peut se mettre avant ouaprès le nom. Cela ne se produit pas dans cet exemple, mais il estpossible d'avoir un ajout, comme "ne pas", dont les parties se mettent àdeux endroits différents du corps.
Cet exemple permet d'engendrer 4X3X2X4X2X4X2X2X4 soit 12.288 corpsdifférents. On devrait en tirer au moins 8.000 phrasesréflexives.
2.5. Une petite cousined'Epiménide
Le crétois Epiménide est passéà la postérité avec sa phrase paradoxale sur les crétoismenteurs. Il est également possible de rencontrer des paradoxes dont les auteurs sont cettefois une phrase. Considérons la phrase  :
Cette curieuse phrase ment quandelle affirme qu'elle contient exactement neuf 'a', un 'b', douze 'c', cinq 'd', trente-deux'e', cinq 'f', cinq 'g', deux 'h', vingt 'i', un 'j', un 'k', cinq 'l',quatre 'm', vingt-sept 'n', cinq 'o', quatre 'p', quinze 'q', treize 'r',cinq 's', vingt-trois 't', vingt et un 'u', cinq 'v', un 'w', quatre 'x', un 'y' et pour finir quatre 'z'.
Le problème est que cette phrase nement pas, elle est correcte ; elle contient bien par exemple quinze 'q' etcinq 's'. Il faut donc la corriger, mais cela n'est pas si facile. Nous nepouvons pas nous contenter d'écrire :
Cette curieuse phrase ne ment pas quand elle affirme qu'elle contientexactement neuf 'a', un 'b', douze 'c', cinq 'd', trente-deux 'e', cinq'f', cinq 'g', deux 'h', vingt 'i', un 'j', un 'k', cinq 'l', quatre 'm',vingt-sept 'n', cinq 'o', quatre 'p', quinze 'q', treize 'r', cinq 's', vingt-trois 't', vingt et un 'u', cinq 'v',un 'w', quatre 'x', un 'y' et pour finir quatre 'z'.
En effet, elle n'est plus correcte : lenombre des 'e' n'est plus 32, mais 33 alors que celui des 's' est devenuégal à 6. De même, les nombres de 'n', 'p' et 'a' sont maintenant inexacts. Cette phrasene ment pas quand elle dit qu'elle ment et elle ment quand elle dit qu'ellene ment pas. Nous retrouvons un cycle analogue à celui d'Epiménidequi passe son temps à osciller entre le statut de menteur et celui d'homme digne de foi.Heureusement, tout s'arrange ici avec la phrase suivante :
Cette curieuse phrase ne ment pasquand elle affirme qu'elle contient exactement quatorze 'a', un 'b', dix 'c', quatre 'd', trente-quatre 'e', quatre 'f', cinq 'g', trois 'h', vingt etun 'i', un 'j', un 'k', cinq 'l', quatre 'm', vingt-quatre 'n', cinq 'o',quatre 'p', seize 'q', seize 'r', huit 's', vingt-six 't', vingt-deux 'u',cinq 'v', un 'w', cinq 'x', un'y' et pour finir quatre 'z'.
Tout est rentré dans l'ordre, lenombre des 'e' est bien égal à 34 tandis que celui des 'q' est devenuégal à 16 et celui des 's' égal à 8. Remarquons qu'il esttrès facile de créer une phrase qui ment quand elle dit qu'elle ment. Il suffit d'associeraux lettres des nombres choisis au hasard. Il y a bien peu de chance quel'on construise ainsi une phrase correcte.
2.6. Une autre méthodede création des phrases réflexives
Une autre méthode pour engendrer desphrases réflexives semble prometteuse. On crée une table de hash pourtoutes les situations rencontrées pour un certain corps ; cette tableest commune à tous les points de départ. Une situation est caractérisée par lesnombres de la partie mobile et par la lettre pour laquelle on a remplacéla valeur affichée par la valeur réelle. On poursuit lesitérations jusqu'à rencontrer soit un succès, soit une situation déjà trouvée.Dans ce dernier cas, on modifie un nombre lié à une lettre qui n'apas encore été remplacé par sa valeur réelle. Si l'on adéjà fait les changements pour toutes les lettres possibles, on choisit auhasard un nouveau point de départ. A chaque nouveau point de départ,on commence par appliquer une fois la méthode initiale d'Hofstadter defaçon à déterminer immédiatement la partie fixe.
La limite sur le nombre d'itérations disparaîtainsi que celle sur le nombre de points de départ. Elles serontremplacées par une limite sur le nombre de situations différentesconsidérées. Par contre il est toujours nécessaire de regarder dans certains cassi l'ensemble des lettres des nombres réels est le même quel'ensemble des lettres des nombres affichés.
Cette amélioration élimine la perte de temps due aux bouclages quipeuvent se produire avant que l'on coupe par le nombre d'itérations.Elle permet également de ne pas refaire les mêmes essais avec despoints de départ différents. Mais il faut bien gérer la mise en mémoire des situations déjà rencontrées qui sont en très grand nombre. Elle n'a pas été implémentée.
3. Les solutionsmultiples
3.1. Existence deplusieurs solutions pour le même corps
Il se peut que le même corps donnenaissance à plusieurs solutions. Cela est particulièrement facilequand on s'intéresse aux occurrences d'un seul caractère. Si l'on aune phrase correcte qui indique qu'il y a N occurrences d'un caractère et si lesnombres N, N+1, …N+p contiennent respectivement q, q+1, …q+poccurrences de ce même caractère, nous aurons p+1 solutions correctesen remplaçant N par un des p nombres suivants. Par exemple, cela se produit pour la lettre 'e' avec N valant 28, q valant 0 et pvalant 3 puisque les nombres "vingt-huit", "vingt-neuf", "trente" et"trente et un" contiennent respectivement 0, 1, 2 et 3 fois le caractère 'e'. Si une phrase correcte indique seulement son nombre de 'e' et si cenombre 28, cette phrase est également correcte pour les trois valeurssuivantes ce qui donne quatre solutions.

Pour le cas de deux caractères, nous avions vu dans l'introduction laphrase :
Cette phrase contient exactementcinq 'n' et trois 'o'.
Il existe d'autres solutions sur le mêmecorps, par exemple :
Cette phrase contient exactementquatre 'n' et trois 'o'.
Cette phrase contient exactement cinq 'n' et deux 'o'.
Cette phrase contient exactement quatre 'n' et deux 'o'.
Il est facile de créer de tels groupesde phrases parce qu'il y a seulement deux lettres et que les nombresassociés à une lettre sont indépendants de l'autre lettre. En effet, "cinq" et "quatre" ne contiennent pasde 'o' et que "trois" et "deux" ne contiennent pas de 'n'. De plus lenombre le plus élevé ("cinq" et "trois") contient la lettre àlaquelle il est lié alors que le nombre inférieur ("quatre" et "deux") ne la contient pas.

Les heuristiques qui nous ont permis de créer lesphrases précédentes ne sont valables que si l'on s'intéresse aunombre d'occurrences d'un petit nombre de lettres. Aussi n'est-il pas évident qu'il existe plusieurs solutions pour le même corps quand onindique les nombres d'occurrences des vingt-six lettres de l'alphabet. Ilest surprenant de voir que c'est très fréquent. Nous avons donnédeux phrases réflexives dans la section 2.5. Chacune d'entre elles a d'autres variantes ;celle qui dit qu'elle ment a au moins cinq autres solutions sur le mêmecorps, l'une d'entre elles étant :
Cette curieuse phrase ment quand elle affirme qu'elle contient exactementdix 'a', un 'b', six 'c', six 'd', trente 'e', sept 'f', quatre 'g', trois'h', dix-huit 'i', un 'j', un 'k', cinq 'l', quatre 'm', vingt 'n', six'o', quatre 'p', neuf 'q', quatorze 'r', neuf 's', vingt-trois 't', vingt-deux 'u', quatre 'v', un 'w', neuf'x', un 'y' et pour finir deux 'z'.
alors que la phrase qui dit qu'elle ne mentpas a au moins une autre solution :
Cette curieuse phrase ne ment pasquand elle affirme qu'elle contient exactement huit 'a', un 'b', sept 'c', six 'd', vingt-neuf 'e', six'f', six 'g', trois 'h', vingt et un 'i', un 'j', un 'k', cinq 'l', quatre'm', vingt-quatre 'n', cinq 'o', six 'p', sept 'q', neuf 'r', douze 's',vingt-deux 't', vingt et un 'u',six 'v', un 'w', dix 'x', un 'y' et pour finir deux 'z'.
Il peut y avoir de fortes différencespour certaines lettres entre deux solutions basées sur le même corps.Par exemple, dans les deux phrases qui ne mentent pas, le nombre des 'q'est de 7 dans un cas et de 16 dans l'autre. De même, le nombre de 'r' est de 9 pour l'uneet de 16 pour l'autre.
Le record actuel est donné en annexe 3, avec aumoins dix solutions pour le même corps. Le corps de la phrase donnéeà la fin de la section 2.1. conduit à au moins huit solutions.
3.2. Le couple onze–douze
Des opérateurs permettent danscertains cas de trouver directement une solution à partir d'une solutiondéjà connue. Dans le cas du français, le cas le plus fréquentest lié à la ressemblance existant entre les deux nombres consécutifs "onze" et"douze".
Les deux nombres "onze" et "douze" ont trois lettresen commun : 'e', 'o' et 'z'. La lettre 'n' apparaît dans "onze" et pasdans "douze" ; les lettres 'd' et 'u' apparaissent dans "douze" et pas dans "onze". Sinous avons donc une solution avec douze 'd', N 'u' et N-1 'n', nous auronsaussi une solution où tous les nombres associés aux 23 autres lettresseront les mêmes, mais où l'on associera "onze" à 'd', N-1 à 'u' et N à 'n'. En effet,puisqu'il y aura "onze" à la place de "douze", il y aura bien un 'd' etun 'u' moins et un 'n' de plus. Remarquons que ceci est aussi valable enchangeant les rôles de 'd' et de 'u', mais il est plus fréquent d'avoir douze 'd' quedouze 'u', lettre très fréquente car elle apparaît dans plusieursnombres. L'opérateur fonctionne aussi en sens inverse dans le cas où l'on a onze 'u', N-1 'd' et N 'n'. C'est ainsi que la phrase :
Cher lecteur, vous avez bien raison de compter avecbeaucoup de soin les lettres de cette phrase bizarre avant de la croire quand elle affirme qu'elle contient exactement dix-sept'a', quatre 'b', douze 'c', onze 'd', quarante-huit 'e', sept 'f', cinq'g', sept 'h', vingt-deux 'i', un 'j', un 'k', neuf 'l', quatre 'm',vingt-sept 'n', douze 'o', huit 'p', neuf 'q', quinze 'r', douze 's', vingt-huit 't', vingt-six 'u', neuf 'v', un 'w',cinq 'x', un 'y' et enfin huit 'z'.
satisfait aux conditions de l'opérateurappliqué à l'envers avec N valant 27. Nous avons bien 11 'd, 27 'n'et N-1=26 fois la lettre 'u' ; nous créons donc immédiatement uneautre solution :
Cher lecteur, vous avez bien raison de compter avec beaucoup de soin leslettres de cette phrase bizarre avant de la croire quand elle affirmequ'elle contient exactement dix-sept 'a', quatre 'b', douze 'c', douze 'd',quarante-huit 'e', sept 'f', cinq 'g', sept 'h', vingt-deux 'i', un 'j', un 'k', neuf 'l', quatre 'm', vingt-six'n', douze 'o', huit 'p', neuf 'q', quinze 'r', douze 's', vingt-huit 't',vingt-sept 'u', neuf 'v', un 'w', cinq 'x', un 'y' et enfin huit 'z'.

Le couple "onze–douze" correspond àl'opérateur qui s'applique le plus souvent. Il en existe bien d'autres,mais il sont bien moins souvent appliquables. Par exemple, un autreopérateur est issu du couple "six–sept" ;.le premier nombre a 'i' et 'x' en plus et 'e', 'p' et 't'en moins. Si donc nous avons sept 'p', alpha-M 't', bêta-N 'e', N-1 'x'et gamma-(M-1) 'i', nous avons une autre solution avec six 'p', alpha-(M-1)'t', bêta-(N-1) 'e', N 'x' et gamma-M 'i'. Dans «alpha-M 't'», alphareprésente le nombre des dizaines, comme "trente" ou "quarante" et Mcelui des unités. Cela permet d'associer des nombres qui ont des valeurstrès différentes, comme ceux des 'x' et des 'e'. Il était également possibled'avoir de telles variantes pour le couple précédent, mais lesnombres de 'n' et de 'u' sont en général proches. Cette nouvellerègle s'applique si l'on a :
	lettre	solution connue	nouvelle solution
	'e'	quarante-cinq	quarante-quatre
	'i'	vingt-deux	vingt-trois
	'p'	sept	six
	't'	trente-trois	trente-deux
	'x'	quatre	cinq
Alpha vaut "trente", bêta "quarante",gamma "vingt", M "trois" et N cinq" Je n'ai donné qu'une varianteliée à ce couple, mais on peut permuter les rôles des lettres.L'opérateur s'applique aussi dans l'autre sens. On peut créer d'autresopérateurs à partir du même couple en associant les lettres defaçon différente ; dans l'opérateur précédent, on aassocié "sept" à 'p', 'e' à 'x' et 'i' à 't'. On aurait pu aussi associer "sept" à 'e' sous laforme "delta-sept" (comme "quarante-sept"), 'i' à 't' et 'p' à 'x'.L'application de chacun des opérateurs lié à ce couple demande lavérification de cinq conditions, ce qui fait qu'ils sont d'un usage moinsfréquent que ceux lié au couple précédent. Il existe d'autrescouples, mais ils exigent souvent encore plus de conditions ; on a donctrès peu de chance de pouvoir les appliquer.
L'anglais n'a pas de couples de nombresvoisins en valeur et en symboles qui soient aussi proches que le coupleonze–douze pour le français.
Bien que l'on rencontre assez souvent des couples desolutions qui correspondent au couple onze–douze, la plupart dessolutions multiples ne sont toutefois pas dues à l'application d'unopérateur issu de ce couple. Par exemple, aucune des dix solutions donnéesdans l'annexe 3 ne rentre dans ce cadre.
4. Les solutions
4.1 Fréquence dessolutions
Quand on part d'un point de départ, onpeut soit arriver à une solution, soit boucler indéfiniment. Cettedernière situation est la plus fréquente, d'une part parce qu'il y ades corps pour lesquels il n'existe aucune solution et d'autre part parce que mêmes'il existe une solution il arrive très souvent qu'un point de départconduise à un bouclage. La situation du corps examiné dans lapremière expérience de la section 2.3 où il y avait un succès pour environ deuxpoints de départ sur trois est exceptionnelle. Même quand il existeau moins une solution, il est déjà rare de la trouver pour un pourcent des points de départ. Dans l'exemple donné en annexe 3, une des phrases a ététrouvée une seule fois sur 100.000 points de départ.
Il arrive que l'on ne trouve pas de solution parceque l'on n'a pas poussé assez loin les itérations. Il arriveeffectivement que l'on obtienne une solution après plus de 10.000 itérations. Dans la plupart des cas on les trouve pourtant avant 5.000itérations et très souvent avant 2.000. Le temps ordinateur est àpeu près proportionnel au nombre d'itérations alors que laprobabilité de trouver une solution diminue très vite quand le nombred'itérations déjà effectué est élevé. Il seraitintéressant de détecter les bouclages, mais ce serait coûteux entemps, car ils ont souvent de très grandes périodes. Par ailleurs, quand une solution demande beaucoup d'itérationspour un point de départ, elle peut en demander bien moins pour d'autrespoints de départ. Il vaut donc mieux augmenter le nombre de points dedépart et diminuer celui du nombre d'itérations.

Sur un essai fait avec 3573 corps différents avecun nombre d'itérations de 2.000, on a trouvé au moins une solution pour 1528 corps, soit 43%. Dans cette recherche, pour engendrer le maximum dephrases avec des solutions multiples pour le même corps, le nombre depoints de départ était variable selon le nombre de solutionsrencontrées. Il était de 1.000 au départ ; il passait à 2.500 quand on avaittrouvé une solution, à 10.000 pour deux solutions, à 20.000 pourtrois solutions, à 30.000 pour quatre solutions, à 40.000 pour cinqsolutions, à 50.000 pour six solutions et à 100.000 au delà. On a manquéprobablement peu de solutions multiples, mais certainement beaucoup desolutions simples, 1.000 points de départ étant une valeur faible, beaucoup de solutions n'apparaissant pas une foissur mille, surtout quand on ne fait que 2.000 itérations. Avec un autreessai portant sur seulement 122 corps mais avec un nombre de points dedépart de 10.000, on est arrivé à plus de 60% de corps ayant au moins une solution. Le pourcentageréel de corps qui ont au moins une solution dépend des corpsessayés, mais il doit être au moins de 50%.
Pour la première expérience, le nombre totalde solutions a été de 2401, soit un nombre moyen de solutions pourles corps qui en avaient au moins une de 1,57. Il arrive donc très souvent qu'il existe des solutions multiples. Le nombre total desolutions a été ainsi de 67% de celui des corps étudiés, c'està dire les deux tiers. Il est à noter que tous ces chiffressous-estiment la réalité, le nombre des itérations et surtout celui des points de départétant trop faibles. Il est d'ailleurs arrivé plusieurs fois qu'enreprenant un essai avec une autre séquence de points de départ, on neretrouvait pas une solution déjà rencontrée.
4.2 Influence des diversparamètres
Il y a deux paramètres importants :le nombre maximum d'itérations et le nombre de points de départ. Parailleurs, il est essentiel de bien définir la condition quisélectionne les situations où l'on examine si l'ensemble des caractères des nombres affichés estle même que celui de l'ensemble des caractères des nombresréels.
4.2.1 Le nombred'itérations
Le nombre d'itérations doit avoir aumoins une valeur de 1.000. Au delà de 25.000 itérations, il est très rare que l'on trouve ensuite une solution. Quand il y a des solutionsmultiples, augmenter le nombre d'itérations n'a pas tellement pour effetd'augmenter le nombre de solutions trouvées que d'augmenter le fréquence de certaines d'entre elles. Prenons une expérience faite avec1.000 points de départ pour le corps donné en annexe 3. Laséquence des points de départ est la même pour toutes ces expériences, ce qui fait que le nombre de solutions ne peut jamaisdécroître si l'on augmente le nombre d'itérations. Avec ces 1.000point de départ, on a retrouvé quatre des dix solutions et pour chacune d'entre elles, j'indique lenombre de fois qu'elle a été rencontrée.

	Nombre	nombre de	nombre de	nombre de	nombre de
	d'itérations	solution I	solution II	solution IV	Solution V	Temps
	100	0	0	0	1	18s
	200	0	0	0	1	37s
	500	0	0	1	1	90s
	1.000	1	2	1	1	184s
	2.000	1	3	2	2	367S
	5.000	1	3	5	2	920s
	7.500	1	3	18	2	1384s
	10.000	1	3	44	2	1801s
	15.000	1	3	117	2	2608s
	20.000	1	3	168	2	3455s
	50.000	1	3	186	2	7984s
	100.000	1	3	186	2	15452s

On arrive à 19,2% de succès si l'on admet50.000 itérations. Au delà de ce nombre, le nombre de succèsn'augmente pas. En augmentant le nombre d'itérations, on augmenteconsidérablement le nombre de succès, mais on n'augmente pas le nombre de solutions différentes au delàd'une limite faible : à 1.000 itérations, on a les quatre solutionsque l'on aura à la fin. On n'a pas trouvé les six autres solutions enaugmentant ce nombre d'itérations. Par ailleurs, l'augmentation du nombre d'itérations n'aaugmenté le nombre de découvertes que pour la solution IV. Pour lestrois autres solutions trouvées, leur nombre de découverte aété figé après 2.000 itérations.
Le temps croit linéairement au départ. Lacourbe s'infléchit ensuite quand le nombre de succès devientimportant. En effet, on arrête dès que l'on a un succès, et le gain est d'autant plus important que le nombre d'itérationspermis est grand.
4.2.2 Le nombre de points dedépart
Il est important d'avoir un grand nombrede points de départ. Dans l'expérience précédente, bien quel'on allait jusqu'à 100.000 itérations, on n'a obtenu que quatre des dix solutions parce que l'on n'avaitque 1.000 points de départ. L'une des solutions n'a été obtenuequ'une fois sur 100.000 points de départ.
Il n'est pas évident de définir ce qu'est unbon point de départ, aussi le système se contente-t-il de balayer auhasard l'espace des points de départ. Il utilise des nombrespseudo-aléatoires pour cela, l'aléatoire pur n'apportant aucun avantage. Au contraire, le pseudo-aléatoirepermet de refaire la même séquence de points de départ avec desvaleurs différentes des paramètres. Nous pouvons ainsi apprécierl'importance de ces paramètres.
J'ai fait un essai pour 122 corps avec un nombred'itérations de 2000. Le tableau ci-dessous donne le nombre de corpspour lesquels il y a eu au moins un succès avec des nombres de points dedépart variant de 100 à 10.000. Il donne également Le pourcentage de corps qui ont au moins unsuccès pour ces mêmes nombres de points de départ.

Nombre de	
    points de	100	200	500	1000	2000	5000	10000
départ envisagés
Nombre de	
corps avec	19	31	51	59	61	72	75
  solution
Pourcentage	
  de corps	15,6	25,4	41,8	48,4	50,0	59,0	61,5
avec solution

4.2.3 La condition de test
On teste si l'ensemble des caractèresdes nombres affichés est le même que l'ensemble des caractères desnombres réels. Si cela est vrai, l'ensemble des nombres réels est une solution. Cette condition est inutile pour la méthoded'Hofstadter pour laquelle on a automatiquement la solutions àl'étape suivante si elle est satisfaite. Par contre, pour la varianteutilisée ici, cette condition est indispensable. Sans elle, on peut très bienpasser à côté d'une solution. Par exemple, on a affiché à uncertain instant "cinq" 'f' et "quatre" 'z' et on a compté qu'il y a enréalité 4 f' et 5 'z' . Même s'il n'y a pas d'autre différence entre valeurs affichéeset réelles, on ne trouve pas toujours la solution évidente si l'onn'utilise pas l'amélioration où l'on compare les lettres des nombresaffichés et réels. Cela se produit même si l'on fait ensuite de nombreusesitérations.
L' "écart" est une mesure de la distance à lasolution. C'est la somme sur toutes les lettres des valeurs absolues desdifférences entre valeurs affichées et valeurs réelles. Enreprenant l'exemple précédent, l'écart est de deux, il y a en effet une différence de une unitépour 'f' et de une unité pour 'z'. Dans l'exemple donné dans lasection 2.1, cet écart est de douze. Il peut donc atteindre des valeursimportantes et donner quand même un succès.
S'il est théoriquement possible qu'un écartimpair conduise au succès, cela est certainement très rare. Tous lesessais où les écarts impairs étaient autorisés n'ont jamaismené à une solution. Cela s'explique, car, en général, la méthode donneune solution quand il y a une permutation des nombres. Cela donne desécarts pairs : on compte N unités pour la différence entre lesdeux premiers éléments d'une permutation qui sont M et M+N  et N autres unités pour ladifférence entre M+N et M correspondant au couple symétrique de lapermutation ; cela ajoute 2N points à l'écart. Aussi nous excluonsdans la condition la recherche d'une solution en cas d'écart impair. Par ailleurs, nousdonnons une limite supérieure à la valeur de l'écart pair pourlaquelle on regarde si l'on fait cette vérification. La recherche des ensembles de lettres correspondant aux nombresaffichés et réels différents demande un temps important ; il vautmieux ne la faire que quand elle a des chances raisonnables de succès. De plus, comme la plupart des écarts sont compris entre 10 et 32, onrencontre peu d'écarts faibles, donc on fait rarement intervenir laméthode. Tant que l'écart maximum considéré est inférieur ouégal à 12, le temps supplémentaire que cela demande est très faible puisqu'il ne concernequ'un faible pourcentage des situations, inférieur à 3%. Si l'onpasssait à 20, cela concernerait près d'un cas sur quatre, en tenant compte du fait que l'on n'examine que lesécarts pairs. Pourtant, la plupart des succès sont obtenus pour unécart inférieur ou égal à 12. La valeur de l'écart pourl'exemple donné à la section 2.1 est de 12 et cela mène déjà à un bouleversementde la phrase.

Les temps d'exécution augmentent rapidementdès que la valeur maximale de l'écart dépasse 10 puisque l'onrentre dans les zones où le nombre de situations ayant de telles valeursest très grand. Par ailleurs, la plupart des succès ont lieu avec des écarts inférieurs ouégaux à 12.
4.3. Les meilleurs choixde paramètres
La valeur maximale pour laquelle onregarde si l'on a une solution par permutation des lettres devrait êtrevoisine de 12. C'est un bon compromis entre un temps d'exécution quiaugmente très vite au delà et un pourcentage de succès qui n'augmente pratiquement plus  On n'acertainement pas intérêt à lui faire dépasser 18.
Le nombre d'itérations ne doit pas êtreinférieur à 2.000. En deçà de cette valeur, de nombreusessolutions ne sont plus trouvées. Au delà de 10.000, on augmente certes le nombre de fois d'obtention d'unesolution, mais on ne découvre pas tellement de nouvelle solution. Si onn'a pas trouvé de solution après 25.000 itérations, on n'entrouvera pas davantage en poursuivant même jusqu'à 100.000 itérations.
Le facteur essentiel est le nombre de points dedépart, certaines solutions n'étant trouvées que très rarement.Beaucoup d'expériences ont été faites avec 1.000 points dedépart ce qui est très faible. Avec ce nombre de points de départ, on n'a jamais trouvéplus de quatre solutions sur dix pour le corps de l'appendice 3, même enaugmentant à 40 l'écart ou à 100.000 le nombre d'itérations. Quand on prend un nombre de points de départ nettementsupérieur à 1.000, il est fréquent d'avoir des solutions qui sontobtenues moins de une fois sur mille. Quand on fait deux essais avec lemême corps avec des séquences différentes de points de départ, il arrive souvent que l'on ait unesolution dans un cas et pas dans l'autre. 1000 points de départ est unminimum et il serait souhaitable qu'il soit au moins de 5000.
5. Réflexionsur le means-ends
Le "means-ends" est une méthode derésolution de problèmes où l'on détermine une différenceentre la situation actuelle et le but à atteindre [Newell 1959]. Tant que l'on n'a pas atteint ce but, il existeau moins une telle différence. On associe à chaque différence unensemble d'actions qui la réduisent. On applique une de ces actions etl'on poursuit jusqu'à ce que le but soit atteint.
Cette méthode est appliquée avec succès aussi bien par des humainsque par des systèmes d'IA. Par exemple, pour résoudre une équationdu premier degré, un sous-but est de faire passer les termes en 'x' d'uncôté et les termes constants de l'autre. Une différence est la présenced'un terme en 'x' du mauvais côté. L'action correspondante est de lefaire passer de l'autre côté en changeant son signe.
Quand un sujet ou un programme résout unproblème de cette façon, il voit bien son progrès vers larésolution du problème. Mais cela suppose que les actions ne perturbent pas trop la situation.Si chaque fois que l'on réduit une différence, on en ajoute cinqautres, la méthode devrait échouer. La vie dans un monde où lamoindre action a un grand nombre de conséquences devient vite très compliqué.Quand nous agissons sur un interrupteur, nous allumons la lumière etcela n'a pas d'autre conséquence importante, à part une faibleaugmentation de notre note d'électricité. Mais que serait notre vie si l'action sur cet interrupteuréteignait la lumière dans deux autres pièces, ouvrait la porte dufrigo, interrompait le courant dans le four, faisait passer au rouge un feuà 100 kilomètres de là, arrêtait une rame de métro et sonnait l'heure de la fin descours dans un lycée. Dans un monde où toutes les actions ont desconséquences multiples, il paraît difficile de résoudre desproblèmes avec l'analyse means-ends. Or, le monde des phrases réflexives estde ce type, la modification d'un nombre associé à une lettre modifieune demi-douzaine de nombres associés à d'autres lettres.

On peut parfois utiliser la méthode means-endsdans un univers apparemment cahotique si l'on détermine un ensemble demacro-opérateurs pour lesquels l'univers cesse d'être cahotique. Prenons le cas du rubikube. Chaque rotation d'une partie ducube bouleverse toutes les faces, ce que l'on a gagné sur une face estlargement perdu sur les autres. Il semblerait que nous soyons dans unesituation analogue à celle de la phrase réflexive. Pourtant il existe desmacro-opérateurs, formés de séquences d'une dizained'opérateurs élémentaires (rotations d'un quart de tour). Un deces macro-opérateurs va par exemple permuter deux cubes diamétralement opposés sans changer quoi que ce soit aux autres cubes. A ce moment, il est possible d'appliquer l'analyse means-ends en réduisant progressivement les différences entre l'état actuel et le but. Onrepère une différence et on exécute le macro-opérateur qui réduit cettedifférence.
Malheureusement, nous connaissons peu demacro-opérateurs dans le domaine de la phrase réflexive. L'un d'entreeux est la permutation des nombres dans le cas où l'ensemble descaractères figurant dans les nombres réels est le même que l'ensemble des caractères figurant dans lesnombres affichés. Nous avons vu un autre macro-opérateur avec lecouple onze–douze qui permet d'avoir directement une solution àpartir d'une solution déjà trouvée. Ces macro-opérateurs sont certes utiles, surtout le premier quele système utilise largement, mais ils sont insuffisants pour créerune démarche classique basée sur le means-ends.

Nous pourrrions donc penser que la méthodemeans-ends ne peut être utilisée dans cet univers ; or elle conduitau succès. En effet, la méthode proposée par Hofstadter relèvede cette idée. On prend une lettre pour laquelle le nombre affiché est différentdu nombre réel et on remplace le nombre affiché par ce nombreréel. On avait une différence et on pense la réduire ainsi.Même de ce point de vue, la méthode n'est pas satisfaisante, car souvent on ne réduit pas cettedifférence, alors que l'on en crée d'autres en rendant incorrects desnombres qui étaient corrects. Supposons que le nombre affiché pour'c' était de "quatre" et le nombre réel était "cinq", alors que le nombre affiché pour 'a' était de"neuf" et était égal au nombre réel. Si l'on remplace "quatre" par "cinq", le nombre de 'c' est toujoursinexact puisqu'il est maintenant de "six", mais le nombre de 'a' est devenuinexact puisqu'il vaut maintenant "huit" alors qu'il est toujoursaffiché à "neuf". Il paraît incroyable que cette méthode puisse donner des résultats dans ununivers où chaque action a autant de conséquences.

Une explication pourrait être que cetteméthode fonctionne parce qu'il existe beaucoup de solutions dansl'espace de recherche et que n'importe quelle recherche combinatoireréussirait. Cela est évidemment faux, puisqu'il n'existe qu'une dizaine de solutions au plus dansun espace qui a des milliards de milliards de situations. On peut avoir uneidée de la taille de cet espace en considérant celui qui est défini parles dix solutions du corps étudié dans l'annexe 3. Si onprend l'espace défini par les valeurs extrêmes rencontrées, onarrive à 1,7 X 1012. Mais il est difficile de tomber apriori juste sur ces valeurs et d'être sûr qu'il n'y aura pas de solution avec moins de 38 'e' ou plusde 43 'e'. En supposant seulement la possibilité d'une unité en moinspour chaque valeur minimale et d'une en plus pour chaque valeur maximale,on arrive à un espace de 1,2 X 1015 éléments dans lequel il ya dix solutions. Ceci est à comparer avec les 100.000 points dedépart et les 5.000 itérations pour l'expérience décrite dansl'annexe 3. Cela fait un total de 5 X 108 essais qui ont donné 4433 succès puisque l'ona engendré de nombreuses fois la plupart des phrases. Ce résultat estincomparablement supérieur à ce que donnerait une recherche auhasard.

Un des mérites de la méthode d'Hofstadter estde se placer dans des zones où il y a des chances d'avoir des solutions,les valeurs des nombres considérés au cours des itérations sontpour chaque lettre du même ordre de grandeur que ceux des solutions. Il n'est pas évident detrouver une autre méthode qui maintiendrait aussi simplement cettesituation. Mais, vu la taille de l'espace raisonnable de recherche, celan'explique pas tout. Est-ce que les systèmes qui évoluent ont des propriétés spéciales ?
6. Conclusion
Au fond, est-ce bien utile desavoir que cette phrase contient cinq 'a', deux 'b', huit 'c', huit 'd', vingt 'e', quatre 'f', cinq 'g', six 'h', vingt-deux 'i', un'j', un 'k', deux 'l', un 'm', vingt-deux 'n', cinq 'o', trois 'p', sept'q', cinq 'r', huit 's', dix-neuf 't', vingt 'u', six 'v', un 'w', huit'x', un 'y' et enfin un 'z' ?

Etudier la construction de phrases réflexivespeut semble un amusement sans grand intérêt. Il est évident quecela n'a pas une grande importance pratique. Pourtant, je pense quel'étude de ce problème est intéressante pour trois raisons :

— Il existe de nombreux problèmes qui ontles mêmes caractéristiques que la construction de phrasesréflexives, chaque action ayant des conséquences importantes sur lasituation et détruisant ce qui était satisfaisant. Il serait intéressant de voir quelles méthodessont les plus efficaces pour résoudre les problèmes où chaqueaction a de nombreuses conséquences. Cela se produit presque toujoursquand la réflexivité est en jeu, mais cela arrive aussi dans d'autres types de problèmes.
Nous avons mentionné plus haut le rubikube oùchaque action modifie beaucoup les couleurs des carrés des diversesfaces. C'est le cas de bien d'autres puzzles, par exemple le "instantinsanity" où l'on doit empiler des cubes dont les faces ont des couleurs différentesde telle façon que l'on ait la même couleur sur chaque verticale ;une rotation d'un cube a en général pour effet de rendre davantage monocolore une colonne, mais d'aggraverla situation sur les autres. L'existence d'actions qui ont de nombreusesconséquences devient fréquente dans les problèmes du monderéel, à cause des liens de plus en plus nombreux entre les différents domaines.Les hommes politiques veulent tous relancer l'économie ou réduire lechômage. Pour cela ils prennent une mesure qui paraît raisonnablepour le but cherché, mais elle a des conséquences imprévues et néfastes sur d'autresdomaines. Cela les oblige à prendre une autre mesure pour y remédier,mais cette nouvelle mesure va avoir des conséquences négatives pourle but initial.

— De telles études incitent àréfléchir sur la réflexivité [Pitrat 1988]. Un premierproblème est de savoir comment la mettre en œuvre ; nous avonsmarqué ici l'auto-référence avec le démonstratif "ce" et un nom qui caractérise un texte comme "phrase" ou"titre". D'autres solutions sont possibles, comme l'utilisation du pronom"je". Mais est-ce vraiment de l'auto-référence, c'est nous quil'interprétons ainsi. Dans « J'ai dit "il fait beau". Cette phrase ne contient aucun 'y'.», "cettephrase" fait référence à une phrase citée dans la phraseprécédente et non à elle-même. Elle serait d'ailleurs fausse sielle s'appliquait à elle-même.
La phrase qui s'applique à elle-même le saitimplicitement parce que nous l'obligeons à se modifier enconséquence. Pourtant, dans beaucoup d'applications, comme celle oùdes métaconnaissances s'appliquent à elle-mêmes, ces métaconnaissances ne le savent pas et se traitentcomme elles le feraient de n'importe quelle autre connaissance.Contrairement à ce qui se passe ici, la modification n'a pas effetinstantanément, la nouvelle forme attendant que la forme ancienne ait terminé satâche pour prendre sa place. La notion d'individu n'est pas toujoursclaire dans le domaine de la réflexivité [Pitrat 89 et 95]. Nousavons affaire ici à la réflexivité la plus pure et la plus rare : un élément fait référenceà lui-même et non à une copie de lui-même comme cela arrive engénéral en informatique. C'est d'ailleurs pour cette raison que leproblème est si difficile.
Par ailleurs, il existe des cas où savoir si deuxindividus sont ou non les mêmes n'est pas très clair. Par exempleconsidère-t-on ou non comme la même phrase les variantes correctesbâties sur le même corps ? De même, considère-t-on comme la même phrase le titre de cerapport et la traduction que j'en ai donné en anglais ? Et qu'en est-ilde ce titre et d'une traduction littérale en anglais ?

— La méthode means-ends donne de bonsrésultats dans une situation où nous ne nous y attendions pas. Est-ceque cette méthode capte une régularité encore inconnue duproblème, voire du monde ? Y-a-t-il d'autres problèmes pour lesquelles une telle méthodeobtient des succès contre toute attente ? Le succès est-il dûà l'existence d'un mécanisme évolutif ? Nous sommes surpris et ilest toujours utile de lancer une réflexion pour comprendre les raisons d'une surprise.
Références
Il est difficile de trouver desréférences dans un domaine nouveau qui n'a pas encore delittérature spécialisée et pour lequel un vocabulaire précisn'existe même pas. Il existe peut-être de nombreuses publications sur ce sujet, mais je ne les connais pas. Unmot assez proche est celui de "pangramme" ("pangram" en anglais). Mais celane correspond pas tout à fait à ce domaine, un pangramme est une phrase qui contient toutes les lettres,sans qu'il y ait obligatoirement auto-référence. Un exemple est :«Mixez cinq whiskys pour le futé juge bavard.», qui contient les 26 lettres de l'alphabet dans une phrase de 36 lettres.Cela a un intérêt pratique pour tester les imprimantes. Toute lesphrases décrivant le nombre d'occurrences des vingt-six lettres sont des pangrammes, mais ce n'estpas leur caractéristique essentielle. J'ai cherché sur le Web avec"pangram" et je n'y ai trouvé que des pangrammes qui n'étaient pasauto-référentiels.

Hofstadter D., Metamagical themas, Basicbooks, 1985.
Newell A., Shaw J. and Simon H., Report on a GeneralProblem Solving Program, Proceedings of the International Conference onInformation Processing, 1959, p.259-264.
Pitrat J., Ceci n'est pas un article, Colloquefranco-espagnol sur la métaconnaissance, Cahier du Laforia 70, 1988,p.111-126.
Pitrat J.,Qu'est-ce qu'un individu au royaume de la connaissance, Colloquedu Mans sur la métaconnaissance, Cahier du Laforia 77, 1989,p.37-58.
Pitrat J., What does "itself" mean? Rapport Laforia95/28, 1995.

Annexe 1 :Glossaire
* affiché : Le nombre affichélié à un caractère est celui que la phrase déclare pour cecaractère.
* ajout : Un ajout est un ensemble decaractères que l'on ajoute au noyau pour former un corps particulier. Ondéfinit plusieurs ensembles d'ajouts indépendants les uns des autrespour créer un grand nombre de corps.
* corps : Le corps d'une phrase est formé del'ensemble des caractères de cette phrase que l'on veut compter et quine sont pas dans les nombres associés aux lettres. Dans le cas où l'on engendre les corps automatiquement, il est constitué du noyau etde l'ensemble des ajouts.
* correct : Une phrase est correcte si, pourchaque caractère, le nombre affiché est égal au nombred'occurrences réel de ce caractère dans la phrase.
* degré déterminant le problème : C'estle nombre minimum de nombres qu'il faut connaître pour vérifier siune phrase décrit correctement son contenu quand on connaît déjà son corps. Il est de 18 pour le français ; il est de 16 pour l'anglaisà condition que la phrase n'ait pas une longeur démesurée. Plus ilest élevé, plus la combinatoire est élevée.
* écart : L' écart est la somme, sur tousles caractères, des valeurs absolues des différences entre valeursréelles et valeurs affichées. S'il est nul, on a une solution.
* fixe : La partie fixe d'une phrase est formée du corps et descaractères des nombres liés aux caractères qui n'apparaissent dansaucun nombre.
* itération : A chaque itération, onremplace certains des nombres affichés par les nombres réelscorrespondants. Dans la méthode d'Hofstadter, tous les nombresaffichés différents des nombres réels sont remplacés à chaque itération ; dans la méthodemodifiée, un seul remplacement est fait à chaque itération.
* mobile : La partie mobile d'une phrase estformée des caractères des nombres qui sont liés aux caractèresqui peuvent figurer dans des nombres.
* nombre : La partie nombre d'une phrase est formée de l'ensembledes caractères qui appartiennent aux nombres liés aux caractèresque l'on compte 
* noyau : Dans la méthode proposée pour engendrer denombreuses phrases réflexives, le noyau est la partie commune aux corpsde toutes ces phrases.
* point de départ : Un point de départ estl'ensemble des nombres tirés au hasard que l'on affecte à tous lescaractères dont le nombre est défini dans la phrase ; en français, on tire 26 nombres. A la suite de ce tirage, on itérera jusqu'aunombre maximum d'itérations prévu sauf si l'on atteint une solutionauquel cas on arrête évidemment les itérations. On continue avecle point de départ suivant jusqu'à avoir atteint le nombre maximum de points dedépart prévu sauf si l'on a trouvé une solution et si l'on nedésire pas avoir plusieurs solutions pour le même corps.
* réel : Le nombre réel lié à uncaractère est le nombre de ses occurrences dans la phrase.

Annexe 2 :Le programme
Il est écrit en C. Lescommentaires sont en italiques.
#include <stdio.h>
char noyau[]="vousavezraisondecompterleslettresdecettephraseavantdelacroirequandelleaffirmequellecontientabcdefghijklmnopqrstuvwxyetz";
Définition du noyau.
char ajout[9][4][30]={
{"cherlecteur","","cherslecteurs","amilecteur"},
{"","bien","parfaitement"},
{"soigneusement","avecsoin","avecbeaucoupdesoin",""},
{"longue","curieuse","bizarre",""},
{"finalement","pourfinir","enfin","pourterminer"},
{"exactement",""},
{"etderecompter",""},
{"toutes",""},
{"vous",""}
};
Nous venons de donner la listedes ajouts. Il y en a neuf qui ont au plus quatre valeurs possibles. On asupposé qu'un ajout ne peut avoir plus de 29 caractères.
charlettres[100][30]={"zero","un","deux","trois","quatre","cinq","six","sept","huit",
"neuf","dix","onze","douze","treize","quatorze","quinze","seize",
"dixsept","dixhuit","dixneuf","vingt","vingtetun","vingtdeux",
"vingttrois","vingtquatre","vingtcinq","vingtsix","vingtsept",
"vingthuit","vingtneuf","trente","trenteetun","trentedeux",
"trentetrois","trentequatre","trentecinq","trentesix","trentesept",
"trentehuit","trenteneuf","quarante","quaranteetun","quarantedeux",
"quarantetrois","quarantequatre","quarantecinq","quarantesix",
"quarantesept","quarantehuit","quaranteneuf","cinquante",
"cinquanteetun","cinquantedeux","cinquantetrois","cinquantequatre",
"cinquantecinq","cinquantesix","cinquantesept","cinquantehuit",
"cinquanteneuf","soixante","soixanteetun","soixantedeux",
"soixantetrois","soixantequatre","soixantecinq","soixantesix",
"soixantesept","soixantehuit","soixanteneuf","soixantedix",
"soixanteetonze","soixantedouze","soixantetreize",
"soixantequatorze","soixantequinze","soixanteseize",
"soixantedixsept","soixantedixhuit","soixantedixneuf",
"","","","","","","","","","","","","","","","","","","",""};
lettres[i] contient la suitedes caractères du nombre i. "zero" ne sert normalement que dansl'initalisation de la phrase. Toutefois, si l'on veut réaliser une phrase qui ne contienne pas certaines lettres, il fautimpérativement remplacer "zero" par la suite vide. Si l'on veut passerà l'anglais, il suffit de changer ces nombres et de donner un noyau etdes ajouts en anglais. Il faut cependant tenir compte de ce que, en anglais, on met  les lettres au pluriels'il y a plusieurs occurrences. On doit donc mettre "twos", "threes",fives", etc, mais naturellement "one" figure sans 's'.
On n'a mis que les énoncéscorrespondants aux nombres allant de 0 à 79. Par précaution, on aajouté vingt énoncés vides pour les valeurs entre 80 et 99 ; elles peuvent se rencontrer au moment de l'initialisation d'un nouveaupoint de départ. Il est alors possible d'atteindre des nombres del'ordre de quatre-vingt pour 'e' ou 't' : ils apparaissent jusqu'à trois fois dans certains nombres, comme "trente-quatre".
Si jamais un nombre dépasse 79 dans unephrase solution, celle-ci est incorrecte. Cela ne peut arriver qu'avec desnoyaux très longs et il suffit dans ce cas de définir les nombresaprès 79.
int nh[9]={4,3,4,4,4,2,2,2,2};
Liste des nombres de valeurspossibles pour chaque ajout.
main()
{
int reel[256], aff[256], w[256], g[20][256];
int za[256], zb[256], nn[20];
int nt, f, i, j, k, l, m, n, q, s, t, z;
int lim, bis, nz, ncorps, nsuc, tot, ecart, ecartmax, iter;
int ih[9], na[9];
scanf("%d %d %d %d %d %d %d %d %d %d %d %d%d %d %d",&ih[0], &ih[1], &ih[2], &ih[3], &ih[4], &ih[5], &ih[6], &ih[7], &ih[8],&ncorps, &nsuc, &tot, &lim, &iter, &ecartmax);
Les "ih" indiquent l'ensembledes neuf ajouts que l'on va commencer par examiner. "ncorps" est le nombrede corps envisagé, "nsuc" le nombre de corps pour lesquels on a eu aumoins un succès et "tot" le nombre total de phrases réflexives engendrées. Ils sontlus de façon à pouvoir répartir les essais sur un même noyausur plusieurs exécutions. Pour la première exécution, on  donne lavaleur 0  à  ces 12 nombres. Pour les suivantes, on part des valeurs obtenues à lafin de l'exécution précédente.
"lim" est le nombre de points de départque l'on considére pour un corps donné. La probabilité d'avoir unsuccès augmente asymptotiquement avec ce paramètre. Beaucoup d'essaisont été faits avec la valeur 1000 qui est très faible, certaines solutionsn'ont été trouvées qu'une fois pour 100.000 points de départ.Le temps machine est proportionnel à ce paramètre. 10.000 serait unevaleur plus sérieuse, mais le temps machine serait dix fois plus grand.
"iter" est le nombre d'itérations. Ceparamètre est important car il joue sur le temps machine, qui estproportionnel à ce nombre, et sur le pourcentage de succès quicroît asymptotiquement. Des essais ontété faits avec des valeurs entre 2.000 et 10.000. Beaucoup desolutions sont trouvées avant 2.000 itérations, mais il est assezfréquent que ce nombre soit compris entre 2.000 et 10.000 ; il est rareque plus de 10.000 itérations soient nécessaires pour trouver une solution quand il en existeune.
"ecartmax" est la valeur maximale del'écart pour laquelle on fera la recherche d'une solution évidente.Une valeur de 12 est satisfaisante et il ne semble guère utile dedépasser 18.
for( ; ; )
Boucle sur les corps.
{
for (nt=0; nt<9; nt++) na[nt]=ih[nt];
Les "na" indiquent l'ensembled'ajouts présentement utilisé.
for (nt=8; nt>=0; nt--) if (++ih[nt]>=nh[nt]) ih[nt]=0; elsebreak;
Les "ih" définisentl'ensemble d'ajouts suivant.
ncorps++;
On vient de définir unnouveau corps, aussi on incrémente le nombre de corps essayés.
bis=(-1);
bis indique le nombre desolutions différentes obtenues pour le corps. Il est négatif tant quel'on n'en a pas encore trouvé, il vaut 0 si l'on en a trouvéune…et N-1 si l'on en a trouvé N.
for (f=0; f<lim; f++)
Boucle sur les "lim" points dedépart.
{
for (z='a'; z<='z'; z++) w[z]=(rand()>>11)&077;
Détermination d'un point dedépart ; on crée vingt-six nombres aléatoires équipartis entre0 et 63. Le décalage est indispensable, la fonction rand n'étant pasde bonne qualité pour les bits de faible poids. En particulier, le bit de plus faible poidsprend alternativement les valeurs 0 et 1. Sans cette précaution, onrisque, comme cela est effectivement arrivé, un bouclage sur laséquence des valeurs de départ.
for (i='a'; i<='z'; i++) {reel[i]=0; aff[i]=w[i];}
"reel" contient l'ensemble desvaleurs réelles, "aff" l'ensemble des valeurs affichées. L'ensembledes valeurs affichées de départ est celui des vingt-six nombresaléatoires que l'on vient de déterminer. On va calculer les valeurs réelles correspondantes. On acommencé par les initialiser à 0.
for (j=0; noyau[j]!='\0'; j++) reel[noyau[j]]++;
On compte les caractères dunoyau.
for (i=0; i<9; i++) for (j=0; ajout[i][na[i]][j]!='\0'; j++) reel[ajout[i][na[i]][j]]++;
On prend maintenant en compteles caractères des 9 termes ajoutés au noyau.
for (i='a'; i<='z'; i++) for (j=0; lettres[w[i]][j]!='\0'; j++) reel[lettres[w[i]][j]]++;
On compte les caractèresdes vingt-six nombres aléatoires qui sont dans le tableau "w". "reel" contient bien les nombres d'occurrences réels des lettres de la phrase correspondant à l'affichage des nombres aléatoires que l'on vient de tirer.
q='a';
On initialise la lettre àpartir de laquelle on commence à chercher une différence entre valeuraffichée et valeur réelle.
for (n=0; n<iter; n++)
Boucle de "iter" itérationspour ce point de départ.
{
 lab1: q+=19;
 if (q>'z') q-=26;
 if (reel[q]==aff[q]) goto lab1;
On détermine la premièrelettre après la dernière lettre modifiée pour laquelle il y a unedifférence entre la valeur affichée et la valeur réelle. Onprogresse à chaque étape, puisque q n'est pas modifié ailleurs. Le choix del'incrémentation à 19 plutôt qu'à 1 vient d'un bogue dans uneancienne version. Quand le bogue a été corrigé, les performancesont baissé. En analysant ce bogue, il est apparu que ce qu'il faisait correspondaitaux instructions précédentes. Il semble qu'il vaut mieux ne pas faireun balayage trop systématique des lettres de l'alphabet et que«q+=19» est préférable à «q++».
 l=aff[q];
Valeur affichée de lalettre à modifier.
 m=reel[q];
Valeur réelle de la lettreà modifier. Il est indispensable de stocker la valeur réellecorrespondant à la lettre choisie, car les étapes suivantes vont lamodifier.
 for (s=0; lettres[l][s]!='\0'; s++) reel[lettres[l][s]]--;
On enlève des valeursréelles les occurrences des caractères de l'ancienne valeuraffichée de la lettre à modifier.
 for (t=0; lettres[m][t]!='\0'; t++) reel[lettres[m][t]]++;
On ajoute aux valeursréelles les occurrences des caractères de l'ancienne valeur réellede la lettre à modifier.
 aff[q]=m;
La nouvelle valeur affichéeest l'ancienne valeur réelle.  On vient de mettre à jour les valeursaffichées et les valeurs réelles ; on va maintenant voir si l'on aobtenu une solution.
 ecart=0;
 for (k='a'; k<='z'; k++) ecart+=abs(reel[k]-aff[k]);
On calcule l'écart ; s'ilest nul, on a une solution.
 if (ecart<=ecartmax&&(ecart%2)==0&&ecart>0)
{
Dans le cas où l'écartn'est pas nul, on vérifie si l'on n'a pas quand même une solutionévidente. Pour cela, on examine si l'ensemble des lettres des valeursaffichées est le même que l'ensemble des lettres des valeurs réelles. Comme ceci est long,on ne le fait que pour les écarts pairs, les écarts impairs ayanttrès peu de chance de donner lieu à un tel accord. On ne le faitégalement que pour des écarts pas trop importants, valant au plus ecartmax.
 for (j='a'; j<='z'; j++) {za[j]=0; zb[j]=0;}
Initialisation des compteurs.
 for (j='a'; j<='z'; j++)
{if(reel[j]!=aff[j])
{for (s=0; lettres[reel[j]][s]!='\0'; s++) za[lettres[reel[j]][s]]++;
Les za contiennent le nombred'occurrences de chaque caractère pour toutes les valeurs réelles quine sont pas égales aux valeurs affichées.
 for (s=0; lettres[aff[j]][s]!='\0'; s++) zb[lettres[aff[j]][s]]++;

pardLes zb contiennent le nombred'occurrences de chaque caractère pour toutes les valeurs affichéesqui ne sont pas égales aux valeurs réelles.
}
}
 for (j='a'; j<='z'; j++) if (za[j]!=zb[j]) goto lab2;
Si l'on franchit cette boucle,l'ensemble des caractères des valeurs affichées est le même quel'ensemble des caractères des valeurs réelles. L'ensemble des valeursréelles est donc une solution. Le "goto" est nécessaire, car il ne suffitpas de sortir de la boucle en cas d'échec.
 ecart=0;
}
lab2: if(ecart==0)
{
On a une solution qui estcontenue dans les "reel". On regarde d'abord si on ne l'a pas déjàrencontrée, les "bis+1" solutions déjà connues étantstockées dans les "g".
 for (nz=0; nz<=bis; nz++)
{
 for (j='a'; j<='z'; j++) if (g[nz][j]!=reel[j]) goto lab4;
En cas de différence, lanouvelle solution n'est pas égale à la "nz"-ième solutiondéjà connue ; on passe à la comparaison avec la solution suivantesi elle existe.
 nn[nz]++;
Il n'y a aucune différenceavec une solution déjà rencontrée. On incrémente le nombre defois où l'on a trouvé cette solution.
 goto lab3;
On saute à l'examen dupoint de départ suivant.
 lab4: ;
Fin de la boucle de recherched'une solution déjà rencontrée.
}
 bis++;
C'est la première fois quel'on rencontre cette solution. "bis" compte le nombre de solutionsdifférentes pour un corps.
 tot++;
On incrémente le nombretotal de solutions différentes rencontrées avec ce noyau.
 if (bis==0)
{
C'est la première solutiontrouvée pour ce corps.
 nsuc++;
On incrémente le nombretotal de corps pour lesquels il existe au moins une solution.
 printf("on considere%d,%d,%d,%d,%d,%d,%d,%d,%d. Total des essais %d, nombre de succes %d\n",na[0], na[1], na[2], na[3],na[4], na[5], na[6], na[7], na[8], ncorps, nsuc);
On imprime le numéro dechaque ajout quand on trouve la première solution. Cela permet dedéterminer le corps.
}
printf("On a un nouveau succes %d. Total dessucces %d\n", bis, tot);
 for (i='a'; i<='z'; i++) printf("(%c:%d)", i, reel[i]);
 printf("\n");
On imprime le nombred'occurrences des lettres de la solution.
 for (j='a'; j<='z'; j++) g[bis][j]=reel[j];
On stocke dans les g lesnombres d'occurrences de chaque caractère pour cette "bis+1"-ièmesolution.
 nn[bis]=1;
Les "nn" comptent le nombre defois où l'on a trouvé chaque solution. Comme on a trouvé unesolution, il est inutile de continuer d'itérer.
 goto lab3;
On passe au point de départsuivant.
}
}
lab3: ;
Fin de la boucle des points dedépart.
}
for (nz=0; nz<=bis; nz++)
printf("nombre d'obtentions pour %d : %d sur %dessais avec %d iterations et un ecart max de%d\n", nz, nn[nz], lim, iter, ecartmax);
A la fin de l'examen d'uncorps, on indique le nombre de succès rencontrés pour chaquesolution.
if (nt<0) exit(0);
Si nt est négatif, on atraité tous les ajouts que l'on devait examiner.
}
}
C'est le programme le pluscourt que j'aie jamais écrit. En IA, les programmes ont d'habitude unetaille nettement plus importante.

Annexe 3 :Une phrase avec de nombreuses solutions
Un corps a donné naissance à dixsolutions, ce qui est supérieur à ce qui a été obtenu pour tousles autres corps essayés, les records suivants étant de huit solutions. Nous donnons ci-dessous ces solutions avec lenombre de fois qu'elles ont été obtenues au cours d'un essai avec 100000 points de départ et 5.000 itérations. Le total des succès aété de 4433, ce qui fait 4,43% des points de départ. Dans un autre essai,les chiffres pourraient être un peu différents. En particulier, il sepourrait que l'on n'obtienne pas la dixième solution. Il se pourraitaussi que l'on trouve une onzième solution hypothétique que le programme n'a pas encoreengendrée. Notons qu'avec la méthode initiale d'Hofstadter, aucune deces solutions n'a été obtenue après 82.000 points de départ et5.000 itérations.
Phrase I, engendrée 1470 fois.
Vous avez bien raison de comptertoutes les lettres de cette phraseavant de la croire quand elle vous affirme qu'elle contient quatorze 'a',deux 'b', huit 'c', neuf 'd', trente-neuf 'e', cinq 'f', quatre 'g', six'h', vingt et un 'i', un 'j', un 'k', huit 'l', quatre 'm', vingt-quatre'n', douze 'o', quatre 'p', onze 'q', dix-huit 'r', dix 's', trente 't', vingt-cinq 'u', huit 'v', un 'w', six'x', un 'y' et pour terminer cinq 'z'.
Phrase II, engendrée 1253 fois.
Vous avez bien raison de comptertoutes les lettres de cette phrase avant de la croire quand elle vousaffirme qu'elle contient onze 'a', deux 'b', sept 'c', huit 'd', trente-neuf 'e',six 'f', cinq 'g', quatre 'h', vingt-deux 'i', un 'j', un 'k', huit 'l',quatre 'm', vingt-cinq 'n', douze 'o', six 'p', neuf 'q', quinze 'r',quinze 's', vingt-six 't', vingt-trois 'u', neuf 'v', un 'w', sept 'x', un 'y' et pour terminer six 'z'.
Phrase III, engendrée 650 fois.
Vous avez bien raison de comptertoutes les lettres de cette phrase avant de la croire quand elle vousaffirme qu'elle contient treize 'a', deux 'b', huit 'c', douze 'd', trente-huit 'e', cinq 'f', cinq 'g', six 'h', vingt-quatre'i', un 'j', un 'k', huit 'l', quatre 'm', vingt-deux 'n', dix 'o', cinq'p', dix 'q', dix-sept 'r', dix 's', vingt-neuf 't', vingt-quatre 'u', neuf'v', un 'w', huit 'x', un 'y' et pour terminer quatre 'z'.
Phrase IV, engendrée 455 fois.
Vous avez bien raisonde compter toutes les lettres de cette phrase avant de la croire quand ellevous affirme qu'elle contient treize 'a', deux 'b', sept 'c', neuf 'd',quarante et un 'e', six 'f', cinq 'g', quatre 'h', vingt-deux 'i', un 'j', un 'k', huit 'l', quatre 'm',vingt-trois 'n', douze 'o', sept 'p', huit 'q', dix-sept 'r', seize 's',vingt-neuf 't', vingt-trois 'u', neuf 'v', un 'w', six 'x', un 'y' et pourterminer cinq 'z'.
Phrase V, engendrée 426fois.
Vous avez bien raison de compter toutes les lettres de cette phrase avantde la croire quand elle vous affirme qu'elle contient treize 'a', deux 'b',sept 'c', huit 'd', quarante 'e', cinq 'f', cinq 'g', quatre 'h',vingt-deux 'i', un 'j',un 'k', huit 'l', quatre 'm', vingt-trois 'n', onze 'o', six 'p', neuf 'q',seize 'r', quinze 's', vingt-six 't', vingt-deux! 'u', neuf 'v', un 'w',sept 'x', un 'y' et pour terminer six 'z'.
Phrase VI, engendrée 89 fois.
Vous avez bien raison de compter toutes les lettres de cette phrase avantde la croire quand elle vous affirme qu'elle contient treize 'a', deux 'b',sept 'c', sept 'd', quarante 'e', quatre 'f', cinq 'g', cinq 'h',vingt-trois 'i', un 'j', un 'k', huit 'l', quatre 'm', vingt-deux 'n', onze 'o', six 'p', huit 'q', seize 'r',seize 's', vingt-huit 't', vingt et un 'u', neuf 'v', un 'w', six 'x', un'y' et pour terminer six 'z'.
Phrase VII, engendrée 67 fois.
Vous avez bien raison de compter toutes les lettres de cette phrase avantde la croire quand elle vous affirme qu'elle contient quatorze 'a', deux'b', sept 'c', huit 'd', quarante 'e', cinq 'f', cinq 'g', quatre 'h',vingt et un 'i', un 'j', un 'k', huit'l', quatre 'm', vingt-deux 'n', douze 'o', six 'p', neuf 'q', seize 'r',seize 's', vingt-sept 't', vingt-trois 'u', neuf 'v', un 'w', six 'x', un'y' et pour terminer six 'z'.
Phrase VIII, engendrée 18 fois.
Vous avez bien raison de compter toutes les lettres de cette phrase avantde la croire quand elle vous affirme qu'elle contient seize 'a', deux 'b',huit 'c', huit 'd', quarante et un 'e', quatre 'f', cinq 'g', cinq 'h',vingt-trois 'i', un 'j', un 'k', huit 'l', quatre 'm', vingt-trois 'n', quatorze 'o', quatre 'p', douze 'q',vingt-deux 'r', treize 's', trente-trois 't', vingt-cinq 'u', neuf 'v', un'w', quatre 'x', un 'y' et pour terminer six 'z'.
Phrase IX, engendrée 4 fois.
Vous avez bien raison de compter toutes les lettres de cette phrase avantde la croire quand elle vous affirme qu'elle contient quinze 'a', deux 'b',six 'c', neuf 'd', quarante 'e', six 'f', cinq 'g', quatre 'h', vingt 'i',un 'j', un 'k', huit 'l', quatre 'm', vingt-deux 'n', neuf 'o', sept 'p', dix 'q', dix-sept 'r', treize's', vingt-huit 't', vingt-quatre 'u', neuf 'v', un 'w', sept 'x', un 'y'et pour terminer quatre 'z'.
Phrase X, engendrée 1fois.
Vous avez bien raison de compter toutes les lettres de cette phrase avantde la croire quand elle vous affirme qu'elle contient quinze 'a', deux 'b',sept 'c', sept 'd', quarante-trois 'e', quatre 'f', cinq 'g', trois 'h',vingt et un 'i', un 'j', un 'k',huit 'l', quatre 'm', vingt-cinq 'n', treize 'o', sept 'p', douze 'q',vingt et un 'r', quinze 's', trente-quatre 't', vingt-quatre 'u', neuf 'v',un 'w', trois 'x', un 'y' et pour terminer six 'z'.

Pour ces dix phrases, voici lesvaleurs minimales et maximales ainsi que le nombre de valeurs possibles,c'est à dire en comptant les intermédiaires et les extrêmes, pour les 18 lettres correspondant au degré déterminant leproblème :

	lettre	valeurminimum	valeur maximum	nombre de valeurs
	'a'	11	16	6
	'c'	6	8	3
	'd'	7	12	6
	'e'	38	43	6
	'f'	4	6	3
	'g'	4	5	2
	'h'	3	6	4
	'i'	20	24	5
	'n'	22	25	4
	'o'	9	14	6
	'p'	4	7	4
	'q'	8	12	5
	'r'	15	22	8
	's'	10	16	7
	't'	26	34	9
	'u'	21	25	5
	'x'	3	8	6
	'z'	4	6	3

Remarquons que certaines valeurs intermédiairespeuvent ne pas être représentées dans les solutions, par exemple"dix" et "onze" pour 'd'. Ce sont pourtant des valeurs possiblespuisqu'elles sont encadrées par des valeurs qui sont, elles, représentées. Le produit desnombres de valeurs donne une borne inférieure de la taille d'un espacede recherche raisonnable. Il vaut 215 X 310X 53 X 7, soit environ 1,7 X 1012. Mais il est difficile apriori de déterminer ces limites avec autant de précision. Si l'onenlève une seule unité pour chaque valeur minimale et si on ajouteune seule unité pour chaque valeur maximale, on arrive cette fois à un espace de taille1,2 X 1015. Même ce nombre est sans doute plutôttrop petit : dans les deux exemples de la phrase qui ne mentait pas,donnés dans les sections 2.5 et 3.1, les nombres d'occurrences de 'q' étaientde 7 et de 16, ce qui correspond à dix valeurs raisonnables pour cettelettre. C'est largement supérieur au chiffre de 5 trouvé pour les dixphrases du corps étudié ici.