Gro-Tsen Profile picture
18 Nov, 15 tweets, 4 min read
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
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 Cette phrase comporte huit a, six c, sept d, vingt-cinq e, dCette jolie phrase contient huit a, huit c, cinq d, vingt-se
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
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

• • •

Missing some Tweet in this thread? You can try to force a refresh
 

Keep Current with Gro-Tsen

Gro-Tsen Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @gro_tsen

18 Nov
Ce que je trouve fascinant avec les grincheux s'indignant que le “Robert” ait ajouté un nouveau pronom dans son dico, c'est surtout cette image prescriptiviste du dictionnaire qui dirait comment «bien» écrire plutôt que permettre de comprendre ce que les gens écrivent vraiment.
Moi je n'utilise pas le pronom «iel». (Pour la façon dont je conçois l'écriture inclusive, cf.: madore.org/~david/weblog/…‌.) Mais c'est JUSTEMENT pour ça que je suis plutôt content qu'il entre dans le dico: si j'avais un doute sur ce que veulent dire les personnes qui l'utilisent.
Je ne me sens pas menacé dans ma non-utilisation du pronom «iel» par son entrée dans le “Robert” parce que je n'utilise pas les dictionnaires pour savoir comment bien écrire, je les utilise pour savoir ce que veulent dire les gens quand ils écrivent.
Read 5 tweets
13 Nov
I bookmarked a couple of months ago, and finally got around to reading, this article by ‘Quanta’ magazine on the story behind Freedman's proof of the 4-dimensional Poincaré conjecture — and how it was saved from being “lost”. It's quite interesting. quantamagazine.org/new-math-book-…
The statement is that any topological 4-manifold that is a homotopy sphere is, in fact, homeomorphic to a sphere. (The analogous theorem for dimension ≥5 was proved in the 1960's by Smale & others. In dimension 3 it was proved in the 2000's by Perelman.) en.wikipedia.org/wiki/Generaliz…
The gist of the story in dimension 4 is that Michael Freedman wrote a sketch of a proof in the 1980's and convinced the experts that his proof held water, but details were never fully written down beyond this basic sketch (which further contained errors).
Read 6 tweets
12 Nov
Tiens, aujourd'hui je cherchais à savoir quelle est la forme légale de Paris-Saclay, l'article fr.wikipedia.org/wiki/Intercomm… m'apprend qu'il y a des «métropoles», des «communautés urbaines», des «communautés d'agglomération», des «communautés de communes», des «syndicats …
… d'agglomération nouvelle», des «syndicats de communes», des «syndicats mixtes fermés» et «…ouverts», des «pôles métropolitain», des «pôles d'équilibre territorial et rural» et des «pays». Ça ressemble à une blague mais ça n'en est pas.
On a réussi à inventer aussi incompréhensible que le Royaume-Uni avec ses shires / historical counties, ceremonial counties, metropolitan counties, non-metropolitan counties, unitary authorities, etc. #ClubContexte
Read 4 tweets
12 Nov
The absurdity of the Unix system of locales is confounding. If you want to use language xx and the conventions of country YY and encoding ZZZ, you might set locale to xx_YY.ZZZ; but LC_CTYPE only cares about ZZZ, some locale variables about xx, others about YY.
And every one of these xx_YY.ZZZ combinations needs to be “generated”. And on a multi-user machine, since you don't know what your users might want, well, you need to generate them all.
So why couldn't you just set LC_CTYPE=ZZZ, LC_LANGUAGE=xx (perhaps with xx_YY in case you really care about some per-country language differences) and LC_COUNTRY=YY? Because f😡ck you, that's why.
Read 4 tweets
11 Nov
I've recently started reading (or attempting to) Takayuki Kihara's paper ‘Lawvere-Tierney topologies for computability theorists’, I think it will take me a long time to digest, but it really makes me consider computability in a different light. arxiv.org/abs/2106.03061
He defines a generalization of Turing degrees but for partially defined multivalued functions with a secret input; the reduction is defined by a fun three-player game; and he shows that these degrees are isomorphic to L-T topologies on the effective topos (which he defines).
He then proposes that these form a plausible definition of a “world” of computability intermediate between computable mathematics (corresponding to the effective topos) and classical mathematics (corresponding to the topos of sets).
Read 4 tweets
4 Nov
For possible later reference, here is a ✺meta-thread✺ linking to several (long) explanatory threads I've written in the past regarding epidemiology. Since I was often learning as I was tweeting, it's a bit of a mess, but I think it's still worth compiling: ⤵️ •1/9
Let's start with a thread on the basic deterministic SIR model, which was written quite early on (and I didn't fully understand the point made in the thread linked in the next tweet). •2/9
A thread on the difference (“overshoot”) between “herd immunity threshold” and “final attack rate” in the SIR model. •3/9
Read 9 tweets

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal

Thank you for your support!

Follow Us on Twitter!

:(