Thread by @gro_tsen

Bon, ce genre de petits «tours de magie» 🔽 a le don de m'insupporter. Moi je n'ai pas envie qu'on me donne un poisson, j'ai envie qu'on m'explique comment pêcher! Donc, comment générer ce genre de phrase? ⤵️ •1/15

https://twitter.com/ThomasCabaret84/status/1460553575273308160

Bon, je ne peux pas expliquer comment Gilles Esposito-Farèse a trouvé la phrase citée ci-dessus, mais je peux vous dire comment j'ai trouvé les deux ci-dessous (en même temps que reconnaître que ce n'est pas malin du tout): •2/15

Mon code (Perl) est là; si on le lance, il va tourner pendant assez longtemps et finalement produire une phrase autodescriptive du genre de celles ci-dessus (et si ça se trouve identique à l'une d'elles): •3/15 gist.github.com/Gro-Tsen/32de1…

L'algorithme, donc, est complètement idiot: à la base, j'applique de façon répétée la fonction φ (appelée «describe» dans mon code) qui transforme une phrase en une description, en espérant tomber sur un point fixe. •4/15

La fonction φ ne présente aucune difficulté particulière à écrire, il faut juste coder le truc qui transforme un nombre en son écriture littérale, ça tombe bien j'avais fait ça il y a longtemps. •5/15

https://twitter.com/gro_tsen/status/1461384113160663046

En général, quand on applique une fonction φ (disons aléatoire) dans un ensemble fini, on ne va pas tomber sur un point fixe, on va tomber sur une boucle. Donc le programme enregistre les chaînes produites et s'il en voit une déjà rencontrée, il sait qu'on a bouclé. •6/15

Que faire quand si a bouclé sur autre chose qu'un point fixe? Essayer autrement. On pourrait partir d'un point initial différent, mais après tout rien ne dit qu'un point fixe existe, donc ce n'est pas forcément le mieux. •7/15

(Une fonction φ aléatoire sur un grand ensemble fini a en gros 1 − 1/e ≈ 63% de chances d'avoir un point fixe, parce que ((N−1)/N)^N → 1/e, chaque x ayant (N−1)/N chances d'avoir φ(x)≠x, où N est la taille de l'ensemble. Probable, mais loin d'être certain, donc.) •8/15

(Bon, ici ma fonction φ est sans doute mal modélisée par une fonction aléatoire, mais c'est une heuristique qui vaut ce qu'elle vaut. Je ne sais pas non plus la taille «effective» N de l'ensemble des descriptions plausibles, mais on s'en fout un peu.) •9/15

Bref, si je tombe sur un cycle, au lieu de prendre un point différent, je change (aléatoirement) ma fonction φ, soit en changeant le début de la phrase («Cette phrase comporte», «Cette jolie phrase contient») soit en changeant quelques autres détails. •10/15

(Mais je reprends quand même l'itération à partir du point trouvé dans la fonction précédente, ou d'une petite modification de celui-ci. L'idée étant que pour ma fonction φ variée, ça servira de point de départ plus ou moins aléatoire.) •11/15

Combien faut-il faire d'essais avant de tomber sur un point fixe? Là aussi j'ai une heuristique débile: si au bout de n itérations on a bouclé, c'est sur un des n points précédents, donc on a 1/n chance d'avoir trouvé un point fixe. •12/15

Comme mes fonctions bouclent au bout de ~10⁴ itérations, je m'attends donc à ce que réessayer ~10⁴ fois finisse par révéler un point fixe: long mais pas complètement délirant. Et de fait, ça semble réussir puisque j'ai trouvé les phrases ci-dessus. •13/15

(En passant, n donne idée de N: si on tire des élts aléatoires d'un ensemble à N éléments, la première répétition va se produire à n de l'ordre de √N (en fait, √(πN/2) je crois), donc on doit avoir N ~ 10⁸ ici et on ne fait pas plus intelligent que juste le parcourir.) •14/15

Voilà, tout ça c'était vraiment l'algorithme débile. Peut-être que mes collègues qui sont vraiment cryptographes comme @cryptosaurus6 ou @shab0y ont des idées de façons vachement plus malignes pour trouver des points fixes de la fonction «description». •15/15