David Madore's WebLog: Mathematics

☞ Données de températures à Paris Montsouris

En ce moment il fait chaud à Paris (et en plus notre clim est en panne), alors je suis allé récupérer des jeux de données météo, dont je m'étais plaint précédemment qu'elles n'était pas librement disponible, et qui le sont maintenant, pour faire joujou avec. En l'espèce, je suis allé récupérer[#] les températures relevées à Paris depuis 1873, spécifiquement celles à la station du parc Montsouris (ici).

[#] La source est ici (j'ai utilisé les fichiers Q_75_1816-1949_RR-T-Vent.csv.gz, Q_75_previous-1950-2023_RR-T-Vent.csv.gz et Q_75_latest-2024-2025_RR-T-Vent.csv.gz) ; je précise ça parce que c'est un vrai labyrinthe d'aller entre le site des données publiques de Météo France et l'endroit où sont vraiment les fichiers dont je parle, ça continue à ressembler à la blague avec les chaussures au Goum que j'avais raconté dans ce billet, sauf que maintenant il y a vraiment des chaussures au bout, mais elles sont introuvables depuis l'entrée. (En fait, j'avais bookmarké le lien, et je ne sais honnêtement pas comment j'ai réussi à naviguer jusque là.)

C'est un jeu de données intéressant, parce que, quand même, 152 ans d'observations continues, ce n'est pas mal du tout[#2] : il y a bien quelques jours qui manquent ou sont incomplets[#3] ou douteux (725 jours au total depuis 1873, le plus récent en 1936), et je suppose qu'il faut interpréter ces anciennes observations avec une certaine prudence, mais ça doit néanmoins être une source très précieuse pour les historiens, et en tout cas c'est très rigolo pour faire joujou avec. Faire joujou est exactement ce que je me propose de faire dans ce billet.

[#2] Ce n'est pas le plus ancien relevé que Météo France ait dans son jeu : il y a des températures mesurées à l'Observatoire de Paris qui remontent à 1816 (par exemple, on y apprend que les températures relevées pour le 29 juillet 1830 étaient de 20.5°C pour la minimale et 31.0°C pour la maximale, et que c'était la journée la plus chaude de ce mois-là). Mais le jeu pour Paris Montsouris a l'air d'être le plus complet qui soit.

[#3] Dans certains raisonnements mathématiques que je vais tenir ci-dessous, je vais faire comme s'il n'y avait pas ces lacunes. Il faut donc les prendre avec des pincettes (enfin, les raisonnements sont corrects, mais leur applicabilité est parfois sujette à caution). J'essaierai quand même de le resignaler de temps en temps.

☞ J'aime faire joujou avec des jeux de données

J'ai déjà dû écrire quelque part (et peut-être qu'un jour je ferai un billet entièrement sur le sujet) que j'aime beaucoup jouer avec des jeux de données : faire des stats dessus, tracer des graphes, chercher des corrélations, regarder les extrêmes, les moyennes, les écarts-types, ce genre de choses. Beaucoup de gens feraient ça avec un tableur, d'autres avec Python, moi personnellement je préfère Perl et Gnuplot[#4], mais peu importe.

[#4] J'aime bien Perl parce qu'il est vraiment efficace pour écrire du code qui lit des fichiers textes, et il a l'avantage important à mes yeux sur Python que je peux écrire directement en ligne de commande un one-liner comme perl -F';' -ane 'if ($F[0] eq "75114001" && $F[8] ne "" && $F[12] ne "" && $F[9]==1 && $F[13]==1 && $F[5] ge "18730101") { $med = ($F[16] ne "" && $F[17]==1) ? $F[16] : ($F[8]+$F[12])/2; print "$F[5]\t$F[8]\t$med\t$F[12]\n"; }' Q_75_1816-1949_RR-T-Vent.csv Q_75_previous-1950-2023_RR-T-Vent.csv Q_75_latest-2024-2025_RR-T-Vent.csv > paris-temps.dat sans avoir besoin d'ouvrir un script, de lui trouver un nom, d'indenter chaque ligne précisément comme Python le veut. Et l'avantage de mettre ça directement en ligne de commande c'est que souvent je mélange avec d'autres outils Unix (egrep, sort, awk, cut, tail, etc.) en enfilant les pipes. Par rapport à un tableur, l'avantage est surtout que n'ai pas besoin de refaire plein de manips répétitives à la souris. Pour ce qui est de Gnuplot, en revanche, je ne le recommanderais pas du tout, c'est assez merdique (l'édition de ligne de commande est complètement cassée, donc en fait je me retrouve à faire des echo machin | gnuplot complètement stupides) et c'est plutôt l'inertie qui me fait continuer à m'en servir.

J'avais fait en 2023 quelque chose d'un peu sérieux pour l'analyse des températures moyennées sur toutes la France depuis 1950 (telles qu'extraites de la réanalyse ERA5). Mais le but de ce billet est moins de parler des températures elles-mêmes (c'est plutôt un prétexte) que de parler de la notion de maximum et de minimum, qui est un des concepts mathématiques les plus simples qui soient, mais qui peuvent déjà servir d'illustration de comment un mathématicien pense le monde (cf. ce que j'écrivais dans ce billet). Et je vais en profiter pour (sans doute mal) vulgariser le théorème du minimax de von Neumann. Mais l'idée est surtout de m'amuser avec tout ça (i.e., comme le titre l'indique, ce billet n'a aucun intérêt si ce n'est de me distraire).

❦

☞ Maximales, minimales et moyennes

Bon, la température maximale ou minimale sur une journée, ou sur une année, ou sur une longue période, je pense que tout le monde comprend ce que ça veut dire.

La température moyenne, c'est déjà un petit peu plus compliqué. Historiquement, la température moyenne sur la journée est estimée comme la moyenne entre le maximum et le minimum (je veux dire, ½·(maximum+minimum)), parce que ce n'est pas évident d'avoir un instrument qui mesure ou calcule la moyenne. Mais plus récemment (depuis 1950, on dirait ?), on s'est mis à enregistrer dans les relevés météos une vraie moyenne calculée, je crois, heure par heure (c'est encore une approximation de ce que serait une moyenne calculée de façon continue, mais c'est déjà beaucoup mieux). Il y a une parfois certaine confusion dans les jeux de données entre les deux ; et c'est déjà un premier signe d'un esprit mathématique que de comprendre la différence entre les deux et d'imaginer immédiatement à quoi ressemble une situation où elles vont différer significativement (par exemple, un pic de chaleur bref mais intense dans la journée va augmenter significativement la maximale mais beaucoup moins la vraie moyenne, donc la demi-somme ½·(maximum+minimum) sera plus élevée que la moyenne). Sur une plus longue période, la différence est moins importante.

Je précise donc que dans ce que j'utilise ci-dessous comme moyenne, c'est la moyenne rapportée par Météo France s'il y en a une, et, sinon, faute de mieux, c'est juste la demi-somme ½·(maximum+minimum) (et donc, en gros, ça semble changer en 1950).

Bref, si je dis quelque chose comme le maximum jamais enregistré à Paris Montsouris est de 42.6°C le 2019-07-25 (vers 14h30), le minimum jamais enregistré y est de −23.9°C au matin du 1879-12-10 ou la moyenne sur toute la période allant du 1873-01-01 au 2025-06-25 est de 11.5°C, je pense que tout le monde comprend bien.

☞ Maxima de minima et minima de maxima

Ça devient déjà plus compliqué si je parle de maximum du minimum ou de minimum du maximum. Par exemple : la plus haute minimale quotidienne enregistrée à Paris Montsouris est de 25.5°C le 2003-08-12 (vers 5h10), la plus basse maximale est de −10.5°C le 1938-12-20. Il s'agit là d'un maximum (sur la période) des minima (sur la journée), et d'un minimum (sur la période) des maxima (sur la journée). Concrètement, les gens penseront au maximum des minima comme la nuit la plus chaude, mais entendons-nous bien, il ne s'agit pas d'une moyenne sur la nuit, il s'agit du point le plus froid de la journée (qui se trouve être au petit matin), et ensuite on cherche dans la période considérée la journée où ce minimum est le plus élevé.

L'idée est donc de parler ici de ce qui se passe quand on combine des minima, des moyennes et des maxima, de « toutes les manières possibles », et mon jeu de températures est juste un prétexte pour faire ça.

On peut y penser comme un tableau à deux entrées : une entrée (disons, la colonne) est l'heure du jour, et l'autre (disons, la ligne du tableau) est le jour dans la période. On cherche alors le minimum ou le maximum, ou d'ailleurs la moyenne, de chaque ligne et ensuite le maximum, le minimum, ou d'ailleurs la moyenne, de ces nouvelles valeurs. Ça nous fait neuf valeurs différentes.

Mais comme la météo a deux cycles naturels, le jour et l'année, il est en fait plus logique de considérer trois paramètres : l'année, le jour de l'année, et l'heure du jour. Et comme sur chaque paramètre on peut considérer le maximum, le minimum, ou la moyenne, ça fait 3×3×3 = 27 valeurs distinctes. Pour être bien clair, pour l'instant, je parle de prendre le maximum ou minimum ou la moyenne de la température sur la journée (i.e., sur les heures de la journée), puis de prendre le maximum ou minimum ou la moyenne de ces valeurs sur l'année (i.e., sur les jours de l'année), puis de prendre le maximum ou minimum ou la moyenne de ces valeurs-là sur l'ensemble de la période (i.e., sur les années de la période). Je parlerai après de ce qui se passe si on change l'ordre des opérations.

Bon, là il y a un petit point qu'il faut que j'évoque, c'est comment on découpe les jours et les années. Les jours, on les découpe de minuit à minuit, c'est assez naturel. C'est aussi raisonnable pour faire de la météo, parce que ni le minimum ni le maximum ne vont typiquement se produire près de minuit (enfin, c'est rare, même si ça peut arriver quand une nuit fraîche suit une nuit très chaude, si bien que le minimum sur 24h serait au début de la nuit suivante). [Correction (2025-06-30T09:45+02:00) : on me fait remarquer que ce n'est pas vraiment ça : le minimum et le maximum sont calculés sur des intervalles décalés, le minimum entre 18h la veille et 18h le jour nommé, et le maximum entre 6h le jour nommé et 6h le lendemain : cf. ce document.]

Pour l'année, en revanche, commencer au premier janvier est une mauvaise idée, parce que le minimum sur un hiver peut facilement se produire soit en décembre soit début janvier, et il sera alors artificiellement rattaché soit à l'année N−1 soit à l'année N. (Les saisons météorologiques commencent par convention en mars, juin, septembre et décembre.) J'ai choisi de découper au premier septembre, comme ça ça colle à la fois à des saisons météorologiques mais aussi plus ou moins au calendrier universitaire ; le choix du premier décembre se serait sans doute aussi justifié. Bref, mes années vont du premier septembre au 31 août, et je rattache, par exemple, le 20 décembre 1938 (plus basse température maximale observée à Paris, cf. ci-dessus) à l'année 1938–1939 (celle qui va du 1938-09-01 au 1939-08-31 inclus). Dans tout ce qui suit, sauf précision du contraire, quand je parle d'années, ce sont ces années de septembre à août.

☞ 27 combinaisons

Ceci étant dit, voici les 27 combinaisons possibles de minima, moyennes et maxima (je vais commenter cette table après) :

(Si vous préférez une version texte brut, elle est ici. Quant aux records individuels par année, ils sont là.)

[Lire la suite…]

Méta : Contrairement au précédent qui prétendait être de la vulgarisation (avec quel succès je ne sais pas), le présent billet s'adresse aux personnes qui ont déjà une certaine familiarité avec la calculabilité. (En gros, les prérequis sont les mêmes que dans ce billet ou celui-ci ou celui-là, qui sont sur des sujets proches : je suppose que les notions, disons, de machine universelle ou de codage de Gödel sont connues, et c'est préférable si la notion de machine avec oracle est aussi familière, même si je vais la redéfinir ci-dessous. Les billets que je viens de citer et celui-ci peuvent se lire indépendamment et dans n'importe quel ordre, mais ils devraient s'éclairer mutuellement puisque tout ceci tourne autour des mêmes questions.)

Désolé, donc, pour les gens qui espéraient un billet non technique et qui voient de nouveau de la calculabilité (surtout que j'ai mis beaucoup de temps à le publier parce que j'avais plein de choses à faire), mais j'ai compris quelque chose, là, et il est très utile pour moi de le coucher par écrit pour m'en souvenir ultérieurement.

[Lire la suite…]

Méta : J'étais initialement parti pour écrire un billet sur la calculabilité d'ordre supérieur (il aurait eu pour titre calculabilité d'ordre supérieur : comment un programme peut-il interroger un autre programme ?). Mais en commençant à écrire l'introduction pour la rendre aussi compréhensible que possible, je me suis dit que, tant qu'à faire, ce serait plus intéressant d'essayer de faire un billet autonome sur les bases de la calculabilité, en cherchant à le rendre à peu près accessible au grand public[#]. Après tout, ce sont des notions que j'enseigne à Télécom Paris, ça peut être intéressant d'essayer d'isoler, de façon moins mathématique, les messages principaux que j'essaie de communiquer aux étudiants.

[#] La notion de grand public est, évidemment, assez mal définie. Par exemple, on m'a affirmé que si je fais une phrase avec une subordonnée, l'immense majorité des gens ne savent plus lire. Bon, c'est peut-être vrai, mais je pense que de toute façon cette immense majorité ne sera en aucun cas intéressé par faire l'effort de concentration minimal pour comprendre une tentative de vulgarisation d'un sujet scientifique, même si cette vulgarisation est optimalement faite ; et de toute façon, elle ne lira jamais mon blog vu que, même sur un sujet qui n'a rien de technique, j'ai tendance à faire des phrases à la Proust. Donc disons que je parle à des gens capables de lire une phrase de plus que quelques mots sans perdre le fil de leurs pensées, et qui acceptent de faire un peu d'efforts de concentration. En revanche, j'essaie de ne présupposer du lecteur aucune connaissance préalable en maths ni en informatique. (Ce n'est pas toujours évident, parce que parfois on utilise un terme technique sans s'en rendre compte, et ça a évidemment pu m'échapper.)

[Lire la suite…]

Comme je l'avais évoqué récemment, je voudrais parler un peu de la théorie mathématique du marchandage coopératif (selon Nash).

Je me suis senti motivé, donc, une fois n'est pas coutume j'ai fait des dessins[#] (en SVG, produits avec TikZ) pour illustrer le billet, j'espère qu'ils aideront à comprendre ce que je raconte.

[#] Désolé si les étiquettes sont en anglais : à l'origine j'ai fait ça pour un petit fil BlueSky (dont ce billet est en quelque sorte la version étendue), et je n'ai pas voulu changer ensuite. Mais accessoirement, je n'ai pas trouvé de traduction française satisfaisante pour le mot settlement : j'ai écrit des choses comme accord négocié (ou point négocié) dans le corps du texte, et c'est long et lourd.

En contrepartie, il faut que je reconnaisse que, comme souvent mais peut-être encore plus que d'habitude, ce billet bordélique souffre du défaut que je ne sais pas bien à quel niveau mathématique je veux me placer : il y a des passages qui ne supposent aucune connaissance mathématique, d'autres où je suppose le lecteur familier avec des notions comme celle de partie convexe, de différentielle, ce genre de choses, et je passe de l'un à l'autre de façon pas super cohérente ; il y a des passages où j'essaie de parler de façon purement géométrique et sans aucun symbole, d'autres où je me suis trouvé obligé à écrire des formules, ce qui gâche un peu l'effort fait pour ne pas en mettre ; parfois je redis la même chose de plein de façons différentes et tout ça est mal séparé. (En plus de ça, j'avais commencé par écrire quelque chose de complètement faux[#2] : j'ai rectifié comme j'ai pu, ce qui a donné naissance à la quatrième partie du billet, mais du coup j'ai dû faire pas mal de repentirs, ce qui a certainement cassé des choses, au moins le fil de mes pensées.) Et puis, comme souvent, il y a plein de notes en bas de paragraphe qui sont destinées à apporter des éclaircissements sur tel ou tel point mais qui, peut-être, rendent la lecture d'autant plus compliquée.

[#2] À savoir que la rentabilité de la défense, que je vais définir ci-dessous, vaut toujours exactement ½, ce qui est manifestement absurde.

Bref, j'espère que c'est quand même assez compréhensible. Les lecteurs non mathématiciens peuvent sans doute sauter les passages où il y a des calculs ou des démonstrations, on doit pouvoir tirer quelque chose du reste. (La question de savoir si ce quelque chose est vraiment intéressant, en revanche, est laissé en exercice au lecteur.)

Pour ceux qui veulent une description mathématiquement plus précise que cette sorte de vulgarisation bâtarde, je renvoie principalement à l'article de Nash de 1953 Two-Person Cooperative Games (qu'on pourra aussi trouver ici), ainsi qu'à un plus ancien, The Bargaining Problem, mais aussi, par exemple, le livre de Damme, Stability and Perfection of Nash Equilibria (Springer 1991), chapitre 7 ; ce sont là mes sources essentielles pour ce que je raconte.

[Lire la suite…]

Ce billet de blog a essentiellement comme seule raison d'être de porter un lien, que voici : feuilles de TD d'Algèbre II à l'ENS en 2004–2007. Il faut bien que je lie cette page quelque part, sinon Google ne va pas tomber dessus ; or la structure de mon site Web est complètement inexistante (il n'y a rien qui ressemble à une table des matières ou à un plan du site cohérent, c'est vraiment trop difficile à faire et surtout à maintenir dans le temps, je n'y arrive pas, c'est bien pour ça que j'ai commencé à tenir un blog, pour ne plus avoir à me préoccuper de ces questions), donc ce billet sert juste à créer ce lien.

Mais puisque j'y suis, racontons un peu l'histoire derrière ce lien.

Comme je l'ai raconté dans l'autobiographie mathématique que j'ai écrite récemment, j'ai été agrégé-préparateur (ou comme on le dit dans le jargon de la maison, caïman) à l'ENS de septembre 2004 à l'été 2007. À part gérer la préparation des normaliens à l'agreg de maths, ma principale charge d'enseignement dans cette fonction était d'assurer les travaux dirigés du cours d'Algèbre II, lequel était assuré par Marc Rosso de 2004 à 2006, puis par Bernhard Keller en 2006–2007, et qui portait sur des sujets tels que : anneaux, modules, produits tensoriels, extensions de corps, théorie de Galois, polynômes et divers sujets apparentés. J'ai donc rédigé des feuilles d'exercices, toujours intégralement corrigées (et j'ai d'ailleurs fait ma propre classe LaTeX pour les écrire, et produire systématiquement la double version avec et sans corrigés ; cf. notamment ce vieux billet) ; et j'ai mis ça en ligne, non pas sur mon site personnel (celui-ci), mais sur ma page professionnelle à l'ENS (à l'adresse http://www.dma.ens.fr/~madore/algebre2/), parce que je voulais un peu séparer les choses.

Et autant je fais énormément d'efforts pour préserver la stabilité des liens Web sur ce site-ci, autant s'agissant d'un site professionnel je suis beaucoup moins soigneux, l'argument (assez fallacieux, certes) étant que ce n'est pas moi le webmaster.

Or en 2008 ou 2009, l'ENS m'a fermé mon compte informatique (et a notamment cassé l'adresse mail @ens.fr que j'utilisais depuis 1996). De façon fort cavalière et sans vraiment prévenir, d'ailleurs, ce qui m'a mis assez en colère. Donc le lien en question a cassé, et comme je n'avais aucun moyen de le réparer, que j'étais plutôt fâché et que j'avais autre chose à faire, j'ai laissé filer.

Mais il est aussi vrai que j'étais persuadé, et c'était à tort, que la Wayback Machine de l'Internet Archive avait archivé la page, donc je me disais que les gens intelligents seraient assez grand pour aller chercher la version archivée. Or ce n'était que partiellement vrai : la Wayback Machine avait certes archivé la page index, mais (presque ?) aucune des feuilles de TD en PDF qui sont liées depuis elle et qui constituent, justement, le contenu intéressant à sauvegarder. Donc ce contenu a disparu du Web, ce qui est justement le genre de choses que je n'aime pas du tout.

Correction partielle : Juste après avoir publié ce billet, je m'aperçois que les choses sont un peu plus compliquées que je croyais, parce que l'adresse http://www.dma.ens.fr/~madore/algebre2/ a été renommée en http://www.math.ens.fr/~madore/algebre2/ à peu près à ce moment-là, et la Wayback Machine s'en est mieux tirée sur celle-ci ; donc en fait les documents n'avaient pas autant disparu que je croyais, et ça faisait en fait moins de 16 ans que les liens ne marchaient plus. (Reste que ceci est un exemple intéressant du fait que même avec une redirection propre, changer d'URL pose problème : ça complique les choses quand, bien des années plus tard, on essaie de retrouver les documents sur l'Archive.)

Et c'est particulièrement con parce que non seulement je n'aime pas que l'information disparaisse, mais en plus, je pense qu'il y a dans ces feuilles de TD des exercices vraiment intéressants, beaucoup d'entre eux sont d'ailleurs originaux (soit je les ai imaginés moi-même soit, au moins, je les ai reformulés à ma façon) et j'en étais assez content. Et je crois que les normaliens (enfin, au moins certains normaliens) les appréciaient assez.

Ils sont généralement assez auto-contenus. Bien sûr, ils font appel aux notions mathématiques sur lesquelles portait le cours, mais je ne pense pas qu'ils fassent appel aux détails des définitions données dans le cours, donc on doit pouvoir les utiliser indépendamment du cours.

Et il n'y a pas beaucoup d'autre endroit où vous trouverez des explications sur, par exemple, comment calculer le groupe de Galois de polynômes tels que t⁸ – 8⁢t⁶ + 7⁢t⁴ + 5⁢t² – 3 et t⁸ – 4⁢t⁶ – 8⁢t⁴ + 11⁢t² + 9 et t⁸ + 6⁢t⁶ – 2⁢t² – 3 (oui, il y a des vrais calculs avec des vrais nombres) sur ℚ — ils sont tous les trois d'ordre 192, mais ils ne sont pas isomorphes ; je pense qu'on ne comprend vraiment la notion de groupe de Galois que quand on commence à mettre un peu les mains sur de tels exemples (les détails sont dans cette feuille-ci ; bon, ceux-là sont peut-être un peu tarabiscotés, mais je pense que comparer le groupe de Galois de ℚ(√(2+√5)), de ℚ(√(2+√2)) et de ℚ(√(2+√3)) et se rendre compte qu'ils sont différents et comprendre pourquoi, est vraiment éclairant : pour ça, voyez cette feuille-ci).

(Idéalement, il faudrait recycler ces exercices dans un livre. Un copain m'a proposé de coécrire un tel livre, et nous en avons pondu un certain nombre de pages, mais le travail progressant à une cadence logarithmique, s'il est fini un jour ce sera quand nous serons à la retraite (cf. la note #77 de ce billet). Don't hold your breath.)

Bref, après 16 ans d'absence du Web (mieux vaut tard que jamais…), ces documents sont revenus en ligne, et cette fois-ci je me suis bien assuré que l'Internet Archive garde une copie des PDF.

Reste à voir si je peux faire rétablir le lien http://www.dma.ens.fr/~madore/algebre2/ et/ou http://www.math.ens.fr/~madore/algebre2/ et obtenir que quelqu'un le redirige vers cette nouvelle adresse. Comme je connais quelqu'un qui est sysadmin à l'ENS, les chances dans ce sens sont bien meilleures qu'en 2009. • Mise à jour (2024-12-05T19:23+01:00) : c'est fait, donc les liens anciens doivent de nouveau marcher.

Tant que j'y suis, et sans rapport avec ce qui précède, un autre lien que j'aimerais faire rediriger vers mon site Web, c'est http://www.eleves.ens.fr:8080/home/madore/ (qui était l'ancienne adresse de ce site jusqu'en avril 2005, et qui eut fonctionné comme redirection — au moins par intermittence — jusque vers 2021 ; notez que la version sans le :8080 fonctionne). Je crois comprendre que la responsabilité en appartient à un groupe de normaliens appelés la DGNUM, mais je n'ai pas réussi à les contacter : si par hasard il y a parmi mes lecteurs des gens qui connaissent, n'hésitez pas à nous mettre en contact.

Comme le billet que j'ai écrit il y a un mois sur le métier de mathématicien a suscité un certain intérêt, je me dis que je pourrais en faire un autre sur mon histoire personnelle, i.e., comment j'en suis venu, moi, à faire des maths. J'en ai dit un peu dans mon autobiographie générale mais ce texte a été écrit il y a plus de 20 ans et je ne suis pas forcément très content de la manière dont il est tourné par le David-Madore-de-2003, et par ailleurs il me semble que c'est plus intéressant de raconter les choses thématiquement : voici donc une tentative d'« autobiographie mathématique », de la petite enfance au présent.

Avant de commencer, je dois préciser que je ne prétends ni être typique ni être exceptionnel parmi les mathématiciens. Ceci est mon histoire, ou plus exactement la manière dont je vois (actuellement) mon histoire, elle ne représente que moi, et on se gardera bien d'en tirer des conclusions sur la manière dont on peut ou doit devenir mathématicien (ou pousser un enfant à devenir mathématicien), ni sur le parcours de qui que ce soit d'autre que moi. À l'inverse, je ne prétends pas non plus à une singularité particulière : par exemple, je ne suis sans doute ni un mathématicien exceptionnellement doué ni exceptionnellement mauvais selon quelque mesure de compétence que ce soit, ni même exceptionnellement éclectique (meme si sur cette dimension-là je suis probablement à plus d'un écart-type de la moyenne). Il y a par ailleurs beaucoup de points dans cette histoire où j'ai simplement eu de la chance (soit de la chance de connaître les bonnes personnes, soit de la chance simplement du hasard du moment), et ces choses ne sont simplement pas reproductibles.

(Comme mon autre billet, ce billet est censé être lisible par le grand public, même s'il est certainement plus intéressant si on a au moins une petite idée de la manière dont les mathématiques se découpent disciplinairement. Mais il est assez inévitable que je fasse ici et là des remarques d'ordre un peu plus technique : le lecteur qui ne les comprend pas n'a qu'à sauter ces passages, il n'y aura pas de questions dessus à l'examen.)

[Lire la suite…]

Ce billet s'adresse au grand public et se veut donc compréhensible par tous[#]. Je vais parler de maths, pour une fois il ne s'agit pas de faire de la vulgarisation mathématique[#2] au sens où je ne vais pas expliquer du contenu mathématique, mais plutôt tenter de parler de « ce que ça fait de faire des maths », i.e., essayer de dire un mot sur comment les mathématiciens « pensent » les maths et en quoi consiste notre métier. Et peut-être en profiter pour dissiper quelques malentendus ou quelques idées reçues sur les mathématiciens ou la recherche en mathématiques.

[#] À l'exception de quelques brefs passages essentiellement limités aux notes en bas de paragraphe (où je ferai parfois référence à un concept technique), passages que je pense qu'on n'aura aucune difficulté à identifier et à ignorer si on ne les comprend pas.

[#2] Ni même de la méta-vulgarisation comme j'ai pu le faire ici, mais ça va rejoindre un peu certaines choses que je raconte dans ce billet.

Il va de soi que ce but est trop ambitieux pour que je puisse le mener avec succès. D'abord parce que tenter de parler de comment on fait des maths sans parler de maths revient, forcément, à brasser de l'air en agitant les mains. Ensuite, parce qu'il n'y a pas vraiment de pratique « typique » du métier de mathématicien (comme il n'y a pas de pratique « typique » de celui d'écrivain), donc je peux au mieux parler de la mienne (donc celle d'un mathématicien possiblement médiocre) en essayant de faire remarquer ce que je crois être plus ou moins partagé par mes collègues. Enfin, parce que j'avais de toute façon trop de choses à dire et que j'ai arrêté un peu quand j'en avais marre d'écrire, donc je relègue plein de choses (sur la communauté mathématicienne, notamment) à un éventuel billet ultérieur.

[Lire la suite…]

Le Docteur No, célèbre[#] pour capturer des mathématiciens et les soumettre à diverses énigmes (précédemment sur ce blog : ici, là, là, là, là et peut-être là) est de retour ! Cette fois-ci il n'a capturé que deux mathématiciens, que nous allons appeler Alice et Bob, mais cela ne l'empêche pas de s'amuser à leur proposer une énigme particulièrement cruelle.

[#] Honnêtement, je ne me rappelle même plus si c'est moi qui ai commencé à appeler Docteur No (comme dans le film de James Bond) le grand méchant de ces énigmes ou si je tiens ça d'ailleurs.

Comme ça fait longtemps que nous n'avons pas eu affaire au Docteur No, je commence par une version jouet de l'énigme, histoire de s'échauffer :

Énigme facile : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Après avoir permis à ceux-ci de se concerter sur leur stratégie, il va les soumettre à son épreuve dont il leur communique les termes. Il communiquera deux entiers naturels de son choix à Alice. Alice choisira un et un seul de ces nombres et ce nombre sera transmis à Bob (qui est l'allié d'Alice). Le but de Bob est de deviner le nombre qu'il n'aura pas reçu : pour ça, il aura droit de proposer un nombre fini quelconque d'essais ; autrement dit, il doit proposer au Docteur No un ensemble fini d'entiers naturels (on peut supposer, cela ne change rien, que le nombre transmis par Alice est aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seront libérés ; dans le cas contraire, le Docteur No les tuera avec des tortures particulièrement raffinées.

Comment Alice et Bob font-ils pour être certains d'être libérés ?

La réponse est facile, mais je recommande de prendre le temps de résoudre ce problème avant de passer à la suite (cliquez ici pour la faire apparaître), ne serait-ce que pour vérifier qu'on a bien compris la nature du problème. La réponse est la suivante : Alice communique à Bob le plus grand des nombres qu'elle a reçus, et Bob, recevant ce nombre x, propose l'ensemble (fini) de tous les entiers naturels entre 0 et x ; comme x est le plus grand, l'autre nombre est forcément dans cet ensemble.

Il va de soi que cette solution fonctionne encore si, au lieu que les nombres proposés par le Docteur No soient des entiers naturels, ce sont des entiers relatifs ou des rationnels, car il suffit de coder ceux-ci par des entiers naturels (mais attention, dans la construction ci-dessus, on n'utilisera plus le plus grand nombre, mais le nombre ayant le plus grand code). Mais qu'en est-il pour des nombres réels ?

Contre-énigme : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Il envisage de les soumettre à l'épreuve suivante. Après leur avoir permis de se concerter sur leur stratégie, il communiquerait deux réels de son choix à Alice. Alice devrait choisir un et un seul de ces nombres et ce nombre serait transmis à Bob (qui est l'allié d'Alice). Le but de Bob serait de deviner le nombre qu'il n'aura pas reçu : pour ça, il aurait droit de proposer un nombre fini quelconque d'essais ; autrement dit, il devrait proposer au Docteur No un ensemble fini de réels (on peut supposer, cela ne change rien, que le nombre transmis par Alice est aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seraient libérés ; dans le cas contraire, le Docteur No les tuerait avec des tortures particulièrement raffinées.

Pourquoi le Docteur No, dont le code de l'honneur exige qu'il y ait toujours un moyen de résoudre les épreuves qu'il propose, décide-t-il de ne pas proposer cette épreuve ?

C'est que l'épreuve en question serait impossible : cliquez ici pour voir la preuve. En effet, supposons par l'absurde qu'Alice et Bob aient une stratégie, et considérons la réunion Z de toutes les réponses que ferait Bob si Alice lui transmet un entier naturel (y compris les entiers naturels eux-mêmes) : ce Z est dénombrable (comme réunion dénombrable d'ensembles finis), donc il existe un réel qui n'est pas dedans ; soit donc x un réel qui n'est pas dans Z. Maintenant, si y est un entier naturel quelconque, alors si le Docteur No propose {x,y} à Alice, elle doit forcément transmettre x à Bob, car (sinon) en réponse à y celui-ci répondrait avec une partie finie de Z, qui ne contient donc pas x, et ce serait un échec. Donc la réponse de Bob si Alice lui transmet x doit contenir y, et ce, quel que soit l'entier naturel y. Or aucun ensemble fini ne peut contenir tous les entiers naturels, ce qui est une contradiction.

Le Docteur No doit donc rendre son énigme un peu plus facile. Voici comment il envisage de le faire :

Énigme sur les réels : Le Docteur No a capturé deux mathématiciens, Alice et Bob. Il envisage de les soumettre à l'épreuve suivante. Après leur avoir permis de se concerter sur leur stratégie, il communiquerait trois réels de son choix à Alice. Alice devrait choisir deux de ces nombres et ces nombres seraient transmis (dans un ordre non spécifié) à Bob (qui est l'allié d'Alice). Le but de Bob serait de deviner le nombre qu'il n'aura pas reçu : pour ça, il aurait droit de proposer un nombre fini quelconque d'essais ; autrement dit, il devrait proposer au Docteur No un ensemble fini de réels (on peut supposer, cela ne change rien, que les nombres transmis par Alice sont aussi mis dedans). Si les nombres initialement choisis par le Docteur No sont dans cet ensemble proposé par Bob, alors les mathématiciens seraient libérés ; dans le cas contraire, le Docteur No les tuerait avec des tortures particulièrement raffinées.

Le Docteur No est perplexe quant à la difficulté de cette épreuve et demande conseil à Georg Cantor (qui est emprisonné dans son donjon). Que lui répond Cantor ?

[Lire la suite…]

Je continue ma série d'introduction aux mathématiques constructives en parlant d'entiers naturels, de suites et de « principes d'omniscience ». Ce billet est la continuation de celui-ci, qu'il n'est pas forcément nécessaire d'avoir intégralement lu mais auquel je renvoie au moins pour l'avant-propos expliquant de quoi il est question (je renvoie aussi à ce billet plus ancien pour une explication générale et historique à ce que sont les maths constructives).

[Lire la suite…]

[Lire la suite…]

Le théorème de Desargues, que je veux présenter ici, est à la fois un des plus simples et selon moi un des plus jolis et des plus importants de la géométrie plane. Simple, parce qu'il n'est question que de points et de droites (pas de distances, d'angles, de cercles ni de quoi que ce soit du genre, même pas de parallélisme ou de perpendicularité : on dit que c'est un théorème de « géométrie projective »), et parce qu'il n'y a qu'un petit nombre de points impliqués (c'est quasiment le plus simple possible). Joli pour les raisons que je vais essayer d'expliquer, qui tiennent largement à sa symétrie. Et important parce qu'il est un des axiomes de certaines présentations de la géométrie projective. Pourtant, il ne fait pas du tout partie de l'enseignement de la géométrie en France (certainement pas à l'école primaire, mais pas non plus au collège, ni au lycée, ni même dans les classes préparatoires aux grandes écoles). Je vais essayer de parler un peu[#] de ce théorème, et de la « configuration » de points et de droites qu'il définit, en faisant plus d'efforts que d'habitude pour rester compréhensible par le grand public, au moins au début de ce billet, quitte à reléguer des considérations plus techniques en appendice. (Vais-je pour autant arriver à être compréhensible ? à vous de me dire.) En plus, pour changer des billets de ce blog qui sont généralement du pur texte, vous aurez droit à des illustrations, qui, j'espère, rendent les choses plus compréhensibles ! (Que demande le peuple ?) Notez que vous pouvez cliquer sur n'importe laquelle de ces images pour l'agrandir (et comme elles sont quasiment toutes vectorielles, vous pouvez utiliser quelque chose comme control-+/control-− dans votre navigateur pour zoomer ou dézoomer).

[#] Enfin, un peu est une façon de parler, parce que j'ai passé un temps totalement déraisonnable à écrire ce billet (ce qui explique, comme souvent, que la fin soit sans doute un peu bâclée parce que j'en ai eu vraiment marre).

[Lire la suite…]

J'avais expliqué il y a quelques mois que je m'étais engagé à monter un nouveau cours d'informatique théorique (ou faut-il dire de maths de l'informatique ?) pour certains élèves de première année à Télécom PlusÀParis, intitulé Logique et Fondements de l'Informatique (nom de code interne : INF110). (J'avais d'ailleurs publié un premier jeu de transparents dans de billet.) L'occurrence 2023–2024 de ce cours a eu lieu de mi-novembre (2023) à mi-janvier (2024), le contrôle le 26 janvier, et maintenant (enfin, quelques mois après) que j'ai à la fois rendu les notes finales et reçu les retours (anonymes) des étudiants je suis en mesure d'en faire un premier bilan. L'idée de ce billet n'est pas tellement d'entrer dans le fond du sujet (même si je ne peux pas ne pas en parler du tout), à ce sujet voir plutôt les deux paragraphes ci-dessous, mais de parler au niveau méta : pourquoi ce cours, pourquoi ce sujet, comment je l'ai organisé et préparé, ce qui a bien marché et ce qui n'a pas bien marché. Le but est de me permettre à moi-même de faire le point, et donc de réfléchir à ce que je veux changer l'an prochain, et aussi de préparer un exposé où je dois raconter tout ça (cf. la fin du présent billet).

☞ Pour le fond du sujet, je renvoie notamment à ce billet sur la correspondance de Curry-Howard et à celui-ci sur la réalisabilité propositionnelle, qui sont largement adaptés de certains bouts de mon cours, même si la présentation est différente et qu'ils vont plus loin (surtout le second). Je peux aussi renvoyer à ce billet sur des sujets variés en vrac sur lesquels j'ai appris des choses en préparant ce cours. Enfin, je fais un lien vers ce billet sur les degrés de Turing et leur généralisation parce qu'il touche à des questions adjacentes, même si je n'ai pas fait plus qu'évoquer la définition de degré de Turing (ordinaire) dans mon cours.

☞ Pour ce qui est des documents pédagogiques accompagnant le cours, voici quelques liens (dont, malgré ma passion pour la stabilité des URL, je ne garantis pas qu'ils seront pérennes, parce que je ne sais pas comment je vais les réorganiser à l'avenir). D'abord le PDF des transparents (qui est la concaténation idiote de trois parties inégales : ① calculabilité, ② typage simple et calcul propositionnel et ③ introduction aux quantificateurs ; j'ai aussi fait une version « imprimable » des transparents : ①, ② et ③). Les exercices d'entraînement sont : ici sans corrigé et ici avec corrigé. Et le sujet du contrôle est ici sans corrigé et ici avec corrigé. Et si des gens sont intéressés par le source de tout ça, le dépôt Git est ici.

Avertissement usuel : même si j'évoque ici mon travail d'enseignant-chercheur à Télécom, je dois rappeler que, dans ce billet comme ailleurs sur ce blog, je m'exprime à titre purement personnel et que les avis et opinions que je peux exprimer ici (ou ailleurs) sont juste les miens et n'engagent en aucun cas mon employeur (ni qui que ce soit d'autre que moi, et d'ailleurs ils ne m'engagent même pas moi vu que que je me réserve le droit d'en changer à tout moment et sans prévenir). J'ajoute que si vous faites partie des personnes qui ont besoin d'un tel avertissement, il vous est interdit de lire la suite de ce billet.

[Lire la suite…]

Je veux ici de nouveau parler d'informatique théorique, dans son intersection avec les maths (logique, calculabilité, typage), et plus précisément d'un sujet appelé la réalisabilité propositionnelle. Je reconnais qu'il a un petit côté « opération de pub » de ma part : il s'agit d'un sujet qu'on peut qualifier d'obscur, voire ésotérique (largement confiné à une poignée de publications soviétiques des années 1960–1990, dont certaines n'ont même pas été traduites du russe en quoi que ce soit d'autre[#], ce qui le dessert cruellement), et pourtant il me semble que d'une part il a des choses à nous apprendre sur l'informatique, sur ce que peut ou ne peut pas faire un algorithme, et sur le rapport entre ça et le typage, et d'autre part il n'est techniquement pas très compliqué à exposer (j'en ai dit un mot — bien moins que ce qui va suivre, certes — dans mon cours à Télécom qui s'est récemment fini, et je ne crois pas avoir largué tout le monde). Donc je trouve qu'il mérite plus d'attention.

[#] Bon, le fait que ce soit en russe ne devrait pas être un obstacle sérieux, surtout maintenant qu'on a des OCR et des traducteurs automatiques, il n'y a vraiment plus de raison. Le problème, c'est que souvent, et en plus d'être en russe, l'article a le défaut d'être super mal écrit : extrêmement concis et pas toujours super rigoureux comme les mathématiciens soviétiques avaient tendance à l'être, références vagues, et fautes de frappe à foison. (Voyez par exemple cette question que j'ai posée sur MathOverflow en essayant de comprendre l'argument de Ânkov sur la non-réalisabilité de l'axiome de Scott que j'expose plus bas ici de façon, j'espère, nettement plus clair que le texte original : mon russe est enfoui au fond des oubliettes, mais ce n'est vraiment ce qui était le plus problématique en l'occurrence par rapport aux fautes de frappe et au style de rédaction vraiment minimaliste.)

Je ne sais pas si l'entrée de blog qui va suivre peut aider à convaincre qui que ce soit de s'y réintéresser, mais en tout cas, si on lit ce qui suit on pourra se dire qu'on sait une proportion significative de tout le savoir de l'Humanité sur la réalisabilité propositionnelle (i.e., pas grand-chose !), et il n'y a pas beaucoup de sujets techniques pour lesquels on puisse en dire autant.

Ajout (2024-02-14) : Pour les gens qui veulent savoir de quoi ce billet cause mais qui n'ont pas la patience de lire ce pavé (ni même l'introduction), j'ai écrit un résumé en seulement 13 tweets, ici sur Twitter et ici sur BlueSky [on peut lire le fil BlueSky sans avoir de compte dessus].

[Lire la suite…]

Précisions d'emblée que le but de ce billet, qui évoque le rapport entre (pour prendre un exemple célèbre) un chat vivant avec probabilité ½ et mort avec probabilité ½ (« mélange probabiliste ») et un chat dans un état quantique qui combine vivant et mort (« superposition quantique ») n'est pas vraiment de faire de la vulgarisation, encore moins de la physique. Je m'en sers, comme je fais parfois, surtout pour gribouiller rapidement ce que j'ai (moi matheux) réussi à comprendre de textes que je trouve souvent obscurs, et pour noter des questions que je (me) pose si je veux y réfléchir plus attentivement Un Jour™, mais ça ne signifie pas que d'autres trouveront mes explications plus claires que ce qu'on peut trouver ailleurs. Il s'agit essentiellement de choses très classiques, mais que je trouve généralement très mal expliquées (notamment par le fait qu'on prend rarement le soin d'essayer de décrire le parallèle entre mélanges probabilistes et superpositions quantiques séparément avant de dire comment ces deux choses se combinent), quoique certaines des questions que je soulève au passage n'ont pas l'air d'être beaucoup discutées, et c'est dommage.

Quoi qu'il en soit, ce qui suit s'adresse à des lecteurs qui savent au moins un peu d'algèbre linéaire (en gros, pour qui les mots espace de Hilbert ont un sens — je ne parlerai que de la dimension finie donc on peut préférer espace hermitien), et sont globalement familiers avec le fait qu'une matrice hermitienne est diagonalisable. Et encore une fois, mon point de vue va être celui d'un matheux, pas d'un physicien (témoin le fait que je vais à peine évoquer de lois de la physique) : la question est celle de la représentation mathématique d'états d'un système physique. (Et j'en profite pour pointer du doigts certains faits géométriques sur cette représentation.) Mais au passage, ça soulève des questions, qui me semblent intéressantes, sur la philosophie de la physique (notamment que signifient les probabilités, et dans quelle mesure elles font partie de la réalité du monde).

Je dois aussi préciser que j'ai changé plein de fois d'avis sur ce que je voulais raconter ici, que j'ai fait mon plan a posteriori et que j'ai réécrit plein de fois des passages sans vérifier la cohérence avec ce qui était déjà ailleurs, ce qui explique sans doute des virages un peu bizarres, des redites ou incohérences de propos et des digressions inutiles (comme d'habitude, j'essaie de rédiger de manière à ce qu'on puisse les sauter, mais je ne sais pas dans quelle mesure j'y arrive). Par ailleurs, comme ça m'arrive souvent, j'ai écrit ce texte jusqu'au point où j'en ai eu marre de l'écrire, ce qui explique qu'après être parti dans toutes les directions il s'arrête un peu brutalement et sans vraie conclusion — mais je pense que mes lecteurs (enfin, ceux qui sont assez patients pour lire mes billets jusqu'au bout) ont l'habitude de ça.

[Lire la suite…]

Je voudrais essayer de parler ici d'un concept de géométrie (euclidienne), notamment important pour son application en optique, que je trouve à la fois joli pourtant trop peu connu[#] : celui d'« étendue ». En gros, l'étendue est une façon de mesurer la taille d'un ensemble de droites (disons, dans l'espace) de la même manière que le volume est une façon de mesurer la taille d'un ensemble de points. Mais pour commencer, et pour expliquer une façon dont cette notion apparaît, je veux parler des unités et grandeurs lumineuses que sont le lumen, le lux, la candela et la candela par mètre carré, et le lien entre ces unités, et ce qu'elles nous disent. Parce que même le grand public commence à avoir entendu parler des lumens (c'est écrit sur toutes les boîtes d'ampoules, de nos jours), et peut-être de lux (pour le niveau d'éclairement d'une pièce), mais ne sait pas forcément la différence entre les deux (divulgâchis : un lux, c'est un lumen par mètre carré).

[#] À titre d'exemple, je n'en vois pas de trace dans les programmes de classes préparatoires scientifiques françaises, ce que je trouve un peu surprenant. Et ce n'est pas une évolution récente parce que je ne crois pas qu'on m'en ait parlé quand j'étais moi-même en prépa.

La difficulté de l'exercice, c'est que comme je veux parler de divers concepts (l'étendue en géométrie euclidienne, l'étendue en optique géométrique, les unités de mesure photométriques, et quelques conséquences de tout ça) et ce à différents niveaux de vulgarisation, je mais certainement faire de la bouillie. En plus de ça, je suis infoutu de faire le moindre dessin, ce qui n'aide pas pour expliquer un concept éminemment géométrique.

Mais voilà, essayons quand même (bear with me), parce cette histoire de conservation de l'étendue est quelque chose qui me semble important pour comprendre les bases de l'optique, et c'est aussi un concept mathématique pas compliqué mais néanmoins digne d'être noté. Et j'en ai marre de toujours oublier ces choses, alors ce billet de blog est surtout un aide-mémoire pour moi-même.

*

[Lire la suite…]

Les quelques derniers billets de ce blog qui avaient un contenu scientifique (notamment celui-ci et celui-ci) tournaient autour de l'informatique théorique. (Et je compte en écrire encore plusieurs.) Je ne sais pas si le lecteur non spécialiste aura vu la différence avec des maths. Je ne sais pas si je vois une différence avec des maths. Après tout, j'ai rangé ces billets dans la catégorique « maths » (pas que le mécanisme de catégories sur ce blog serve à quoi que ce soit, et c'est peut-être surtout que j'avais la flemme de créer une nouvelle catégorie, mais quand même, c'est une info) ; alors que par le passé, j'ai écrit des entrées sur la physique théorique (comme celle-ci ou celle-là) et je les ai rangées dans une catégorie différente. Peut-être même qu'avec assez de mauvaise foi on pourrait prétendre que la correspondance de Curry-Howard affirme qu'il n'y a pas de différence entre maths et info (mais soyons clairs, ça demande une bonne dose de mauvaise foi, justement).

Ce n'est pas la première fois que je médite sur cette question à laquelle je n'ai pas vraiment de réponse : qu'est-ce que c'est que l'informatique ? — et secondairement, quelle position a-t-elle par rapport aux maths ? et cette position est-elle analogue à celle de la physique ?

(Je précise que ce billet, qui est une méditation décousue et sans véritable point d'arrivée, se veut non-technique, i.e., lisible par tout le monde, mais que fatalement je vais être amené à faire des remarques techniques çà et là : si on ne sait pas de quoi je parle, on peut juste ignorer ces passages, ils ne sont là que pour appuyer ou illustrer mes propos, ils n'en sont pas le cœur. Si vous n'avez vraiment pas le temps de lire, regardez au moins le dernier paragraphe pour un résumé de ce que j'essaie de dire.)

[Lire la suite…]

Allez, en cadeau de Noël, un deuxième billet à deux jours d'intervalle, ce qui est devenu très rare sur ce blog : je vous propose une devinette dont je posterai la solution ultérieurement. Je la trouve très jolie et surprenante et je pense qu'elle aurait beaucoup plu à Raymond Smullyan.

Méta : Elle m'est venue en réfléchissant à des questions de maths (autour de la réalisabilité propositionnelle). La formulation est de moi, mais c'est en fait une réécriture d'un théorème (de Plisko, je donnerai la référence précise en même temps que la solution) dont j'ai lu l'énoncé et que j'ai reformulé comme une énigme pour y réfléchir parce que je ne voulais pas lire la preuve mais la retrouver moi-même. J'ai eu énormément de mal à la résoudre, donc je pense qu'elle est vraiment dure (d'un autre côté, je n'étais pas sûr d'avoir trouver la bonne formulation, donc je réfléchissais à la fois à la question et à la réponse), mais quand je l'ai présentée sur Twitter, au moins une personne a trouvé la solution, donc elle n'est certainement pas insoluble. Même si elle a un rapport distant avec mon très long billet tout récent sur Curry-Howard (et je compte écrire une autre entrée qui fait référence aux deux, et qui explique l'intérêt mathématique de cette énigme), il n'est pas nécessaire, ni même spécialement utile, d'avoir lu ce billet (ni aucun autre) pour réfléchir à cette énigme. En revanche, il est certainement pertinent d'avoir des notions de calculabilité pour espérer y arriver (même si je vais présenter l'énoncé pour qu'il soit compréhensible sans ça). J'éditerai ce billet d'ici quelques jours pour présenter la réponse ainsi que quelques commentaires : pour l'instant je me contente de l'énoncé de l'énigme, suivi de quelques commentaires.

[Lire la suite…]

Méta : Le présent billet, quoique indépendant, est une sorte de suite de celui-ci où j'exposais quelques points d'informatique théorique que j'ai appris, ou mieux/enfin compris, en enseignant un cours que je crée cette année à Télécom. En fait, j'étais parti pour écrire quelque chose sur un sujet plus spéculatif, mais je me suis dit que pour commencer il fallait que j'explique proprement la correspondance de Curry-Howard, et comme c'est justement une des choses que j'enseigne et que je trouve généralement très mal expliqué, autant en faire aussi une entrée de blog ; puis comme j'étais trop débordé par l'écriture des transparents du cours lui-même, j'ai laissé ça de côté. J'ai de nouveau un petit peu de temps avec les vacances, donc je publie et complète séparément ce bout sur Curry-Howard comme un texte autonome, dans l'espoir de faire ensuite un autre billet sur les questions qui, au-delà de mon enseignement du moment, m'avaient initialement motivé à en parler. Mais comme je tombe dans un trou de lapin dès que je me mets à écrire sur un sujet, j'ai quand même élargi le sujet à des questions connexes.

[Lire la suite…]

Ce que j'aime surtout dans le fait d'enseigner, c'est qu'on apprend souvent soi-même plein de choses sur le sujet qu'on enseigne, surtout la première fois, et surtout si on crée soi-même le programme du cours : on croyait bien savoir les choses de loin, mais être obligé de les regarder de près pour les enseigner oblige souvent à se rendre compte qu'il y avait une subtilité là où on ne le savait pas (ou qu'on avait oubliée) ; ça peut éventuellement conduire à une panique zut, l'approche que je croyais avoir tracée pour ce cours ne marche pas ! comment est-ce que je vais m'en sortir ?, mais souvent on en ressort bien plus compétent qu'avant : même si la subtilité qu'on a découverte, finalement, n'est pas enseignée, l'enseignant sera quand même meilleur (ceci étant, les personnes à qui on enseigne la première fois risquent de moins goûter l'expérience, et il faut parfois quelques années pour que la découverte de surprises se tarisse et que l'enseignant soit rôdé).

Pour prendre un exemple passé précis, en enseignant mon cours de théories des jeux (notez le pluriel à théories !) à Télécom — dont les notes sont ici si ça intéresse quelqu'un — je me suis rendu compte d'une subtilité importante dont je n'avais pas du tout pris conscience avant : quand on parle de stratégie dans un jeu (à information parfaite), on peut soit s'intéresser aux stratégies qui, pour prescrire un coup à jouer, dépendent seulement de la configuration actuelle du jeu (appelons-les stratégies positionnelles), soit de celles, plus générales, qui dépendent de tout l'historique de la confrontation jusqu'à ce point (appelons-les stratégies historiques) ; or, même si la règle du jeu ne dépend que de la configuration actuelle et pas de l'historique qui a mené à cette configuration, ce n'est pas du tout évident a priori qu'une stratégie gagnante dans le sens plus général (historique) soit forcément traduisible en une stratégie gagnante dans le sens plus restreint (positionnel) ; et j'avais un peu paniqué, parce que j'avais construit mon cours autour de la démonstration de l'existence d'une stratégie gagnante dans un sens via la théorie des jeux de Gale-Stewart (qui sont intrinsèquement « historiques »), alors que j'en avais besoin ensuite au sens plus fort (« positionnel ») pour la théorie de Sprague-Grundy. J'ai réussi à m'en sortir (j'ai écrit des notes expliquant correctement le lien, voir la section 3.5 du PDF lié ci-dessus), en cours je demande aux élèves d'admettre ce point en les renvoyant au poly s'ils ne veulent pas l'admettre, donc finalement je n'enseigne pas vraiment cette subtilité, mais j'ai été content d'en prendre conscience, et je suis étonné qu'il soit si peu évoqué, ou si mal expliqué, dans la littérature scientifique sur le sujet.

Même en donnant un cours d'analyse (dont je n'étais, cette fois, pas le responsable ni le créateur, mais simple intervenant) j'ai appris un certain nombre de choses sur le sujet, voyez par exemple ce billet passé pour quelque chose que j'ai appris au détour d'un exercice. Et en donnant un cours d'initiation à la géométrie algébrique, je me rends surtout compte… que c'est très difficile d'enseigner la géométrie algébrique et que je ne sais même pas produire une définition d'un morphisme entre variétés quasiprojectives (l'objet fondamental du domaine, quoi) qui ne soit pas abominable dans sa complication.

Bref. Cette année, comme je l'ai raconté ici et là, j'inaugure un cours intitulé Logique et Fondements de l'Informatique où je dois parler de calculabilité, λ-calcul, logique, typage, isomorphisme de Curry-Howard, ce genre de choses (un programme à vrai dire assez ambitieux, mais on m'a donné comme consigne de profiter de la création de la filière MPI en prépa pour viser quelque chose d'assez sérieux). Des choses, à cheval entre mathématiques et informatique théorique, qui me plaisent beaucoup (sur la calculabilité voyez par exemple ce long billet) et sur lesquelles je pensais ne pas avoir grand-chose à apprendre… Famous last words!

(La suite de ce billet est essentiellement un brain dump de quelques unes des choses que j'ai apprises, réapprises, ou mieux comprises en préparant ce cours jusqu'à présent. Noter que ça ne veut pas dire que je vais les enseigner ! Ou du moins pas forcément sous cette forme. Comme les petits bouts de ce billet, de longueur très inégales, sont assez indépendants, je les ai séparés par des fleurons : si on n'aime pas ce que je raconte à un endroit donné, on peut sauter jusqu'au fleuron suivant.)

❦

Il y a des choses que j'ai apprises en marge de la préparation de ce cours, sans que ça ait vraiment d'impact dessus. Par exemple, comment on fabrique des modèles du lambda-calcul non typé (pour ceux qui veulent en savoir plus là-dessus, j'ai bien aimé l'article From computation to foundations via functions and application: The λ-calculus and its webbed models de Chantal Berline, et notamment la partie sur les K-modèles, qui m'ont semblé les plus parlants de tout cette histoire : de façon très sommaire, on représente un terme par l'ensemble de tous les types qu'on peut lui attribuer dans un certain système de typage dont les types ne sont pas disjoints ; en plus ça semble avoir un rapport avec la réalisabilité, ce qui n'est pas déplaisant) : ce n'est pas spécialement une difficulté que j'ai rencontrée, juste quelque chose que j'ai appris au passage.

❦

Il y a aussi des choses que je pensais savoir sans vraiment y avoir suffisamment réfléchi. Notamment, comment fonctionne au juste le combinateur de point fixe Y de Curry. J'avais déjà appris il y a longtemps que dans un langage fonctionnel non typé on peut faire des appels récursifs sans faire d'appels récursifs, par exemple (en Scheme) :

(define proto-fibonacci
  (lambda (self)
    (lambda (n) 
      (if (<= n 1) n
	  (+ ((self self) (- n 1)) ((self self) (- n 2)))))))
(define fibonacci (proto-fibonacci proto-fibonacci))

— code la fonction définie récursivement[#] par F(n)=n si n≤1 et F(n) = F(n−1) + F(n−2) sinon, sans jamais que la fonction fasse appel à elle-même dans sa définition (c'est, en fait, l'astuce de Quine — qui n'est pas due à Quine, c'est Hofstadter qui lui a donné ce nom-là, mais à Cantor, Gödel, Turing et Kleene — et sur laquelle j'avais écrit une page alors que mes élèves actuels n'étaient même pas nés). L'astuce (de Quine qui n'est pas de Quine), donc, c'est qu'on passe la fonction proto-fibonacci en argument à la fonction proto-fibonacci, et quand elle a besoin de faire appel à elle-même, elle applique son argument (self) en prenant bien soin de lui passer une copie de lui-même, d'où le self self dans ce code.

[#] Oui, je sais que la suite de Fibonacci est un très mauvais exemple de récursion parce qu'en vrai il ne faut pas la coder de façon récursive, c'est épouvantable pour la complexité ; mais c'est un exemple facile à lire, donc je le reprends avec cet avertissement qu'il ne faut pas faire comme ça pour autre chose que pour illustrer les appels récursifs.

Vous noterez bien, donc, qu'il n'y a pas d'appels récursifs dans ce code. La même astuce de Quine permet de faire un programme qui s'écrit lui-même même si le langage ne permet pas de faire référence à lui-même (voyez ma vieille page liée ci-dessus pour tous les détails), à Gödel de fabriquer un énoncé qui dit je suis indémontrable, etc. Ici ça sert à ce qu'une fonction s'appelle elle-même même si le langage ne permettait pas les appels récursifs comme construction spéciale (par exemple en λ-calcul, il n'y a pas de construction récursive).

Ici on est dans un langage fonctionnel donc on peut juste appeler une fonction passé en argument, mais dans un langage non fonctionnel capable d'écrire un interpréteur de lui-même, on pourrait quand même simuler les appels récursifs en lançant l'interpréteur (sur une représentation du code de la fonction !) à chaque fois qu'il est écrit self self dans le code ci-dessus, ce qui est la façon la plus mind-blowing de faire de la récursion, et je ne m'étais pas rendu compte de ça avant de commencer à préparer ce cours.

[Lire la suite…]

La chaîne de télé Arte produit une série de petites vidéos de vulgarisation scientifique (à destination du grand public) sur les mathématiques appelée Voyages au pays des maths (on les trouve ici sur le site web d'Arte ou ici sur YouTube) : je n'en ai regardé qu'une partie (via leur site Web : je ne suis pas tombé dessus à l'antenne, mais c'est juste parce que je n'allume jamais la télé), mais celles que j'ai vues me semblent globalement correctes : il y a parfois des affirmations douteuses ou qui peuvent induire des idées fausses mais je n'ai rien entendu dans celles que j'ai regardées qui me fasse bondir au plafond ; la présentation est plutôt pas mal au sens où j'ai l'impression que tout le monde peut accrocher au moins un peu, et comme chacune dure 10 minutes, même si on n'aime pas, on n'a pas le temps de s'endormir et je pense que ça peut convaincre des gens d'essayer au moins de s'intéresser un minimum au genre de choses sur lesquelles les maths se penchent. (Je peux éventuellement reprocher au choix des sujets, même s'il est agréablement éclectique, de mélanger des choses qui sont des problèmes profonds et difficiles avec des petites curiosités qui ne font pas l'objet de recherches ; ce n'est pas grave en soi, mais il faudrait peut-être mieux expliquer au public ce qui tombe dans chaque catégorie.)

Comme je l'avais raconté dans cette entrée passée de ce blog, je suis moi-même intéressé par la vulgarisation mathématique, pas pour le contenu de ce que ça raconte, mais pour apprendre à améliorer ma propre présentation des choses, qu'il s'agisse de vulgarisation, d'enseignement (ou même d'exposition à des pairs), et à tous les niveaux (du grand public aux chercheurs).

Or il se trouve justement que dans cette série Voyages au pays des maths est paru un épisode intitulé L'Entscheidungsproblem ou la fin des mathématiques ? (visible ici sur le site web d'Arte ou ici sur YouTube) qui porte sur le même sujet — la calculabilité — sur lequel j'ai récemment publié les transparents d'un cours que j'inaugure cette année à Télécom Paris (et aussi un billet qui se veut grand public sur un thème apparenté).

Du coup je suis curieux de savoir comment ce genre de vulgarisation est jugé par le grand public : j'apprécierais si des personnes qui lisent mon blog, surtout celles qui ne sont pas mathématiciennes, idéalement même pas scientifiques, pouvaient regarder cette vidéo de 10 minutes et me dire ce qu'elles en pensent : ce qu'elles en retiennent, si elles ont l'impression de comprendre les enjeux évoqués, quels passages sont clairs, lesquels ne le sont pas, ce genre de choses, et si elles sont d'accord avec mes critiques qui vont suivre.

(Si possible, merci de regarder la vidéo avant de lire la suite pour ne pas se laisser influencer par mes propres remarques qui vont suivre ; et aussi tout bêtement parce qu'elles sont sans doute difficiles à lire si on n'a pas vu la vidéo avant.)

[Lire la suite…]

Comme je le disais il y a un mois, je me suis engagé à organiser à Télécom Paris(PlusÀParis) un cours de Logique et Fondements de l'Informatique où je dois parler de calculabilité, logique et typage. Je suis évidemment complètement à la bourre sur la préparation de ce cours, qui commence vendredi en huit, mais bon, j'ai au moins provisoirement fini d'écrire des transparents pour la partie « calculabilité » qui devrait occuper, je pense, bien 6h de cours (sur 22h au total pour le cours magistral ; il y a des TD/TP à côté). Autant que je rende ça public dès maintenant, des fois que des gens voudraient m'aider à corriger les fautes. Donc :

Ces transparents sont en ligne ici

(Je compte concaténer ceux de la suite du cours quand il seront écrits. Je ne sais pas encore comment je veux diviser ça donc ce n'est pas évident de choisir des adresses intelligemment.)

J'ai à peine commencé à les relire, donc c'est certainement bourré de typos et de fautes plus ou moins graves. J'espère quand même qu'il n'y a pas d'erreur tellement grave qu'elle m'obligerait à tout restructurer.

Si vous faites des commentaires, pensez à me donner l'identifiant Git (en bas du premier transparent) auxquels ils se rapportent. (Au moment où j'écris ce billet, c'est 31080ea Wed Nov 1 11:06:40 2023 +0100 ; l'arbre Git avec le source est ici.)

Il faut préciser que ça s'adresse à des élèves ayant déjà fait de l'informatique en prépa (filière MPI ou filière MP option info, plus quelques uns venus de licences d'info ; les programmes des classes prépa sont ici), donc d'une part ce n'est pas comme s'ils découvraient tout, d'autre part on peut les espérer motivés par le sujet.

Dans cette partie calculabilité, je présente les fonctions primitives récursives et surtout générales récursives, les machines de Turing et le λ-calcul non typé, l'esquisse de l'équivalence entre les trois présentations de la calculabilité (fonctions générales récursives, machines de Turing et λ-calcul non typé), ainsi que divers résultats classiques fondamentaux : théorème s-m-n, théorème de récursion de Kleene, existence d'une machine universelle, résultats élémentaires sur les ensembles décidables (= calculables) et semi-décidables (= calculablement énumérables), et bien sûr l'indécidabilité du problème de l'arrêt (et aussi l'incalculabilité de la fonction « castor affairé »). Dans la suite du cours, il est prévu de parler de λ-calcul simplement typé en lien avec le calcul propositionnel intuitionniste, puis de diverses extensions (logique classique, logique du premier ordre, et évoquer divers bouts du cube de Barendregt). Le fil conducteur du cours est censé être quelque chose comme ceci : L'indécidabilité du problème de l'arrêt signifie que tout langage informatique qui garantit la terminaison des programmes est nécessairement limité ; des systèmes de typage de plus en plus puissants cherchent à rendre cette limitation aussi faible que possible.

J'ai renoncé à parler, même allusivement, de machines avec oracle ou de degrés de Turing ; mais les gens qui veulent en savoir plus sur ce sujet peuvent se référer à ce billet interminable pour lequel les notes ci-dessus suffisent largement en matière de prérequis.

Ajout (2023-11-02) : Suivant ce qu'on m'a fait remarquer en commentaire, j'ai ajouté (Git 1cdc719 Thu Nov 2 17:08:48 2023 +0100) des choses sur le théorème de Rice et les réductions (many-to-one et de Turing). Il est cependant vraisemblable que j'en saute au moins une partie.

Le fait de me replonger dans le λ-calcul non typé, et de vouloir en savoir plus que le minimum que j'enseigne, m'a obligé à réapprendre plein de choses à son sujet[#], que j'avais complètement oublié ou jamais sues, et redécouvrir toutes les petites crottes de ragondin qui polluent un sujet qui a superficiellement l'air simple et élégant (comme : la différence entre β-réduction et βη-réduction, la différence entre termes normalisables et fortement normalisables, la différence entre stratégie de réduction extérieure gauche et intérieure gauche, la différence entre forme normale, forme normale de tête et forme normale de tête faible, etc.) ; le livre de Barendregt (The Lambda Calculus: Its Syntax and Semantics) est assez abominable en matière de dissection de crottes de ragondin, et celui de Krivine (Lambda-calcul : types et modèles — disponible en ligne en traduction anglaise) ne l'est pas moins. Un des problèmes est sans doute qu'on n'a pas vraiment idée de ce que sont les termes du λ-calcul non typé (prima facie, ce sont des fonctions qui prennent en entrée une autre fonction de même sorte et renvoient une autre fonction de même sorte : ce n'est pas du tout clair qu'on puisse fabriquer un objet qui soit aussi l'objet des morphismes de lui-même dans lui-même !) : divers gens (en commençant par Dana Scott à la fin des années 1960) ont réussi à en donner des modèles, ce qui éclaircit un peu la sémantique, mais là aussi on se perd entre les différentes manières de fabriquer des modèles du λ-calcul et les zillions de relations d'équivalence entre types que fournissent ces façons de fabriquer des modèles. (J'ai commencé à lire plein de choses sur le sujet, et surtout à me noyer dans les notations pourries. J'espère que l'article From computation to foundations via functions and application: The λ-calculus and its webbed models de Chantal Berline m'aidera à y voir plus clair.)

Je suis assez étonné, en revanche, de ne pas trouver d'implémentation (libre, flexible et largement disponible) du λ-calcul non typé, qui permettrait de tester un peu les choses (transformer les notations, réécrire les termes à la main ou de façon automatisée, comparer les stratégies de réduction, etc.). Est-ce que j'en ai raté une évidente ?

[#] La première fois que j'ai appris des choses sur le λ-calcul, ça devait être vers 1990 quand on m'a offert le livre de vulgarisation scientifique The Emperor's New Mind de Roger Penrose (j'en ai parlé dans une section d'une entrée récente), qui décrit un peu le λ-calcul et les entiers de Church, et ça m'a complètement fasciné que des règles typographiques aussi simples et élégantes (← mais bon, en fait, une bonne quantité de poussière avait été glissée sous le tapis) puissent donner quelque chose d'aussi puisant.

Ajout (2023-11-12) : Par pure coïncidence, la chaîne de télé Arte vient de produire, dans le cadre de sa série Voyages au pays des maths, un mini-documentaire de vulgarisation (10 minutes) intitulé L'Entscheidungsproblem ou la fin des mathématiques ? (ici sur YouTube, ici sur le site web d'Arte) et qui porte justement sur le sujet dont je parle ici. Je ne suis pas d'accord avec tous les choix de présentation, mais ça donne au moins une idée de ce dont il est question (et notamment, tenter de vulgariser l'équivalence entre fonctions générales récursives, machines de Turing et λ-calcul était un défi pas du tout évident, et je trouve qu'il s'en sort pas mal). Surajout : voir ce nouveau billet où je décortique un peu plus cette vidéo.

Ajout (2024-04-30) : j'ai fait un bilan de la première année de ce cours dans un billet ultérieur.

[Lire la suite…]

Le concept d'oracle dont il est question ici est vient de l'informatique théorique (le terme oracle apparaît dans la thèse d'Alan Turing en 1938). Je voudrais essayer d'expliquer de façon très informelle, très vague aussi malheureusement (mais, j'espère, du coup, assez grand public) ce dont il est question.

Une partie de l'informatique théorique (l'algorithmique) s'intéresse, de façon positive, à trouver des moyens de résoudre des problèmes (mathématiquement bien définis), c'est-à-dire à concevoir des algorithmes qui les résolvent : un algorithme est un programme, un plan d'opération susceptible d'être mené dans un ordinateur — mais aussi en principe par un humain particulièrement patient — qui effectue une tâche calculatoire donnée. Par exemple, la manière dont on apprend à faire des additions et des multiplications à l'école primaire sont des algorithmes, même si ce ne sont pas forcément les plus intéressants, ils ont le mérite de nous rappeler qu'un algorithme ne tourne pas forcément sur un ordinateur, on peut aussi l'exécuter à la main (ce sera juste quelques milliards de fois plus lent…) ; d'ailleurs, le mot algorithme fait référence au mathématicien persan (écrivant en langue arabe) Muḥammad ibn Mūsá al-H̱wārizmī parce qu'il a décrit toutes sortes de méthodes systématiques pour résoudre des problèmes mathématiques, qu'on peut donc légitimement qualifier d'algorithmes, et c'était plus de 1000 ans avant l'invention des ordinateurs.

(Petite digression sur le terme algorithme : il semble qu'un mélange entre l'incompréhension des journalistes face à tout ce qui est technique et l'approximation des termes utilisés dans le contexte de l'intelligence artificielle ait fait dévier le sens du mot, dans l'image qu'en a le grand public, vers une sorte de synonyme de système opaque auquel on ne comprend rien. Certainement beaucoup de programmes utilisés dans l'ingénierie informatique moderne (notamment tout ce qui relève de l'IA) comportent énormément d'heuristiques et de méthodes mal comprises, parfois même mal comprises de leurs programmeurs ou concepteurs, et dont la réponse est parfois fausse ou mal spécifiée. Mais le sens d'algorithme en algorithmique désigne au contraire un plan bien défini et bien compris qui arrive à un résultat bien spécifié.)

Mais d'autres parties de l'informatique théorique s'intéressent non pas à concevoir des algorithmes efficaces pour résoudre tel ou tel problème, mais à se pencher sur la notion même d'algorithme et les limites théoriques du concept : que peut-on faire avec un ordinateur ?

Spécifiquement, on s'intéresse alors plutôt à des résultats négatifs : plutôt que résoudre tel ou tel problème c'est-à-dire concevoir un algorithme qui le résout, on s'attache à montrer que tel ou tel problème est difficile (long et coûteux) voire impossible à résoudre par un algorithme, ou au moins, à étudier cette difficulté, à la classifier et à la jauger. Je reste délibérément vague sur ce qu'un problème peut recouvrir ici et ce que difficile veut dire, mais je peux délimiter ici trois grands domaines où ce que je veux dire s'applique, et j'en profite pour parler un peu plus longuement de chacun des trois, en gros du plus théorique vers le plus appliqué (il n'est pas nécessaire de lire tout ce que j'écris sur chacun ci-dessous pour passer à la suite, mais je cherche à donner un minimum de contexte) :

• La théorie de la calculabilité est la branche de l'informatique théorique (possiblement la plus proche des mathématiques pures, et notamment de la logique) qui étudie ce qu'on peut faire algorithmiquement avec des ressources illimitées, c'est-à-dire, en disposant d'un temps illimité et d'une mémoire illimitée. (Le mot illimité signifie ici fini mais arbitrairement grand, sans limite a priori : c'est-à-dire que les algorithmes en question doivent s'arrêter un jour en disant j'ai terminé, mais ils ont le droit de prendre autant de temps qu'ils veulent, tant que ce temps est fini ; idem pour la mémoire : ils ont le droit de stocker toutes les données qu'ils veulent tant que cet espace utilisé reste fini à tout moment. C'est donc la forme la plus abstraite et théorique de la question que peut-on faire avec un ordinateur ? qui est étudiée ici, et elle déborde sur des questions du type comment peut-on imaginer des types de machines fondamentalement et théoriquement plus puissantes qu'un ordinateur même si elles ne sont pas réalisables en pratique ? — mentionnons par exemple que même un ordinateur quantique, qui si on réussissait à en construire serait pour certains types de problèmes incroyablement plus efficace qu'un ordinateur tel que nous disposons actuellement, ne représente pas un saut qualitatif tel qu'il peut intéresser la calculabilité : pour la calculabilité, un ordinateur quantique, un ordinateur classique, un système d'engrenages mécaniques ou encore un humain extrêmement patient et systématique muni d'un stylo et d'un papier et exécutant mécaniquement des opérations prédéfinies valent exactement la même chose.)

  La calculabilité est un peu la mère de l'informatique, parce que c'est au travers de la recherche d'une formalisation de ce qu'est un algorithme, et ce qu'un algorithme peut faire, qu'Alonzo Church et son étudiant Alan Turing sont arrivés au concept de calculabilité ; la définition précise d'algorithme à laquelle Turing est arrivé, la machine de Turing, est considéré comme une préfiguration théorique de ce qu'est un ordinateur.

  Un des thèmes majeurs de la calculabilité, donc, c'est de montrer que, pour des raisons théoriques, certains types de problèmes (mathématiquement bien posés) ne sont pas résolubles algorithmiquement : même avec un temps illimité(-mais-fini) à votre disposition, et autant de mémoire, vous ne pourrez pas écrire un algorithme qui répond à coup sûr à certaines questions qui admettent pourtant une réponse bien définie.

  L'exemple archétypal à ce sujet est le problème de l'arrêt : très grossièrement, ce problème demande justement, donné un algorithme, i.e., une suite d'instructions à exécuter (qui peut, bien sûr, contenir des boucles, du type répéter les instructions suivantes tant qu'une certaine condition n'est pas vérifiée), et des valeurs à fournir en entrée à cet algorithme, si l'algorithme en question finit (i.e., si le calcul aboutit à un résultat). Le théorème majeur de Turing, qui est à la base de la théorie de la calculabilité (et donc, dans un certain sens, de l'informatique ; mais à l'origine il s'y intéressait pour des raisons liées à la logique mathématique et spécifiquement au théorème de Gödel), c'est qu'aucun algorithme ne peut résoudre le problème de l'arrêt : autrement dit, aucun algorithme ne peut dire à coup sûr si un autre algorithme s'arrête au bout d'un temps fini. (La seule façon de savoir est de l'exécuter, ce qu'on peut faire, mais quand on l'exécute, tant qu'il n'est pas fini, on n'est jamais sûr si le programme finira par terminer plus tard.) La raison de cette impossibilité est d'ailleurs étonnamment bête une fois qu'on a fait le travail de formalisation pour rendre rigoureuse la théorie : en gros, si un algorithme existait qui puisse dire à coup sûr si un algorithme donné s'arrête, on pourrait faire un algorithme qui l'interroge et fait le contraire de ce qu'il a prédit, ce qui le met en défaut. (C'est ce qu'on appelle un argument diagonal de Cantor.)

  La calculabilité ne se contente pas, en fait, de définir des problèmes résolubles ou non résolubles algorithmiquement, et de le montrer : il y a des problèmes plus ou moins impossibles à résoudre, et l'étude des degrés d'impossibilité (par exemple les degrés de Turing dont je dirai un mot plus bas, et que je définirai précisément dans le volet technique de ce billet) est un sujet de recherche qui court depuis Turing, mais l'outil de base pour ne serait-ce que formuler ce genre de questions est la notion d'oracle que je vais chercher à introduire ici.

• La théorie de la complexité [algorithmique], cherche à être plus fine que la calculabilité : alors que la calculabilité donne aux algorithmes l'accès à des ressources (temps, mémoire) illimitées-mais-finies, la complexité s'intéresse à des problèmes résolubles par un algorithme, mais cherche à mesurer combien de temps ou de mémoire (ou parfois d'autres ressources) un algorithme devra utiliser, en fonction de la taille du problème qu'on leur pose, lorsque cette taille devient très grande. (Par exemple, combien d'étapes faut-il pour multiplier deux nombres de 100 chiffres ? de 1000 chiffres ? de 10 000 chiffres ? Avec l'algorithme qu'on apprend à l'école primaire, la réponse est en gros 10 000, 1 000 000 et 100 000 000 respectivement, parce qu'il faut multiplier chaque chiffre du multiplicande par chaque chiffre du multiplicateur avant d'ajouter tout ça : en complexité on appelle ça un algorithme quadratique. En fait, on peut faire beaucoup plus efficacement, et d'ailleurs au moins un algorithme de multiplication plus efficace sur les grands nombres que l'algorithme appris à l'école primaire peut vraiment servir à la main — enfin, pourrait servir à la main si on était dans un monde où nous n'avions pas un ordinateur en permanence avec nous.)

  La complexité est donc une discipline un peu plus applicable au monde réel que la calculabilité : alors que la calculabilité va nous donner des réponses du type vous ne pouvez pas résoudre ce problème avec un ordinateur, quel que soit le temps que vous soyez prêt à attendre ou oui vous pouvez, mais je n'ai aucune idée du temps nécessaire parce que ce n'est pas mon sujet, la complexité va chercher à voir plus précisément dans la deuxième catégorie entre des problèmes théoriquement-résolubles-mais-absolument-pas-en-pratique (un peu comme si vous cherchiez à multiplier à la main deux nombres de 1 000 000 000 000 chiffres… oui, en principe c'est possible) et des problèmes un peu plus abordables en pratique. (La complexité va aussi faire la différence entre différents types d'ordinateurs qui, pour la calculabilité sont équivalents, par exemple un ordinateur quantique permet plus de choses du point de vue de la complexité parce qu'il peut en quelque sorte mener plein de calculs en parallèle ; alors qu'en calculabilité il ne change rien du tout par rapport à un ordinateur classique.)

  Néanmoins, la complexité reste une discipline assez théorique parce qu'elle se penche sur le temps (ou la mémoire, ou une autre ressource) utilisés asymptotiquement : ici, asymptotiquement veut dire quand la taille de l'entrée de notre problème (i.e. l'instance précise) devient extrêmement grande (tend vers l'infini). C'est-à-dire que le but de la complexité n'est pas de savoir si vous allez prendre exactement tel ou tel temps pour multiplier deux grands entiers (disons) mais comment ce temps grandit quand les entiers deviennent très grands (est-ce que doubler la taille des nombres double le temps qu'il faut pour faire la multiplication ? plus ? moins ?). Tout simplement parce que c'est un peu plus abordable comme type de question (et que c'est déjà utile dans la pratique).

  La complexité définit toutes sortes de catégories de problèmes en fonction de la difficulté à les résoudre, mesurée sous la forme des ressources qu'on accepte d'allouer à un algorithme qui les résout. (Par exemple, de façon approximative, un problème est dit EXPTIME ou EXPSPACE s'il existe un algorithme qui le résout et dont le temps d'exécution ou respectivement la mémoire utilisée croît au plus exponentiellement dans la taille de la donnée ; on peut faire énormément de choses avec un temps ou une mémoire exponentielle, donc énormément de problèmes sont dans ces classes, qui ne sont pas d'un grand intérêt pratique, mais c'est quand même plus restrictif que les problèmes tout simplement calculables en ressource illimitées que j'ai évoqués plus haut.)

  Deux classes particulièrement importantes en calculabilité sont les classes P et NP. La classe P est très grossièrement celle des problèmes faciles (un peu plus précisément, ce sont ceux qui sont résolubles par un algorithme qui utilise un temps au plus polynomial dans la taille de l'entrée : linéaire, quadratique, cubique, quelque chose comme ça, mais exponentiel n'est pas permis) ; la classe NP est plus subtile : très grossièrement, ce sont les problèmes faciles à vérifier (mais pas forcément faciles à résoudre ; c'est-à-dire que si vous avez la réponse, la vérification qu'elle est correcte se fait essentiellement selon la classe P, mais par contre, si vous ne connaissez pas la réponse, il est possible qu'elle soit très difficile à trouver ; j'insiste sur le fait que mes explications sont très grossières et que je passe sur plein de subtilités théoriques).

  Un exemple de problème NP très simple à décrire est le suivant : je vous donne un tas de nombres (entiers positifs, disons) et un nombre-cible, et votre but est d'exprimer le nombre-cible comme somme de certains des nombres donnés. (C'est une variante très simple des « chiffres et les lettres » où on n'a le droit qu'à l'addition ! Ou bien imaginez que ce sont des pièces de monnaie dans un système monétaire bizarre, et vous voulez réussir à payer exactement un certain montant cible en ayant dans votre poche des pièces de certains montants donnés. Par exemple, si je vous donne les nombres 1, 3, 8, 17, 32, 51, 82, 127, 216, 329, 611, 956 et 1849, et que je vous demande de faire la somme 2146 avec, ce n'est pas évident d'y arriver sauf à tester énormément de combinaisons ; par contre, vérifier que 1 + 8 + 32 + 82 + 127 + 329 + 611 + 956 = 2146 est un calcul facile.)

  Parmi les classes que j'ai pas-vraiment-définies-mais-un-peu-évoquées, on a P ⊆ NP ⊆ EXPTIME, le symbole ‘⊆’ signifiant ici est inclus dans, c'est-à-dire que tout problème P (facile à résoudre) est en particulier NP (facile à vérifier), et que tout problème NP est lui-même, en particulier, EXPTIME (résoluble en temps exponentiel). (Ce dernier est à son tour inclus dans EXPSPACE mais peu importe.) On sait par ailleurs montrer qu'il existe des problèmes qui sont dans EXPTIME mais qui ne sont pas dans P (et on sait en décrire explicitement), autrement dit, des problèmes résolubles en temps exponentiels mais pas faciles pour autant (pas résolubles en temps polynomial) : ce n'est pas très surprenant, parce qu'une exponentielle grandit vraiment très vite, donc il n'est pas surprenant que certains problèmes puissent se résoudre en un temps exponentiel mais pas en un temps beaucoup plus limité, mais encore fallait-il le prouver (ce n'est pas très difficile, mais ce n'est pas complètement évident non plus). Bref, si voit P ⊆ NP ⊆ EXPTIME comme trois boîtes imbriquées, la plus à gauche est effectivement strictement plus petite que la plus à droite. Mais la question se pose de savoir comment est celle du milieu. En fait, on ne sait pas la situer ni par rapport à celle de gauche ni par rapport à celle de droite.

  Spécifiquement, une question centrale de la théorie de la complexité est de savoir si P=NP (en gros, est-ce que tout problème facile à vérifier est, en fait, facile à résoudre ?). On pense très fortement que la réponse est non (i.e., qu'il existe des problèmes qui sont dans NP et qui ne sont pas dans P ; on en a même plein de candidats, d'ailleurs celui que j'ai donné plus haut en est un), mais on ne sait pas le prouver (l'enjeu, ici, est de prouver rigoureusement qu'un problème est difficile au sens où il ne peut pas exister d'algorithme qui le résout facilement). Cette question P≟NP est même mise à prix à 1 000 000 $ (et attire régulièrement des « solutions » incorrectes de toutes parts).

  Pour en savoir plus sur la situation en complexité, cet article récent de vulgarisation (costaud !) dans le magazine Quanta, quoique long, n'est pas mauvais pour donner un aperçu, et expliquer un peu mieux que ce que je l'ai fait ce que c'est que cette histoire de P≟NP, ce qu'on sait dire à son sujet et quelle est la difficulté. Ce n'est pas vraiment mon propos ici d'en dire plus ici.

• La cryptographie (enfin, peut-être que je devrais plutôt dire cryptologie ici) est l'étude scientifique de la sécurité de l'information : il s'agit de développer des techniques de chiffrement (comment transformer un message en un chiffré qui ne puisse être déchiffré qu'en ayant accès à une clé) ou ayant trait à d'autres questions de sécurité de l'information (signature électronique, authenticité, non-répudiation, partage de secrets, ce genre de choses). Mais plus précisément, ici, au sein de la cryptographie, j'ai à l'esprit la cryptographie à clés publiques (voir ce billet récent pour une explication de ce que ça signifie ; ce n'est pas très important ici).

  Une différence importante entre la calculabilité/complexité et la cryptographie est qu'en cryptographie il y a un adversaire (par exemple, s'agissant d'un chiffrement, l'adversaire est un attaquant hypothétique qui essaie d'obtenir des informations sur le message sans avoir la clé de déchiffrement, ou peut-être sur la clé en ayant connaissance du message et du chiffré, ou des variantes autour de ces questions). En calculabilité ou en complexité on s'intéresse à la difficulté de problèmes parce que ça mettra une borne sur ce que nous pourrons faire. En cryptographie, on s'intéresse à la difficulté plutôt parce que ça peut représenter un travail pour l'attaquant (donc la difficulté est souhaitable !). Spécifiquement, on voudrait concevoir des méthodes de chiffrement qui soient faciles à utiliser (c'est-à-dire, peu coûteuses algorithmiquement) quand on connaît la clé, mais extrêmement difficiles à casser, c'est-à-dire pour l'attaquant qui ne connaît pas la clé, et si possible, on voudrait prouver cette difficulté, ou au moins avoir des raisons un peu plus tangibles que je ne sais pas faire, donc c'est sans doute compliqué.

Bref, dans ces trois domaines (et il y en a sans doute d'autres dont j'ignore tout ou qui ne me viennent pas à l'esprit), pour des raisons un peu différentes et avec des notions de problème et de difficulté différentes, on peut chercher à montrer qu'un certain problème est difficile (voire, s'agissant de la calculabilité, impossible, mais je vais ranger ça sous l'étiquette vague difficile), ou étudier sa difficulté.

Bon, mais comment montre-t-on qu'un problème est difficile ?

[Lire la suite…]

[Lire la suite…]

❦

[Lire la suite…]

Métamotivations : [bon, sérieusement, je ne sais pas ce que sont des métamotivations, mais je trouve ce mot trop rigolo pour ne pas l'écrire]

J'ai commencé il y a quelques semaines à écrire une entrée de ce blog (je vais dire dans un instant à quel sujet, mais pour l'instant ce n'est pas important), et il est arrivé ce qui m'arrive trop souvent : je pars plein d'enthousiasme en me disant que je vais réussir à condenser à sa substantifique moëlle un sujet fort copieux, en même temps que le vulgariser, je me mets à taper, taper, taper, la condensation espérée n'a pas vraiment lieu, au contraire, je me rends compte qu'il faut que je parle de ceci, puis de cela, le texte que j'écris devient de plus en plus indigeste, et, pire, alors que je partais tout content de me dire que l'effort d'exposition me permettra d'y voir plus clair sur le sujet dont je parle, plus je l'écris plus je commence à en avoir marre de l'écrire, donc plus je traîne à m'y mettre, et en plus quand je m'y mets je mets tellement de temps à relire ce que j'ai déjà écrit que les progrès initialement rapides deviennent de plus en plus lent, et cette lente agonie ne prend fin que quand je décide de bouger le billet en cours d'écriture dans un fichier d'entrées inachevées qui prend de plus en plus la forme d'un cimetière, parce que sinon il bloque l'écriture de toute nouvelle entrée.

(Oui, mes phrases sont trop longues. Je sais.)

Que faire quand ce genre de choses se produit ? (C'est fréquent, et j'ai déjà dû en parler plein de fois.) Je n'ai toujours pas trouvé de réponse satisfaisante. Je peux jeter l'éponge et publier l'entrée dans son état inachevé, mais c'est un peu renoncer à toute possibilité de l'améliorer ultérieurement, ce qui me déplaît (il m'arrive bien sûr de modifier des entrées déjà publiées, mais c'est pour ajouter des petites précisions mineures : personne ne va tout relire pour ça). Je peux publier les parties qui sont à peu près présentables (ces entrées fort longues se découpant en parties et sous-parties, je peux publier, disons, le premier chapitre), mais je n'aime pas beaucoup non plus parce que je risque de vouloir quand même y faire des additions ultérieures, et aussi parce que ça rompt ma promesse implicite d'essayer autant que raisonnablement possible d'écrire des entrées indépendantes sur ce blog. (Promesse qui me semble nécessaire si je veux qu'on puisse lire l'entrée #2698 de ce blog sans avoir lu les 2697 qui ont précédé, ce que sans doute personne n'a fait, je ne suis même pas sûr de l'avoir fait moi-même.) Bon, je suis de mauvaise foi, je peux bien dire je suppose qu'on a lu <telle entrée passée>, d'ailleurs il a dû m'arriver quelques fois de le faire, mais si la partie 2 met des années à arriver, personne ne la lira parce que tout le monde aura oublié la partie 1 et que personne n'aura envie de la relire. Même vis-à-vis de moi-même, quand je publie quelque chose sur ce blog, qui est un peu l'espace de swap de mon cerveau, c'est pour me décharger mentalement en me disant que je peux l'oublier puisque je pourrai toujours me relire plus tard (et du coup je ne le fais généralement pas, justement), et ça ne marche plus vraiment si je continue à vouloir donner une suite.

Mais faute d'avoir décidé, je me dis que je peux au moins publier en avance (quitte à la recopier quand même plus tard, ce n'est pas long ce ne sera pas grave) la partie motivations de l'entrée en question. Ne serait-ce que parce que les motivations, c'est un peu comme les remerciements de thèse, c'est la seule chose que doit lire la majorité des gens ; et ici, ils ont, je crois, un intérêt autonome parce que c'est beaucoup moins technique que ce qui vient (enfin, est censé venir) après ; et je ne crois pas avoir envie de les changer plus tard, et elles ont toute leur place ici puisque, finalement, je suis en train de parler de ma motivation.

(En plus, là, j'ai été aspiré par d'autres préoccupations qui m'ont bouffé plein de temps, donc l'écriture de ce billet-ci a elle-même traîné en longueur !)

Voici donc les motivations de ce billet partiellement écrit :

❦

Motivations et introduction générales

Il y a un certain temps, j'avais publié un billet fort mal écrit sur la logique intuitionniste et les mathématiques constructives, pour essayer d'expliquer de quoi il s'agit. J'aimerais réessayer d'en parler, mais en prenant une approche différente : dans le billet précédent (que je ne vais pas supposer que le lecteur a lu, même si ça peut aider de l'avoir au moins parcouru), j'avais mis l'accent sur les règles de la logique intuitionniste (la syntaxe, si on veut), maintenant je voudrais mettre l'accent sur les « mondes » (j'utilise ce terme de façon délibérément vague et informelle, je vais revenir là-dessus) dans lesquels la logique intuitionniste s'applique — la sémantique si on veut. Je pense en effet qu'on comprend beaucoup mieux l'intérêt de cette logique (au-delà de se dire tiens, je vais m'interdire d'appliquer le tiers exclu et voyons ce qui se passe) si on commence par avoir à l'esprit quelques situations où elle s'applique.

Comme on n'a pas besoin de savoir d'avance ce qu'est la logique intuitionniste pour comprendre ces « mondes », cela peut aider, justement, à l'approcher : de l'« intérieur » ils sont régis par la logique intuitionniste, mais de l'« extérieur » ce sont des objets mathématiques classiques (d'ailleurs manipulés régulièrement par des mathématiciens qui n'ont aucune appétence particulière pour la logique, comme les faisceaux en topologie ou géométrie algébrique). Ils forment donc un pont par lequel un mathématicien classique peut comprendre ou visualiser les objets intuitionnistes.

Mais par ailleurs, ces « mondes » sont intéressants, au-delà de l'aspect logique, pour la source de contre-exemples qu'ils fournissent : un monde dans lequel toutes les fonctions ℝ→ℝ sont continues, par exemple, ou dans lequel toutes les fonctions ℕ→ℕ sont calculables, ou dans lequel le théorème des valeurs intermédiaires ne peut pas être affirmé, ou dans lequel on ne peut pas affirmer qu'une suite croissante bornée de réels converge, cela mérite qu'on s'y intéresse même si on n'a aucun intérêt particulier pour la logique : je pense, et c'est en fait ma principale motivation pour m'y intéresser, que cela permet une meilleure compréhension des objets basiques que sont les entiers naturels, les réels, les fonctions entre eux, de comment ils sont construits et de ce qui permet de démontrer ceci ou cela. (Et en comparaison au degré de technicité nécessaire pour construire des mondes dans lesquels l'axiome du choix ne vaut pas, les constructions ici sont raisonnablement peu élaborées bien que plus dépaysantes, ce qui augmente leur intérêt pédagogique.)

J'utilise ci-dessus le mot monde, délibérément vague : disons un mot à ce sujet. En logique classique, le terme correct pour désigner un monde dans lequel vaut une théorie est celui de modèle (pour montrer qu'une théorie T n'implique pas un énoncé φ, on va construire un modèle de T ne vérifiant pas φ). Il y a plusieurs notions de modèle permettant de donner une sémantique à la logique intuitionniste : modèles de Kripke, par exemple, modèles à valeurs dans une algèbre de Heyting, ou encore topoï. Les « mondes » dont je veux parler sont, en l'occurrence, des topoï, mais je ne compte pas expliquer ce qu'est un topos en général, uniquement en donner des exemples. Pourquoi ? Pas que ce soit immensément compliqué si on connaît un peu de théorie des catégories (encore qu'il y a la subtilité qu'il y a deux sens, apparentés mais distincts, du mot topos : topos de Grothendieck [dans ce cas le pluriel est un topos, des topos] ou topoï élémentaires [dans ce cas le pluriel est un topos, des topoï], ces derniers étant plus généraux que ces premiers), mais je pense que la notion de topos ne peut être correctement comprise qu'en ayant au préalable un stock d'exemples, et il s'agit donc de commencer par là. D'autre part, je ne prétends pas énoncer de résultat de complétude. Disons un mot à ce sujet.

[Le paragraphe suivant est une digression par rapport à mon propos général. On peut le sauter sans perdre le fil.]

Quand on a une théorie logique (ce mot étant pris ici, informellement, dans un sens excessivement vague et général), lui définir une sémantique, c'est définir un tas de mondes possibles (même remarque) qui valident certains énoncés (i.e., certaines choses sont vraies dans tel ou tel de ces mondes), et la moindre des choses est que la sémantique donne raison à la théorie, c'est la partie qu'on appelle la soundness en anglais, et je ne sais pas quel mot utiliser en français (cohérence ?) : dire que la sémantique Muf est sound (sensée ?) pour la théorie Truc, c'est dire que tout ce que la théorie Truc permet de démontrer sera vérifié dans chacun des « mondes » Muf. En général, ce n'est pas difficile, c'est même souvent une évidence tellement évidente qu'on ne se fatigue pas à le dire. (Mais remarquez que les « mondes » dont je veux parler, s'ils sont sound pour la logique intuitionniste, ne le sont pas pour la logique classique, et c'est bien pour ça qu'il y aura des théorèmes des mathématiques classiques qui ne seront pas valables dans certains d'entre eux, du genre le théorème des valeurs intermédiaires.) Mais l'autre chose qu'on veut souvent (mais pas forcément) avec une sémantique, c'est qu'elle soit complète, et là ça veut dire la réciproque : dire que la sémantique Muf est complète pour la théorie Truc, c'est dire que tout ce qui est vérifié dans chacun des « mondes » Muf pourra être démontré dans la théorie Truc. En logique classique du premier ordre avec la sémantique fournie par la notion habituelle de modèle, si vous savez ce que c'est, on a effectivement complétude, et le résultat en question s'appelle le théorème de complétude de Gödel (qui affirme que, dans le contexte du calcul des prédicats du premier ordre en logique classique, si φ est vrai dans tout modèle d'une théorie T alors φ est démontrable à partir de T). La question de la mesure dans laquelle les topoï définissent une sémantique complète par rapport à la logique intuitionniste dépend crucialement de ce qu'on appelle exactement la logique intuitionniste (le problème n'étant pas les règles de déduction mais ce sur quoi on s'autorise à quantifier), et essayer d'expliquer ça, sur quoi je n'ai d'ailleurs pas les idées aussi claires que je voudrais, m'entraînerait à parler de logique d'ordre supérieur, de théorie des types et de choses dont je ne veux pas parler. Donc je vais faire complètement l'impasse sur tout ce qui concerne la complétude, et du coup il n'est pas vraiment pertinent que j'explique ce qu'est un topos, ce qui m'importe ce sont les exemples que je veux exposer et le fait qu'ils soient sound.

[Fin de la digression.]

Ce qui est intéressant à comprendre, aussi, c'est le rapport entre le point de vue « interne » et le point de vue « externe » sur les « mondes » en question : on peut soit se plonger dans un de ces « mondes », le regarder avec les lunettes « internes », auquel cas on a affaire à des ensembles dans un monde de maths intuitionnistes, ou au contraire le regarder « de l'extérieur », auquel cas on a affaire à des objets un peu plus compliqués (faisceaux, par exemple, en tout cas des objets d'une catégorie et c'est cette dernière qu'on appelle topos) mais dans un monde plus familier puisque la logique classique s'applique. Les deux points de vue se traduisent l'un l'autre (du moins, tout énoncé « interne » peut se réécrire de façon « externe », la réciproque n'est pas forcément vraie), ils s'éclairent et se complètent. Ce que je voudrais faire c'est expliquer, sur quelques exemples, comment marche cet aller-retour.

[Lire la suite…]

Mon poussinet s'est acheté une nouvelle voiture. Ou plus exactement, a remplacé un joujou, rouge de chez Honda, thermique et bruyant, par un autre joujou, blanc de chez Tesla, électrique et beaucoup moins bruyant et beaucoup plus Internet of Shit ; mais ce n'est pas mon propos ici d'en parler : le point de départ de ce que je veux dire ici, c'est que le nouveau joujou est assez long et large, et que la descente du parking de notre immeuble est compliquée.

Nous avons trois véhicules et trois places de parking (une achetée avec l'appartement et deux louées à des voisins). Ma moto, bizarrement, ne pose aucun problème pour monter et descendre au parking. Pour la Tuture préférée (qui fait censément 1.74m de large, et 4.15m de long dont 2.51m entre les essieux), le poussinet s'en sort bien (le plus souvent sans marche arrière), mais moi je n'ose pas trop essayer, et c'est d'ailleurs mon principal obstacle à circuler en voiture. Et pour le nouveau joujou (qui fait censément 1.85m de large, et 4.69m de long dont 2.83m entre les essieux), c'est beaucoup plus compliqué : à ce stade, à chaque fois que nous voulons entrer ou sortir du parking, je descends de la voiture, je passe devant, et j'indique au poussinet par des signes de main la distance à gauche et à droite (certes, le joujou a plein de capteurs, mais ils sont essentiellement inutiles dans ces circonstances, parce qu'ils passent juste leur temps à faire bip, et ne détectent pas forcément la « bonne » distance) : il arrive à sortir en une seule fois, mais pour rentrer dans le parking il faut trois ou quatre marches arrière (et la question de pourquoi ce n'est pas symétrique est une de celles que je veux discuter ici).

Pourtant, la descente du parking n'est pas si étroite : elle fait 2.67m de large au point le plus resserré que j'aie mesuré ; cette largeur est un peu stupidement grignotée par le fait qu'il y a des garde-corps (je ne sais pas comment les appeler : une sorte de marche ou de micro trottoirs de part et d'autre de la descente, au niveau du sol, large d'environ 15cm et haute d'environ autant), qui réduit l'espace disponible au niveau des roues à 2.38m au point le plus étroit. Mais bien sûr, la descente est courbe : entre la porte côté rue et la base de la rampe, il y a un changement de cap de 90° (on entre perpendiculairement à la rue Simonet, et on finit parallèlement à elle).

Géométriquement, si j'en crois les plans d'architecte de l'immeuble que j'ai récupérés je ne sais plus comment, la forme est très simple (cf. figure ci-contre) : prenez un quart de cercle de rayon 6.50m et un autre de rayon 5.50m dont les centres sont décalés de 1.75m selon chacun des axes du quart de cercle (donc à distance 1.75m×√2 ≈ 2.47m l'un de l'autre), le centre du petit cercle étant évidemment plus éloigné des arcs eux-mêmes que celui du grand cercle, et ensuite prolongez tangentiellement chacune des deux extrémités de chacun des deux arcs. (En notation SVG et en exprimant les distances en mètres : M 0.00 0.00 L 9.37 0.00 A 6.50 6.50 0 0 1 15.87 6.50 L 15.87 18.38 pour le bord extérieur et M 0.00 2.75 L 7.62 2.75 A 5.50 5.50 0 0 1 13.12 8.25 L 13.12 18.38 pour le bord intérieur.) Ceci fait donc une rampe dont la largeur est de (6.50m−5.50m)+1.75m = 2.75m dans ses parties rectilignes, et de (6.50m−5.50m)+1.75m×√2 ≈ 3.47m dans sa partie courbe, à quoi il faut retirer environ 15cm de garde-corps de part et d'autre comme je l'ai expliqué ci-dessus. J'ai fait apparaître sur la figure des rectangles à l'échelle du joujou du poussinet, mais il n'est pas évident de le placer comme je viens de le montrer (cf. plus loin). L'épaisseur des traits sur la figure est de 30cm (le milieu du trait est au niveau du mur lui-même, le bord intérieur correspond à peu près au bord du garde-corps).

Bon, en plus, la rampe est bien sûr en pente (de 14.38% selon le plan d'architecte, l'hélice étant orientée à main gauche : sur le schéma ci-contre, la sortie côté rue est en bas de la figure, la base de la rampe côté parking est à gauche), mais je ne pense pas que ça joue énormément sur le problème géométrique que je vais évoquer. Par ailleurs, la construction de l'immeuble n'a pas respecté précisément les plans d'architecte et les arcs de cercle ont été approchés par des polygones, donc il y a trois ou quatre points anguleux sur le mur extérieur : je ne sais pas bien si ça joue dans l'explication de l'asymétrie ressentie entre montée et descente, je vais y revenir ; la largeur de la rampe, comme je l'ai dit plus haut, n'est, d'après mes mesures, pas tout à fait égale aux 2.75m contractuels de mur à mur, je l'ai déjà noté.

Mes lecteurs savent que j'aime faire des typologies, alors allons-y. Je peux distinguer trois niveaux au problème d'entrer ou sortir la voiture :

1. La question purement géométrique (entrer ou sortir la voiture, en supposant une connaissance parfaite de ses dimensions, sa position, la forme de la rampe, etc., donc toutes les distances impliquées), que je vais elle-même ci-dessous subdiviser en trois.
2. La complication supplémentaire que, assis à la place du conducteur, on voit mal ce qu'on fait, on évalue mal les distances, malgré les rétroviseurs et les diverses caméras de la Tesla, en tout cas, plus mal que quelqu'un qui se tient à distance et qui regarde la voiture de l'extérieur.
3. La complication supplémentaire qu'une voiture n'avance pas exactement comme on veut (je parle du point de vue de la traction : je mets la question du rayon de braquage sur le chapeau géométrique) : ceci ne concerne pas la Tesla, dont le moteur électrique permet d'avancer aussi lentement qu'on veut, presque millimètre par millimètre, aussi bien en montée qu'en descente, mais le problème se pose avec une voiture thermique si on ne veut pas vitrifier l'embrayage en patinant trop longtemps.

Je veux surtout parler ici du (A), même si (B) et (C) sont aussi problématiques en pratique. Maintenant, même si je le simplifie à outrance en traitant la voiture comme un simple rectangle et en ramenant tout le problème dans le plan, ce que je vais faire, le (A) se subdivise lui-même en trois niveaux de difficulté :

[Lire la suite…]

Je rassemble dans cette entrée quelques faits algorithmiques et informatiques qui sont généralement « bien connus » (et franchement assez basiques) mais souvent utiles, et qu'il est possiblement difficile de trouver rassemblés en un seul endroit. Le problème général est de tirer algorithmiquement des variables aléatoires selon différentes distributions, typiquement à partir d'un générateur aléatoire qui produit soit des bits aléatoires (indépendants et non biaisés) soit des variables aléatoires réelles (indépendantes) uniformément réparties sur [0;1]. Je parle d'algorithmique, mais ce n'est pas uniquement sur un ordinateur : ça peut être utile même dans la vie réelle, par exemple si on a une pièce avec laquelle on peut tirer à pile ou face et qu'on veut s'en servir pour jouer à un jeu qui réclame des dés à 6 faces, ou si on a des dés à 6 faces et qu'on veut jouer à un jeu d'aventure qui réclame des dés à 20 faces.

Comment tirer des nombres aléatoires en conditions adversariales ? Je commence par ce problème-ci qui n'a pas de rapport direct avec la suite, mais que je trouve quand même opportun de regrouper avec : Alice et Bob veulent jouer à pile ou face, ou plus généralement tirer un dé à n faces, mais ils n'ont pas de pièce ou de dé en lequel ils fassent tous les deux confiance. Par exemple, Alice a sa pièce fétiche que Bob soupçonne d'être truquée et symétriquement (ou peut-être même que chacun est persuadé de pouvoir tirer des nombres aléatoires dans sa tête mais ne fait évidemment pas confiance à l'autre). La solution est la suivante : chacun fait un tirage avec son propre moyen de son côté, sans connaître le résultat de l'autre, et on combine ensuite les résultats selon n'importe quelle opération (choisie à l'avance !) qui donne tous les n résultats possibles pour chaque valeur fixée d'une quelconque des entrées (un carré latin, par exemple une loi de groupe) ; par exemple, s'il s'agit de tirer à pile ou face, on peut décider (à l'avance !) que le résultat sera pile (0) si les deux pièces ont donné le même résultat et face (1) si elles ont donné un résultat différent ; s'il s'agit de dés à n faces donnant un résultat entre 0 et n−1, on fait la somme modulo n (c'est-à-dire qu'on fait la somme et qu'on soustrait n si elle vaut au moins n, pour se ramener à un résultat entre 0 et n−1). Bien sûr, il faut un protocole pratique pour faire en sorte que chacun fasse son tirage sans connaître le résultat de l'autre (sinon, s'il a moyen de tricher, il pourra adapter le résultat en conséquence) : physiquement, chacun peut faire son tirage en secret et écrire le résultat secrètement sur un papier placé dans une enveloppe scellée, qu'on ouvrira une fois les deux tirages effectués (en fait, il n'y a que le premier tirage qui a besoin d'être fait de la sorte) ; cryptographiquement, on procède à une mise en gage (typiquement au moyen d'une fonction de hachage, mais je ne veux pas entrer dans ces questions-là). On peut bien sûr généraliser à plus que deux joueurs (en faisant la somme modulo n de nombres tirés par chacun des participants). Le protocole garantit que le résultat sera un tirage uniforme honnête si l'un au moins des participants désire qu'il le soit (et a les moyens de réaliser un tirage honnête) : bien sûr, si aucun des participants ne le souhaite, c'est leur problème, donc on s'en fout. Même si on abandonne toute prétention à ce que les participants tirent leur valeur aléatoirement et qu'on s'imagine qu'ils la choisissent, tant qu'il s'agit d'un jeu à somme nulle, la stratégie optimale est bien de tirer au hasard (et encore une fois, s'ils veulent coopérer pour un autre résultat, tant qu'il n'y a pas d'autre partie impliquée, c'est leur problème, de même s'ils s'imaginent pouvoir faire mieux que le hasard en utilisant, par exemple, une prédiction psychologique).

Je ne sais plus où j'avais lu que ce protocole a été découvert (il l'a certainement été de nombreuses fois !) à la renaissance. Dans mon souvenir, le découvreur proposait même que, pour une question de la plus haute importance, on demande au pape de faire un des tirages en plus de tous les autres participants. Je ne sais d'ailleurs pas si ce protocole a un nom standard.

Comment tirer une variable de Bernoulli de paramètre p à partir de bits aléatoires ? Autrement dit, ici, on a fixé p, et on veut faire un tirage aléatoire qui renvoie oui avec probabilité p et non avec probabilité 1−p, et pour ça, on dispose simplement d'une pièce qui renvoie des bits aléatoires en tirant à pile (0) ou face (1), et on souhaite effectuer les tirages de façon économique. Par exemple, combien de tirages de pièce faut-il, en moyenne, pour générer un événement de probabilité 1/3 ? Il s'avère, en fait, que quel que soit p on peut s'en tirer avec deux (2) tirages en moyenne (je veux dire en espérance). Pour cela, on peut procéder ainsi : on effectue des tirages répétés et on interprète les bits aléatoires ainsi produits comme l'écriture binaire d'un nombre réel x uniformément réparti entre 0 et 1 : on compare x à 1−p en binaire, c'est-à-dire qu'on s'arrête dès qu'on dispose d'assez de bits pour pouvoir décider si x < 1−p ou x > 1−p (on peut considérer le cas x = 1−p comme s'il était impossible vu qu'il est de probabilité 0), en notant qu'on va avoir x < 1−p lorsque le k-ième bit tiré est 0 et que le k-ième bit de l'écriture binaire de p vaut 0, et x > 1−p lorsque le k-ième bit tiré est 1 et que le k-ième bit de p vaut 1 ; et si x < 1−p on renvoie non, sinon oui. Concrètement, donc, faire des tirages aléatoires jusqu'à ce que le k-ième bit tiré soit égal au k-ième bit de l'écriture de p, et alors s'arrêter et renvoyer ce bit-là. Il est clair que cet algorithme fonctionne, mais pour qu'il soit encore plus évident qu'il conduit à faire deux tirages en moyenne, on peut le reformuler de la façon encore plus élégante suivante (il suffit d'échanger les résultats 0 et 1 pour x, qui sont complètement symétriques, lorsque le bit correspondant de p vaut 0) : tirer des bits aléatoires jusqu'à tomber sur 1, et lorsque c'est le cas, s'arrêter et renvoyer le k-ième bit de p (où k est le nombre de bits aléatoires qui ont été tirés). Je trouve ça incroyablement élégant et astucieux (même si c'est très facile), et je ne sais pas d'où sort ce truc. (Cela revient encore à tirer une variable aléatoire k distribuée selon une loi géométrique d'espérance 1, comme je l'explique plus bas, c'est-à-dire valant k avec probabilité (½)^k+1, et renvoyer le (k+1)-ième bit b_k+1 de p, ce qui, quand on écrit p = ∑_k=0^+∞ b_k+1·(½)^k+1, est finalement assez évident.)

Comment tirer un entier aléatoire entre 0 et n−1 à partir de bits aléatoires ? (Ma première réaction en entendant ce problème a été de dire : considérer x uniforme dont l'écriture binaire est donnée par la suite des bits tirés, générer suffisamment de bits pour calculer la valeur de ⌊n·x⌋, où ⌊—⌋ désigne la partie entière, et renvoyer celle-ci. Ceci fonctionne, mais ce n'est pas le plus efficace. Un autre algorithme avec rejet consiste à générer r := ⌈log(n)/log(2)⌉ bits, qui, lus en binaire, donnent un entier aléatoire c entre 0 et 2^r−1, renvoyer c s'il est <n, et sinon tout recommencer. Mais ce n'est pas très efficace non plus, quoique dans des cas un peu différents.) Je décris ce problème plus en détails dans ce fil Twitter, mais donnons juste l'algorithme : on utilise deux variables internes à l'algorithme, notées v et c, qu'on initialise par v←1 et c←0 (il s'agit d'un réservoir d'entropie, et la garantie est que c est aléatoire uniformément réparti entre 0 et v−1) ; puis on effectue une boucle : à chaque étape, on génère un bit aléatoire b (valant 0 ou 1 avec probabilité ½ pour chacun, et indépendant de tous les autres, donc) et on remplace v ← 2v et c ← 2c+b ; puis on compare v avec n et c avec n : si v<n (ce qui implique forcément c<n) on continue simplement la boucle (il n'y a pas assez d'entropie) ; si v≥n et c<n, on termine l'algorithme en renvoyant la valeur c ; enfin, si c≥n, on effectue v ← v−n et c ← c−n et on continue la boucle. Le calcul du nombre moyen de tirages effectués est fastidieux (voir cette référence citée dans le fil Twitter référencée ci-dessus), mais c'est optimal.

L'algorithme que je viens de décrire s'adapte assez bien pour tirer un entier uniforme entre 0 et n−1 à partir d'une source de entiers uniformes entre 0 et m−1 (le cas que je viens de décrire est le cas m=2), autrement dit : comment fabriquer un dé à n faces à partir d'un dé à m faces ? Je n'ai pas vraiment envie de réfléchir à si c'est optimal (mise à jour : on l'a fait pour moi), mais c'est en tout cas assez élégant : on utilise deux variables internes à l'algorithme, notées v et c, qu'on initialise par v←1 et c←0 ; puis on effectue une boucle : à chaque étape, on génère un tirage aléatoire b entre 0 et m−1 à partir de la source dont on dispose et on remplace v ← m·v et c ← m·c+b ; puis on effectue la division euclidienne de v et de c par n : si les deux quotients calculés sont différents (⌊c/n⌋ < ⌊v/n⌋), on termine l'algorithme en renvoyant le reste c%n := c − n·⌊c/n⌋ de la division de c par n, tandis que si les deux quotients sont égaux, on remplace chacun par son reste, c'est-à-dire v ← v%n et c ← c%n et on continue la boucle.

Introduisons maintenant aussi des tirages continus.

[Lire la suite…]

Je parle souvent de maths un peu compliquées sur ce blog, alors pour changer (et pour me changer les idées) je vais parler de choses un peu plus simples : de géométrie plane, et plus précisément de points et de droites. Je voudrais évoquer un petit projet que j'ai — qui, comme beaucoup de projets que j'ai, risque de n'aboutir nulle part — et qui ferait intervenir les maths (pour le sujet de fond), la mécanique classique (pour l'animation), l'informatique (pour le calcul) et un côté artistique (parce que le but serait surtout de faire quelque chose de joli à regarder). Enfin, ça c'était l'idée initiale, sauf que, comme d'habitude quand j'écris une entrée dans ce blog (mais bon, c'est un peu l'idée, aussi), je suis tombé dans un terrier de lapin, je me suis perdu dans les méandres de ce que je dois raconter, et au final ça ne ressemble à rien.

J'ai expliqué par le passé (et souvent fait référence depuis au fait) que j'étais fasciné par la symétrie et par les objets mathématiques très symétriques. En même temps, il ne faut pas oublier que je suis géomètre, et au sein de la géométrie, j'aime beaucoup ce qui en est la forme la plus épurée, la géométrie projective (plane, disons) où il n'est question que de points et de droites. (Je faisais d'ailleurs souvent remarquer à mes élèves agrégatifs quand ils faisaient des développements sur les constructions à la règle et au compas qu'il pouvait être bienvenu de consacrer une certaine attention aux constructions à la règle seule, qui sont les constructions « pures » de la géométrie projective, où on ne peut que relier deux points à la règle et intersecter deux droites.)

À la croisée de ces deux intérêts, il y a la notion de configuration de points et de droites (dans le plan) : une configuration est simplement un ensemble fini de points et un ensemble fini de droites[#]. Les figures ci-contre à droite sont des exemples de configurations de neuf points et neuf droites telles que par chaque point de la configuration passent exactement trois droites et chaque droite passe par exactement trois points. Bien sûr, on peut voir sur cette figure d'autres points, à l'intersection de deux droites de la configuration, mais ceux qui sont des points de la configuration sont uniquement ceux que j'ai marqués en rouge, pas n'importe quel point que vous pouvez voir comme intersection de deux droites (et symétriquement, on peut considérer d'autres droites en reliant deux des points, mais ceux qui sont des droites de la configuration sont celles qui ont été tracées, pas n'importe quelle droite que vous pouvez faire apparaître en reliant deux points).

[#] Pour éviter de considérer des objets sans intérêt, on demandera que chaque point de la configuration soit situé sur au moins une des droites de la configuration (sinon c'est un point isolé qui ne sert à rien), voire deux (sinon c'est un point isolé sur sa droite), voire trois (sinon c'est juste le marqueur d'une intersection), et symétriquement, que chaque droite passe par au moins un des points, voire deux, voire trois. De toute façon, comme je le dis plus bas, on demande en général que la configuration soit régulière, c'est-à-dire que par chaque point passe le même nombre q de droites et que chaque droite passe par le même nombre k de points.

Je ne veux pas parler longuement des configurations de points et de droites, parce que ce n'est pas tellement mon sujet, mais disons-en quand même quelques mots. (Enfin, quelques mots qui, comme d'habitude, se sont multipliés en quelques pages.) Ceux qui veulent juste savoir ce qu'est mon projet peuvent sauter directement plus bas.

Généralement on s'intéresse aux configurations possédant un certain degré de régularité, au moins numérique, c'est-à-dire que par chaque point passe le même nombre de droites et chaque droite passe par le même nombre de points (voire que ces deux nombres sont égaux, ce qui est le cas sur mes exemples), voire un certain degré de symétrie. Spécifiquement, on dit qu'une configuration est de type (p_q,n_k), où p,q,n,k sont quatre entiers ≥2 (ou en fait plutôt ≥3), lorsqu'elle comporte p points et n droites, que par chaque point passent q droites et que chaque droite passe par k points (ces informations sont donc redondantes et on a pq = nk, ce qui se voit en comptant le nombre total d'incidences d'un point et d'une droite) ; la plupart des textes sur les configurations de points et droites utilisent le mot configuration pour désigner spécifiquement les configurations régulières, c'est-à-dire celles qui sont de type (p_q,n_k) pour certains paramètres p,q,n,k≥3. Lorsque de plus p=n (ou ce qui revient au même, q=k), on dit simplement qu'on a affaire à une configuration de type (n_k), c'est-à-dire n points, n droites, chaque droite passant par k points et par chaque point passant k droites : mes figures à droite sont donc des configurations de type (9₃).

Pour être plus précis, je dois distinguer la notion de configuration abstraite et de réalisation géométrique de la configuration : deux configurations géométriques ont la même configuration abstraite lorsqu'on peut étiqueter (i.e., donner des noms, ce que je n'ai volontairement pas fait sur les figures ci-contre) aux points et aux droites des deux configurations de manière à ce qu'elles se correspondent avec les mêmes incidences, c'est-à-dire que si la droite nommée ℓ passe par le point nommé P sur une figure, ça doit aussi être le cas sur l'autre. (Cela pourrait être le cas parce qu'on a déplacé juste un petit peu les points et les droites d'une des figures pour former l'autre, mais ce n'est pas forcément le cas qu'on puisse passer continûment de l'une à l'autre.) Une configuration abstraite est donc la manière de demander quelles droites doivent passer par quels points (par exemple, un triangle abstrait consisterait à dire trois points A,B,C et trois droites a,b,c de manière que a passe par B et C, que b passe par C et A et que c passe par A et B ; et une réalisation géométrique de cette configuration abstraite est simplement un triangle).

Bref, une configuration abstraite est simplement la donnée de deux ensembles finis d'objets, arbitrairement appelés points et droites, et d'une relation d'incidence entre points et droites (on peut dire qu'une droite [abstraite] passe par un point [abstrait] lorsque cette relation est satisfaite) ; si on veut, c'est un graphe bipartite ; et on demandera en outre qu'il existe au plus une droite incidente avec deux points distincts donnés et au plus un point incident avec deux droites distinctes données (ceci correspond au fait que, dans le plan, deux points distincts définissent une droite et que deux droites distinctes se coupent en au plus un point). Une réalisation géométrique d'une configuration abstraite est une façon de trouver des points distincts et des droites distincts dans le plan (encore qu'il faut préciser quel plan : plan euclidien, ou ce qui revient au même, affine réel, plan projectif réel, ou des plans affines ou projectifs différents), en correspondance avec la configuration abstraite à réaliser, de façon qu'une droite passe par un point exactement quand l'incidence a lieu dans la configuration abstraite.

Il y a donc plusieurs questions qui se posent naturellement : quelles sont les configurations abstraites possibles ? (peut-on, par exemple, les dénombrer ? les classifier ? a priori non, cela reviendrait en gros à classifier les graphes bipartites, ce qui n'a guère de sens, il y a juste trop de possibilités, mais on peut s'intéresser à celles qui vérifient certaines contraintes, par exemple ont beaucoup de symétries ; ou on peut simplement en chercher qui sont particulièrement remarquables et intéressantes, et je vais donner quelques exemples ci-dessous) ; parmi elles, quelles sont celles qui sont réalisables ? (peut-on tester ce fait efficacement sur tel ou tel corps ? je dois mentionner que cela revient en fait à tester si un système d'équations polynomiales tout à fait général a des solutions, ce qui est décidable mais très coûteux sur les complexes, décidable mais extraordinairement coûteux sur les réels, et possiblement indécidable sur les rationnels) ; puis on peut encore se poser des questions sur les réalisations d'une configuration donnée, par exemple peut-on passer continûment de l'une à l'autre ? Malheureusement, je doute qu'on puisse dire quoi que ce soit de vraiment intelligent sur aucune de ces questions à ce niveau de généralité (il faut se contenter de résultats du type : pour tout n≥9, il existe au moins une configuration géométrique de type (n₃) dans le plan euclidien).

Il n'est pas toujours évident, visuellement, de reconnaître quand une configuration abstraite est la même qu'une autre. Par exemple, les trois configurations (9₃) ci-dessus à droite sont distinctes non seulement géométriquement (c'est évident) mais même abstraitement ; et celle qui est ci-contre à gauche, est une réalisation géométrique (différente) d'une des trois configurations abstraites en question, et ce n'est pas forcément immédiat de reconnaître laquelle ! Le lecteur saura-t-il reconnaître laquelle, et saura-t-il montrer que les trois de départ sont bien distinctes ? Pour ça, on peut suggérer l'indication consistant à relier (d'une couleur différente, disons) les paires de points qui ne sont pas situées sur une même droite de la configuration, et regarder le graphe ainsi formé (par exemple, y a-t-il des triplets de points dont aucune paire n'est située sur une droite de la figure ? combien de tels « anti-triangles » y a-t-il ?).

Plus difficile, on peut chercher à montrer qu'il n'y a que trois configurations (9₃) abstraites possibles, et que je les ai donc toutes les trois réalisées géométriquement. (La plus en haut, (9₃)①, s'appelle la configuration de Pappus, parce qu'elle est celle qui intervient dans l'énoncé du théorème de Pappus.) Il y a une unique configuration (8₃) abstraite possible, la configuration de Möbius-Kantor, mais elle n'est pas réalisable géométriquement dans le plan réel même si elle l'est sur les complexes (on peut par exemple l'obtenir en retirant un point et les droites qui vont avec à une autre, de type (9₄,12₃) celle-là, la configuration de Hesse, elle aussi non réalisable sur les réels mais réalisable sur les complexes, qui est celle des neuf points d'inflection d'une courbe cubique lisse). Il y a aussi une unique configuration (7₃) abstraite possible, la configuration de Fano, mais celle-ci n'est réalisable que sur un corps de caractéristique 2.

[Lire la suite…]

Je continue dans ce billet de blog une série sur l'épidémiologie mathématique que j'avais commencée avec cette entrée sur le modèle SIR classique, celle-ci sur une variante de SIR où le rétablissement se fait en temps constant, accessoirement celle-ci sur la différence entre seuil d'immunité collective et taux d'attaque, et plus indirectement celle-ci sur des modèles d'hétérogénéité basés sur les graphes aléatoires ; je ne présuppose pas la lecture des billets en question, même si celle du premier a un intérêt, mais je vais en résumer rapidement le contenu.

Mon but aujourd'hui est d'expliquer un peu en détails, mathématiquement, comment on peut modifier le modèle SIR classique (dont le vais rappeler les grandes lignes dans un instant), lequel décrit l'évolution d'une épidémie dans laquelle tout le monde est également susceptible à l'infection, pour le cas d'une susceptibilité hétérogène, c'est-à-dire que certains individus sont plus ou moins susceptibles d'être infectés (= ont plus ou moins de chances d'être infectés dans des circonstances identiques), et on va voir que ces hétérogénéités de susceptibilité ont un impact important. (Je ne me prononce pas sur la cause de ces différences de susceptibilité : elles pourraient être dues à des différences biologiques — certaines personnes s'infectent plus facilement que d'autres — ou sociales — certaines personnes sont plus fréquemment exposées à des conditions infectieuses. Néanmoins, comme le modèle que je vais développer ici suppose que la variation de susceptibilité n'est pas corrélée à une variation d'infectiosité, c'est-à-dire que les personnes plus susceptibles ne sont pas spécialement plus infectieuses — si c'était le cas l'effet que je décris ici serait encore plus accentué — il vaut peut-être mieux imaginer le cas d'une origine biologique, parce qu'une hétérogénéité sociale a plus de chances d'être symétrique.)

Ce qui est assez surprenant, c'est que cette idée, qui peut paraître compliquée à traiter, complique en fait extrêmement peu le modèle SIR, et qu'on peut trouver des réponses exactes à essentiellement les mêmes questions que pour SIR classique (du genre quel est le nombre maximal d'infectés ?) dans ce cadre plus complexe, donnée la distribution (initiale) de susceptibilité dans la population. En général les réponses feront intervenir la transformée de Laplace de la distribution de susceptibilité (je vais expliquer ce que c'est plus bas), mais dans un cas particulier assez naturel (celui d'une distribution Γ, par exemple la distribution exponentielle), on peut tout traiter complètement.

[Un résumé de ce post de blog est contenu dans ce fil Twitter (17 tweets ; ici sur ThreadReaderApp), pour ceux qui préfèrent ce format ou qui veulent surtout les points importants (noter que tweet 11/17 il y a une typo, il faut lire φ′(0)=−1 et pas φ′(0)=1). ※ Une version anglaise (un petit peu plus longue) est contenu dans ce fil Twitter (25 tweets ; ici sur ThreadReaderApp).]

Ajout (2021-11-06) : Comme je commence à avoir écrit pas mal de choses au sujet d'épidémiologie sur Twitter, voici un méta-fil (ici sur ThreadReaderApp) rassemblant les plus importants fils que j'ai pondus.

❦

Je commence par rappeler les grandes lignes du modèle SIR classique.

Le modèle SIR classique, donc, étudie l'évolution d'une épidémie dans une population en distinguant trois classes d'individus : les Susceptibles, les Infectieux (qui dans ce modèle sont les mêmes que les infectés) et les Rétablis (qui sont immuns — ou, en fait, morts). Parmi les nombreuses hypothèses simplificatrices faites par ce modèle, il y a les suivantes (j'en oublie certainement) : l'immunité acquise par l'infection est parfaite et permanente, les individus sont infectieux dès qu'ils sont infectés, et ils vont donc soit rester dans l'état S, soit passer succesivement par les étapes S,I,R ; la population est homogène, c'est-à-dire que tous les individus sont également susceptibles et également infectieux une fois infectés, ils ont les mêmes probabilités de se faire infecter, la taille de la population est constante, et elle est assez grande pour être traitée de façon continue déterministe, et les contacts obéissent à une hypothèse de mélange parfait (au sens où tous les contacts sont également plausibles) ; le comportement de la population est constant dans le temps et notamment indépendant de l'évolution de l'épidémie ; les contaminations et le rétablissement obéissent à une cinétique du premier ordre I+S → I+I et I → R respectivement, avec des constantes β (d'infectiosité) et γ (de rétablissement) respectivement, c'est-à-dire le nombre de nouveau infectés par unité de temps est simplement proportionnel au produit du nombre d'infectieux par le nombre de susceptibles, et que le nombre de nouvellement rétablis est simplement proportionnel au nombre d'infectieux.

Bref, si on note s,i,r (quantités réelles entre 0 et 1, fonctions du temps) les proportions de la population formées d'individus susceptibles, infectieux et rétablis respectivement, alors les nouvelles infections par unités de temps se représentent par le terme β·i·s, et les rétablissements par γ·i, du coup le modèle SIR est décrit par le système d'équations différentielles ordinaires (autonomes) du premier ordre suivant :

• ds/dt = −β·i·s
• di/dt = β·i·s − γ·i
• dr/dt = γ·i
• (s+i+r=1)

où on impose en outre généralement les conditions initiales telles que s(−∞)=1, i(−∞)=0 et r(−∞)=0 (je parle bien sûr des limites en −∞), avec i croissant exponentiellement pour t assez proche de −∞ (cf. ci-dessous). La constante β d'infectiosité représente le nombre moyen de personnes qu'une personne infectieuse donnée infecte par unité de temps dans une population entièrement susceptible, tandis que la constante γ de rétablissement représente la proportion moyenne d'infectés qui se rétablissent par unité de temps (donc l'inverse du temps moyen de rétablissement, le temps de rétablissement suivant en fait une loi exponentielle). Notons que β peut aussi, symétriquement, se comprendre comme une constante de susceptibilité, c'est-à-dire comme le nombre moyen de personnes par lesquelles une personne susceptible donnée sera infectée par unité de temps dans une population entièrement infectieuse : c'est la raison pour laquelle je parlerai tantôt de β comme représentant une infectiosité et tantôt une susceptibilité (et comme ici on veut modéliser des variations de susceptibilité, c'est plutôt le deuxième qui va être mis en lumière).

Rappelons quelques uns des points saillants de ce modèle concernant le début, le pic et la fin de l'épidémie, résumé que je recopie de ce billet (plus exactement, comme je viens de le dire, on s'intéresse aux solutions pour lesquelles s→1 quand t→−∞) ; on notera κ := β/γ le nombre de reproduction, que je suppose >1 :

• tant que s reste très proche de 1 (si on veut, t→−∞), les proportions i et r croissent comme des exponentielles de pente logarithmique β−γ = β·((κ−1)/κ), avec un rapport 1/(κ−1) entre les deux, autrement dit comme i = c·exp((β−γ)·t) = c·exp(β·((κ−1)/κ)·t) et r = c·(γ/(β−γ))·exp((β−γ)·t) = c·(1/(κ−1))·exp(β·((κ−1)/κ)·t) (ergotage : dans l'entrée sur le sujet, j'avais mis un −1 aux exponentielles pour r, parce que je voulais partir de r=0, mais je me rends compte maintenant qu'il est plus logique de partir d'une solution où i/r tend vers une constante en −∞, cette constante étant κ−1) ;
• au moment du pic épidémique (maximum de la proportion i d'infectieux), on a s = 1/κ et i = (κ−log(κ)−1)/κ et r = log(κ)/κ ; notamment, le moment où l'épidémie commence à régresser correspond à i+r = 1 − 1/κ (seuil d'immunité collective) ;
• quand t→+∞, la proportion i tend vers 0 (bien sûr) et s tend vers Γ := −W(−κ·exp(−κ))/κ (en notant W la fonction de Lambert) l'unique solution strictement comprise entre 0 et 1 de l'équation Γ = exp(−κ·(1−Γ)) (qui vaut 1 − 2·(κ−1) + O((κ−1)²) pour κ proche de 1, et exp(−κ) + O(κ·exp(−2κ)) pour κ grand), tandis qu'évidemment r, lui, tend vers 1−Γ (taux d'attaque final).

J'ai parlé dans cette entrée de la différence entre seuil d'immunité collective et taux d'attaque final (qui sont les deux quantités essentielles que le modèle calcule) dans le modèle SIR.

*

[Lire la suite…]

Interrompons un petit peu la succession de rants au sujet du covid pour parler un peu de maths. Je déterre pour le terminer un vieux texte que j'avais commencé il y a environ deux ans et que j'avais abandonné, mais auquel je repense parce que j'ai reréfléchi à des questions adjacentes. Le but est ici de définir un concept à cheval entre la logique et la calculabilité qui s'appelle la réalisabilité de Kleene. Plus tard (un jour, si j'en trouve le temps et la patience) j'aimerais parler du topos effectif, et comme le topos effectif contient (généralise, donne un cadre catégorique à) la réalisabilité de Kleene, il sera utile que j'aie au moins écrit à ce sujet avant, même si en principe on n'a pas besoin de passer par cette étape intermédiaire. [Ajout : le billet sur le topos effectif est ici.]

Tout ceci a un rapport avec la logique intuitionniste : j'ai déjà écrit un post de blog à ce sujet, qu'il peut être utile d'avoir lu, mais il faut admettre qu'il est extrêmement brouillon et mal structuré [ajout : celui-ci, écrit ultérieurement, est sans doute bien plus clair]. En tout état de cause, il n'est pas nécessaire de savoir ce que c'est que la logique intuitionniste pour comprendre la définition de la réalisabilité de Kleene. (Le principal prérequis à ce qui va suivre est de savoir les bases de la calculabilité : ce qu'est une machine de Turing — ou toute autre représentation des fonctions partielles calculables —, et savoir qu'on peut les encoder par des entiers naturels ; donc comprendre une expression comme le résultat de l'exécution de la machine de Turing codée par l'entier e sur l'entier n en entrée. c'est-à-dire l'image de n par la e-ième fonction calculable partielle, qui sera noté e•n ci-dessous.) Néanmoins, comme la réalisabilité de Kleene est compatible avec les règles de la logique intuitionniste (elle réalise tous les théorèmes de l'arithmétique de Heyting), et est inspirée par (et rend rigoureux) les principes (informels) de Brouwer-Heyting-Kolmogorov, c'est bien d'en avoir au moins une idée ; cette connexion avec la logique intuitionniste sera encore plus forte dans le topos effectif : on peut dire sommairement qu'un topos est une sorte de « monde mathématique alternatif » régis par les lois de la logique intuitionniste (et le topos effectif est un tel monde où la calculabilité joue un rôle central et notamment toutes les fonctions ℕ→ℕ sont calculables).

Mais le but de cette entrée-ci n'est pas de décrire le topos effectif (pas qu'il soit très long à définir, mais ça devient long si on veut en dire le minimum pour que ce soit intéressant). C'est de présenter une notion plus ancienne, la réalisabilité de Kleene, qui sert de fondement ou de prolégomène à la construction du topos effectif. Je dois avouer que le sens profond de cette notion m'échappe encore, et j'ai vaguement l'impression que personne ne la comprend aussi profondément qu'il voudrait ; je ne sais même pas bien ce que Kleene cherchait à faire en introduisant cette notion. Mais superficiellement, l'idée est qu'on définit une notion que je vais noter n ⊪ φ, lire n réalise φ, entre un entier naturel n et une formule logique φ de l'arithmétique du premier ordre (je vais rappeler ce que c'est plus bas), et dont le sens intuitif est que n apporte une sorte de témoignage(?) algorithmique de la véracité de φ (néanmoins, on va voir que φ n'est pas forcément vraie dans le monde classique, et il va s'agir d'expliquer le rapport entre ces notions).

Le rapport avec le topos effectif sera notamment que les énoncés arithmétique du premier ordre qui sont réalisables (au sens où il existe un n qui les réalise) seront exactement ceux qui seront vrais dans le topos effectif. En particulier, la réalisabilité permet de faire un pont vers la logique intuitionniste, même en partant de la logique classique : on n'a pas besoin de savoir ce qu'est la logique intuitionniste ni comment elle fonctionne pour définir la relation n ⊪ φ, mais une fois qu'on l'a définie, on constate qu'elle fonctionne de façon fondamentalement intuitionniste en φ (et notamment, réaliser la double négation ¬¬φ n'est pas du tout pareil que réaliser φ). Par ailleurs, la relation n ⊪ φ est elle-même une formule logique (avec une variable n de plus que la formule de départ), on peut se demander sous quelle condition elle-même est réalisable, ou démontrable (ou démontrablement réalisable), etc., et les réponses sont assez satisfaisantes.

Ajout : ce billet ultérieur, sur la réalisabilité propositionnelle (qu'on peut lire avant, ou après, ou indépendamment) a aussi un rapport étroit avec celui-ci, puisque la réalisabilité propositionnelle est la logique propositionnelle interne du topos effectif de même que la réalisabilité de Kleene dont il est question ici est l'arithmétique du premier ordre dans le topos effectif.

Avant de donner la définition, je dois rappeler des choses sur la logique, qu'on peut sans doute se contenter de lire en diagonale parce que ce qui suit est vraiment standard et peu surprenant.

Pour être tout à fait exact, je définis par les mêmes clauses énumérées ci-dessus deux variantes de la réalisabilité : il y a une notion dans l'univers mathématique, si j'ose dire, ambiant (n étant un entier naturel et φ une formule de l'arithmétique du premier ordre, n ⊪ φ a le sens défini par les clauses ci-dessus), et il y a une réalisabilité formalisée qui consiste à voir les clauses ci-dessus elles-mêmes dans l'arithmétique du premier ordre, c'est-à-dire qu'on va définir, par exemple, n ⊪ (φ∧ψ) comme la formule ∃n.(n=⟨p,q⟩ ∧ (p⊪φ) ∧ (q⊪ψ)) et ainsi de suite. Il n'y a pas forcément besoin de distinguer ces deux notions, mais il est important de noter que la réalisabilité peut être formalisée, et donc que n ⊪ φ est elle-même une formule de l'arithmétique du premier ordre (pour n une variable libre n'apparaissant pas libre dans φ). (Ce n'est pas tellement différent de la formalisation de la notion de démonstration : l'affirmation φ est démontrable dans l'arithmétique de Peano, par exemple, est un énoncé arithmétique lorsque φ en est un : cf. ici pour plus d'explications.)

On lit n ⊪ φ en disant que n réalise φ ou que φ est réalisée par n, et ∃n.(n⊪φ) en disant que φ est réalisable.

[Lire la suite…]

Je veux écrire ici une petite note sur un point que je pense avoir mal expliqué par le passé, et autour duquel il existe une certaine confusion. Il s'agit du rapport entre le seuil d'immunité grégaire d'une part et le taux d'attaque final d'une épidémie d'autre part : quelle est la différence entre ces deux concepts, que penser de l'écart, ou overshoot entre ces deux quantités, et laquelle est la plus pertinente en pratique. Il faudra bien distinguer le cas du modèle théorique SIR et le cas d'une épidémie réelle (et pour faire la transition de l'un à l'autre, j'évoquerai rapidement un modèle SIR « en deux phases »).

Le seuil d'immunité grégaire (ou …collective, peut-être un meilleur terme parce qu'il évoque moins l'image déplaisante d'un troupeau, mais comme j'ai commencé avec grégaire je préfère maintenant rester dessus) est la proportion d'immuns qu'il faut atteindre dans la population pour que le nombre de reproduction effectif de l'épidémie devienne <1. Autrement dit :

• soit on considère une épidémie naissante, c'est-à-dire qu'il n'y a que très peu d'infectés, mais pour laquelle un certain nombre d'individus sont préalablement immunisés (par exemple par un vaccin) : alors le seuil d'immunité grégaire est le nombre d'immunisés nécessaires pour que l'épidémie ne démarre pas (son nombre de reproduction est <1 donc le petit nombre d'infectés disparaît simplement) ;
• soit on considère une épidémie déjà en cours, et dans ce cas le fait qu'on atteigne le seuil d'immunité grégaire se voit au fait que le nombre d'infectés commence à décroître, c'est-à-dire qu'il y en a de moins en moins (le nombre de reproduction est <1 donc ce nombre diminue progressivement).

Par contraste, le taux d'attaque final (qui n'a de sens qu'en considérant le cours d'une épidémie particulière) est la proportion d'individus qui seront atteints par l'épidémie pendant toute sa durée.

Même si on suppose que l'immunité est parfaitement stérilisante et dure indéfiniment (ce que je ferai pour simplifier, ce n'est pas le propos ici de discuter de ces questions), ces deux quantités sont différentes : la raison est simple, c'est que même une fois que le seuil d'immunité grégaire est atteint, le nombre d'infectés commence certes à diminuer, mais il n'est pas nul pour autant, donc il y a de l'inertie : ce nombre d'infectés en infecte un plus petit nombre, qui en infecte à son tour un encore plus petit nombre, et ainsi de suite, mais la somme de tout ça n'est pas nulle.

La différence entre ces deux quantités s'appelle l'overshoot de l'épidémie : i.e., l'overshoot est la proportion qu'elle attaque en plus du seuil d'immunité grégaire.

Dans le cas du modèle théorique (ultra-simpliste) SIR, on peut calculer explicitement ces deux quantités. Je l'ai fait dans l'entrée que j'ai écrite à ce sujet, mais je n'ai pas été clair parce que je n'avais pas la bonne terminologie (j'ai parlé de modèle extrêmement simpliste pour une description qui calcule, en fait, le seuil d'immunité grégaire, ce qui a pu augmenter la confusion), je redis donc les choses un peu autrement : en notant κ le nombre basique de reproduction (lettre que je préfère à R parce que le R de SIR a un sens différent), c'est-à-dire le nombre de reproduction pour une population immunologiquement (et sociologiquement) naïve :

• le seuil d'immunité grégaire r_herd dans le modèle SIR se calcule à partir du nombre basique de reproduction κ par la formule r_herd = 1 − 1/κ (la démonstration est facile : lorsqu'une proportion s des individus est susceptible, le nombre de reproduction effectif tombe de κ à κ·s simplement parce que chaque contact possiblement infectieux a cette probabilité de donner effectivement une infection, du coup pour avoir κ·s = 1 on doit avoir s = 1/κ et cela correspond à la proportion complémentaire r = 1 − 1/κ d'immuns au final) ;
• le taux d'attaque final r_∞ dans le modèle SIR se calcule à partir du nombre basique de reproduction κ par la formule r_∞ = 1 + W(−κ·exp(−κ))/κ où W désigne la fonction transcendante W de Lambert (j'ai déjà démontré cette formule dans mon entrée passée sur le sujet).

J'ai tracé ces deux courbes ci-contre en fonction du nombre de reproduction κ : en rouge le seuil d'immunité grégaire, et en bleu le taux d'attaque final. Rappelons en outre, pour ce qui est du comportement asymptotique que [encore une fois, tout ça je l'ai déjà dit, mais avec une terminologie qui n'était pas claire] :

• si le nombre basique de reproduction κ est juste un peu au-delà de 1, disons 1 + h avec h>0 petit, alors le seuil d'immunité grégaire r_herd vaut h − h² + O(h³) tandis que le taux d'attaque final r_∞ vaut 2·h − (8/3)·h² + O(h³), donc en gros le double (ce qui se conçoit grosso modo par le fait que les deux périodes de l'épidémie sont alors symétriques, celle où elle est croissante jusqu'au seuil d'immunité grégaire, et celle d'overshoot où elle est décroissante jusqu'à tendre vers son taux d'attaque final),
• si le nombre basique de reproduction κ est grand, alors le seuil d'immunité grégaire r_herd vaut 1 − 1/κ (il n'y a rien à simplifier) tandis que le taux d'attaque final r_∞ vaut 1 − exp(−κ) − κ·exp(−2κ) + O(κ²·exp(−3κ)), qui devient vite extrêmement proche de 1.

[Lire la suite…]

Pendant que j'étais occupé à ne pas écrire dans ce blog, les sujets sur lesquels j'aurais pu écrire quelque chose se sont accumulés. Je veux dire, les sujets sur lesquels soit j'ai appris quelque chose et j'aurais pu/dû le braindumper ici pour me simplifier la vie quand j'aurais plus tard oublié et voulu réapprendre, soit je me suis simplement dit que c'était quelque chose de potentiellement intéressant dans quoi je devrais me plonger si j'avais le temps. Bref, voici une liste de quelques choses sur lesquels je n'ai rien écrit, et il n'est pas impossible que j'y revienne, mais il ne faut pas compter dessus non plus. Pas un TODO, mais un MIGHTDO, si on veut.

(Les différentes parties qui suivent n'ont généralement aucun rapport entre elles. C'est bien le problème, si j'ose dire, de trop aimer l'éclectisme. Par ailleurs, elles mélangent des sujets où j'ai quelques trucs à expliquer (mais je ne le fais pas vraiment ici) et d'autres où j'ai simplement des questions à poser, ou encore où je n'ai rien à dire mais que j'utilise simplement comme memento pour me rappeler que c'est quelque chose d'intéressant à visiter ou revisiter un jour. Les explications, ou les absences d'explications, qui suivent, se placent aussi à des niveaux très variés de prérequis mathématiques.)

Liens vers les sous-parties de cette entrée : • Mandelbrot • inégalités de Bell • topologie sans points • axiome de Scott • topos effectif • complexité au-delà du calculable • algèbres de Jordan • problème du secrétaire • mécanique sphérique • surface de Bring • Cayley-Bacharach • le spectre des polynômes à valeurs entières

[Lire la suite…]

Même si mon moral est moins mauvais, je continue à avoir beaucoup de mal à faire autre chose que de l'épidémiologie. Du coup, je vais en parler encore une fois, pour présenter une approche différente du calcul du taux d'attaque, qui permet cette fois-ci d'illustrer (par des considérations théoriques plutôt que des simulations numériques) certains effets d'hétérogénéité. (Il s'agit d'une traduction+développement de ce que j'ai écrit dans ce fil Twitter [lien direct Twitter] ainsi que celui-ci [lien direct Twitter], et secondairement, de ce fil [lien direct Twitter] plus ancien.) Mais je commence par quelques remarques d'ordre méta sur ces effets d'hétérogénéité et les épidémiologistes de fauteuil (si ça ne vous intéresse pas, sautez après).

On (un des auteurs !) a enfin fini par me pointer du doigt un livre (et donc une référence citable !) où étaient traitées les probématiques épidémiologiques qui me préoccupaient : il s'agit de Mathematics of Epidemics on Networks (From Exact to Approximate Models) d'István Z. Kiss, Joel C. Miller et Péter L. Simon (Springer 2017). Non seulement il traite exactement tout ce que je voulais voir traité, mais la présentation est vraiment très agréable pour le mathématicien que je suis : les énoncés sont précis, les approximations sont expliquées avec soin, les notations ne sont pas trop pénibles, bref, je le recommande très vivement. (Quel dommage que toutes les bibliothèques soient fermées… Si seulement il y avait un site web — qui pourrait par exemple porter le nom en anglais d'une bibliothèque et du premier livre de la Bible — où on pourrait trouver les PDF de ce genre de choses. Ah non, zut, ce serait illégal, parce qu'on a des lois à la con qui empêchent la diffusion des connaissances. Mais pardon, je digresse.)

Il y aurait peut-être à analyser la raison pour laquelle j'ai réussi à passer à côté de cet excellent ouvrage jusqu'à tout récemment. (Il est possible qu'on me l'ait déjà suggéré et que je sois quand même passé à côté de la suggestion, parce que le mot networks ne m'inspirait pas : en fait, il s'agit de graphes, il y a apparemment des gens qui, parce qu'ils ont une approche un peu différente, parlent de réseaux pour parler de graphes, et notamment de graphes aléatoires, ce qui est leur droit mais ça ne facilite pas la communication. J'aimerais quand même bien comprendre, par exemple, pourquoi si on recherche Galton-Watson "attack rate" dans Google, les deux premières réponses sont de moi, alors que ça a quand même l'air d'être des termes très naturels à rechercher dans le contexte de la propagation des épidémies, et d'ailleurs le livre que je viens de mentionner devrait être dans les résultats, et beaucoup plus haut qu'un tweet à moi.) Mais je ne vais pas m'étendre là-dessus, en tout cas pas maintenant.

Bref, toujours est-il que j'ai été soulagé de voir que tout un tas de phénomènes que je voulais voir étudiés, et que j'avais au moins en partie redécouverts, comme ce que je vais décrire ci-dessous, étaient effectivement étudiés quelque part, et que j'aurai des références citables à montrer. J'ai l'habitude de redécouvrir des résultats connus, je dirais même que ça fait partie du fonctionnement normal de la science, et quand je l'apprends je suis plutôt content que mon intuition ne soit pas complètement à côté de la plaque.

En revanche, je demeure perplexe quant au fait que ces phénomènes soient bien connus ou non des épidémiologistes. Il y a deux prépublications qui sont sorties récemment, une sur l'arXiv (par des matheux) et une autre sur medRxiv (par des épidémiologistes plus médecins, ça se voit au fait qu'ils déposent sur medRxiv et n'utilisent pas TeX ), qui font tous les deux la même observation, évidemment formulée et argumentée de façon plus précise, que j'écrivais dans cette entrée de blog ou de façon concise dans ce tweet (en mars) : l'épidémie va atteindre, et donc immuniser, les personnes les plus connectées en premier, ce qui fait que l'hétérogénéité des contacts contribue à réduire le seuil d'immunité à partir duquel elle se met à régresser (le premier de ces documents calcule 43%, ce qu'il ne faut pas, à mon avis, prendre comme une prédiction mais comme un ordre de grandeur grossier de l'effet qu'on peut attendre). D'un côté, il semble que ce type d'effet ait été étudié depuis 1980 (au plus tard). Mais de l'autre, un épidémiologiste renommé (Marc Lipsitch) semble considérer que c'est intéressant et vaguement nouveau, et il y en a qui n'ont pas reçu le message (et ce n'est qu'un exemple parmi d'autres où j'ai vu affirmer, y compris de la part de personnes qui sont des épidémiologistes ou qui ont une formation proche, que puisque R₀~3 on doit atteindre ~70% d'immunisés pour que l'épidémie régresse). Donc il y a, au minimum, un problème de communication. Ce n'est pas très grave, maintenant j'ai au moins quelque chose d'un peu plus crédible (un PDF !) à citer pour contester cette idée (et le fait que Marc Lipsitch prenne ça au sérieux est bien puisque c'est lui qui est à l'origine, d'avoir popularisé le chiffre de 70% comme taux d'attaque, même s'il l'a immédiatement nuancé). Mais ça reste un peu pénible d'avoir l'impression d'être le crackpot qui vient contredire les experts qui ont dit que c'était 70%. (Un peu quand comme l'OMS a fait une communication un peu hâtive en affirmant qu'il n'y avait aucun signe que l'infection par le Covid-19 confère une quelconque forme d'immunité, alors que quand même, si, il y a des raisons de le penser : ce n'est vraiment pas une position confortable que de tenir le discours je ne suis pas du tout médecin, mais je vais quand même remettre l'OMS à sa place sur une question de médecine. Bon, je digresse encore.)

PS : D'ailleurs, on me souffle que j'ai peut-être contribué à diffuser ces idées. Tant mieux si c'est le cas.

❦

[Lire la suite…]

Il y a quatre éternités semaines, quand nous n'étions pas encore maintenus prisonniers chez nous, j'ai parlé ici du modèle épidémiologique SIR, le plus basique qui soit. Je rappelle brièvement les principes qui le définissent :

• l'immunité acquise est permanente, les individus sont successivement S (susceptibles, c'est-à-dire jamais infectés donc susceptibles de l'être), I (infectés et infectieux) et R (rétablis, c'est-à-dire guéris ou morts) (il existe toutes sortes de variantes, par exemple le modèle SEIR ajoutant un état E (exposé) pour les individus infectés mais non encore infectieux) ;
• la population est homogène (fongible) avec mélange parfait dans les contacts (j'ai parlé ici de l'effet de modifier cette hypothèse) ;
• la contamination et le rétablissement se font selon une cinétique d'ordre 1, c'est-à-dire que la contamination se fait proportionnellement aux proportions d'infectés et de susceptibles (avec une constante cinétique β), et que le rétablissement se fait proportionnellement à la proportion d'infectés (avec une constante cinétique γ).

Rappelons brièvement ce que j'ai exposé la dernière fois. Les équations de ce modèle SIR basique, que j'appellerai (*) pour m'y référer plus tard, sont les suivantes (il s'agit d'un système d'équations différentielles ordinaires non-linéaire, du premier ordre et autonomes) :

• s′ = −β·i·s
• i′ = β·i·s − γ·i
• r′ = γ·i
• (s+i+r=1)

où s,i,r≥0 sont les proportions de susceptibles, d'infectieux et de rétablis dans la population ; les solutions de ces équations ne semblent pas pouvoir s'exprimer en forme close, mais on peut exprimer s en fonction de r (à savoir s = exp(−κ·r) dans les conditions exposées ci-dessous).

Je rappelle les principales conclusions que j'avais exposées dans mon entrée sur ce modèle (*), en supposant qu'on parte d'une population presque entièrement susceptible avec une proportion infinitésimale d'infectés (plus exactement, on s'intéresse aux solutions pour lesquelles s→1 quand t→−∞) ; on notera κ := β/γ le nombre de reproduction, que je suppose >1 :

• tant que s reste très proche de 1 (si on veut, t→−∞), les proportions i et r croissent comme des exponentielles de pente logarithmique β−γ = β·((κ−1)/κ), avec un rapport 1/(κ−1) entre les deux, autrement dit comme i = c·exp((β−γ)·t) = c·exp(β·((κ−1)/κ)·t) et r = c·(γ/(β−γ))·exp((β−γ)·t) = c·(1/(κ−1))·exp(β·((κ−1)/κ)·t) (ergotage : dans l'entrée sur le sujet, j'avais mis un −1 aux exponentielles pour r, parce que je voulais partir de r=0, mais je me rends compte maintenant qu'il est plus logique de partir d'une solution où i/r tend vers une constante en −∞, cette constante étant κ−1) ;
• au moment du pic épidémique (maximum de la proportion i d'infectés), on a s = 1/κ et i = (κ−log(κ)−1)/κ et r = log(κ)/κ ;
• quand t→+∞, la proportion i tend vers 0 (bien sûr) et s tend vers Γ := −W(−κ·exp(−κ))/κ (en notant W la fonction de Lambert) l'unique solution strictement comprise entre 0 et 1 de l'équation Γ = exp(−κ·(1−Γ)) (qui vaut 1 − 2·(κ−1) + O((κ−1)²) pour κ proche de 1, et exp(−κ) + O(κ·exp(−2κ)) pour κ grand), tandis qu'évidemment r, lui, tend vers 1−Γ.

Je veux ici explorer la modification d'une hypothèse de ce modèle (*), celle qui concerne le rétablissement. Quand j'écris ci-dessus que le rétablissement se fait proportionnellement à la proportion d'infectés (avec une constante cinétique γ), au niveau individuel, cela signifie la chose suivante :

Pendant chaque intervalle de temps de longueur (durée) dt très courte, la probabilité qu'un individu infecté (I) se rétablisse (I→R) vaut γ·dt et ce, indépendamment d'un individu à l'autre et d'un instant à l'autre.

Autrement dit, le temps de rétablissement d'un individu infecté donné suit une distribution de probabilité exponentielle d'espérance 1/γ.

Autant l'hypothèse analogue sur la cinétique de la contamination est relativement plausible (si on admet le principe éminemment discutable d'une population homogène et du mélange parfait !), autant l'hypothèse sur le temps de rétablissement est médicalement insensé : on est en train de dire que si vous êtes malade, votre probabilité de guérir (ou d'ailleurs, de mourir) ne dépend pas de l'avancement de votre maladie mais est la même pendant la première heure que pendant la 1729e (si tant est que vous soyez encore malade à ce stade-là). Une maladie ne se comporte pas comme ça !

Cherchons donc à remplacer cette hypothèse par une autre, tout aussi simpliste, mais néanmoins un peu plus proche de la réalité médicale, celle du rétablissement en temps constant.

Un individu infecté (I) se rétablit toujours au bout du même temps T après son moment d'infection.

Autrement dit, le temps de rétablissement d'un individu infecté donné suit une distribution de Dirac concentrée en T (qui est, du coup, son espérance).

[Lire la suite…]

Je suis vraiment débordé (le temps que je passe à me documenter sur l'épidémie et à répondre aux présentations biaisées et autres conneries sur Twitter représente une surcharge de travail absolument énorme qui s'ajoute au fait que tout est devenu tellement plus long et compliqué dans ma vie, je ne vais pas pouvoir tenir longtemps comme ça), donc je me contente ici de reproduire en français ce que j'ai écrit dans un fil Twitter :

Il s'agit d'expériences numériques sur l'influence de la structure du graphe social sur le taux d'attaque des épidémies (taux d'attaque = le nombre de personnes infectées cumulé pendant l'épidémie).

Rappelons la situation basique : j'ai déjà écrit ici sur mon blog (et ici en anglais sur Twitter) sur ce que prédit le modèle épidémiologique SIR au sujet du taux d'attaque. En bref, il prédit un taux d'attaque énorme : 89% (de la population touchée) pour un nombre de reproduction de 2.5. (La formule, comme je l'ai expliqué, est 1 + W(−κ·exp(−κ))/κ = 1 − exp(−κ) + O(κ·exp(−2κ)) où κ est le nombre de reproduction. Par ailleurs, il faut bien différencier ce taux d'attaque du seuil d'immunité grégaire qui, lui, vaut, 1 − 1/κ, et qui est le taux d'infectés à partir duquel l'épidémie commence à régresser, c'est-à-dire le taux d'attaque au pic épidémiologique.)

Or les épidémies réelles ne semblent pas avoir des taux d'attaque aussi énormes, même avec des nombres de reproduction de l'ordre de ce que je viens de dire. Bien sûr, on connaît mal le taux d'attaque même a posteriori, mais (malgré une absence d'immunité préalable aux souches) il semble que les grippes de 1918 et 1957 aient infecté autour de 30% de la population à différents endroits, pas franchement autour de 90%.

Alors que se passe-t-il ? Mon explication est que SIR, étant un modèle basé sur des équations différentielles, ne connaît qu'une seule chose, c'est la proportion de la population qui est susceptible, infectée et rétablie, et pas où ces personnes sont ni comment elles interagissent socialement.

Autrement dit, un tel modèle suppose un « mélange parfait » : tout individu a la même probabilité d'infecter n'importe quel autre individu. Ce n'est bien sûr pas du tout le cas dans la réalité. En réalité, une bonne proportion des contaminations suit un graphe social (famille, amis, collègues).

Même les modèles plus sophistiqués qui stratifient la population par catégories d'âge (disons) supposent toujours un mélange parfait dans chaque catégorie. Je soupçonne que c'est la raison pour laquelle le papier d'Imperial obtient un taux d'attaque si élevé (j'en ai déjà parlé dans cette entrée, voir aussi ce fil Twitter).

Alors, comment peut-on prendre en compte le fait que les contaminations suivent des graphes sociaux, et que doit-on en attendre ? Je m'attendais, et je voulais tester, deux effets apparentés mais distincts :

Le premier effet est que si l'épidémie doit suivre les liens d'un graphe social de connectivité relativement modeste (chacun n'ayant qu'un petit nombre de parents/amis/collègues par rapport à toute la population), elle va s'étouffer plus rapidement, même pour un nombre de reproduction donné, par rapport au cas de mélange aléatoire : c'est ce que j'ai essayé de dire ici sur Twitter ainsi que dans cette entrée dans la phrase la première [sous-raison] c'est (a) que quand on retire une proportion suffisamment élevées de sommets d'un graphe (en l'occurrence celui des contacts humains), il cesse de « percoler », c'est-à-dire qu'on ne peut plus passer d'un sommet à un autre. Ce phénomène est, en effet, lié à des questions de seuil de percolation dans les graphes (qui est, en gros, la proportion des sommets, ou des arêtes selon la définition, qu'il faut retirer aléatoirement à un graphe pour qu'il cesse d'avoir une composante connexe géante) : l'idée est que quand suffisamment de personnes (=sommets, =nœuds) sont immunisées, l'épidémie ne peut plus se propager d'un point à un autre : même avec l'hypothèse de mélange parfait le nombre d'immunisés ralentit l'épidémie, mais le seuil de percolation suggère qu'une proportion plus faible d'immunisés peut arrêter complètement la propagation (et, probablement, on la ralentit plus vite avant de l'arrêter complètement).

Le second phénomène est différent : non seulement il doit suffire de retirer relativement peu de nœuds pour arrêter l'épidémie (comme je viens de l'expliquer), mais en plus l'épidémie va retirer (c'est-à-dire infecter et rendre immuns) en premier les nœuds les plus « précieux » à sa propre propagation, parce que ce sont les nœuds les plus connectés, les « célébrités ». C'est ce que j'ai essayé d'exprimer ici et là (+ tweet suivant) sur Twitter, ainsi que dans la même entrée que mentionée dans la phrase (b) les infections ont tendance à infecter en premier les personnes qui sont hautement connectées dans le graphe, et en les rendant immunes, elle neutralise en premier les liens qui lui permettaient le plus facilement de se propager.

Tout ça n'est que mon intuition ! Maintenant, voyons si je peux modéliser ces phénomènes, pour au moins montrer qu'ils existent. Je ne vais pas chercher à quantifier les effets (il y a tout simplement trop de paramètres avec lesquels jouer), seulement d'illustrer qu'ils peuvent exister et semblent jouer dans la direction que je pensais.

J'ai donc écrit un petit programme Perl qui simule un modèle épidémique SEIR stochastique. SEIR, ça signifie que les nœuds (les individus) passent entre quatre états, S = susceptible = non-infecté, puis E = exposé = en incubation, puis I = infectieux et enfin R = rétabli = immunisé ou mort. Stochastique, ça signifie que plutôt que modéliser les choses avec des équations différentielles, je prends un grand nombre de nœuds (300 000 dans mes expériences) et les contaminations ont lieu au hasard. Ça rend les calculs non-reproductibles, mais cela permet de gérer des situations bien plus complexes qu'avec des équations différentielles.

[Lire la suite…]

Dans l'entrée précédente, je soulevais entre autres la question de comment calculer (et de comment appeler !) le nombre, que j'y appelais r, de personnes qui sont finalement infectés par une épidémie (quelle que soit l'issue de cette infection) puisque c'est un des facteurs du produit f·r qui donnera le taux de mortalité due à l'infection (l'autre étant la proportion f des cas qui conduisent à un décès) ou de tout autre calcul analogue (comme g·r pour le nombre de cas graves où g est la proportion correspondante). Dans plusieurs mises à jour ultérieures de cette entrée, j'ai signalé que j'ai fini par apprendre que r s'appelle le taux d'attaque et un raisonnement simpliste pour l'estimer, que je reproduis ici parce que je vais vouloir le comparer à une estimation donnée par un modèle différent :

[Essentiellement recopié de ce fil Twitter :] Une amie m'a expliqué le rapport que je cherchais à comprendre entre le taux de reproduction de base R₀ (= nombre de personnes que chaque personne infectée infecte à son tour) et le taux d'attaque final r (= proportion de la population qui sera infectée à terme pendant l'épidémie) : dans le modèle le plus simpliste, c'est r = 1 − 1/R₀ ; en effet, tant que le taux de reproduction est >1, l'épidémie croît exponentiellement ; mais si une proportion r a déjà été infectée, le taux effectif de reproduction est ramené à R₀·(1−r) parce que, en supposant que les personnes déjà infectées sont immunisées et sont également réparties dans la population (j'ai bien dit, modèle simpliste !), seule une proportion 1−r est encore susceptible d'être contaminée ; donc l'épidémie cesse de progresser lorsque R₀·(1−r) redescend à 1, c'est-à-dire r = 1 − 1/R₀. C'est probablement la raison pour laquelle certains ont prédit r ~ 70% en l'absence de contre-mesures efficaces pour réduire R₀ qui a été initialement mesuré à R₀ ~ 3. Encore une fois, ceci est un modèle extrêmement simpliste.

Dans la suite, je vais noter plutôt κ que R₀ ce nombre de reproduction, parce que même si R₀ est la notation standard elle serait source de confusion dans le modèle SIR où la lettre R désigne les cas rétablis (guéris, recovered en anglais ; enfin, avec une drôle de définition de rétablis puisque dans le modèle qui va suivre on ne cherche pas à compter les décès et on les compte avec les guérisons). Par ailleurs, plutôt que le taux d'attaque final noté r ci-dessus (ce qui, par chance, colle bien, à la limite, avec l'usage de la lettre R que je viens d'évoquer), je vais m'intéresser plutôt à la proportion complémentaire s = 1−r, i.e., la proportion de la population qui échappe à l'épidémie, et dont le raisonnement simpliste que je viens de recopier prédit donc qu'il s'agit de 1/κ.

Maintenant, en suivant de près ce fil Twitter (ou ici sur Thread Reader), que je développe un peu un peu, je vais essayer d'expliquer la prédiction que fait un modèle basique en épidémiologie, le modèle SIR :

Le modèle SIR modélise une infection en traduisant l'évolution dans le temps de trois variables : s (susceptible) la proportion de la population qui n'a pas encore contracté l'infection (et qui est donc susceptible de l'attraper), i (infectée) la poportion de la population qui est actuellement infectée, et r (rétablie) la proportion de la population qui n'est plus infectée, que ce soit suite à une guérison ou un décès (cf. ci-dessus : on ne s'intéresse pas à la différence ici). On a s + i + r = 1 puisqu'il s'agit de trois parties exclusives et exhaustives : il y a donc seulement deux variables indépendantes. Le modèle fait toutes sortes d'hypothèses simplificatrices : notamment, que la population est constante (puisque les décès comptent parmi les guéris, ce n'est pas idiot), et surtout, que les personnes ayant contracté l'infection ne peuvent pas la contracter une seconde fois (soit parce qu'elles sont immunisées soit parce qu'elles sont décédées).

Il s'agit d'écrire une équation différentielle (non-linéaire, du premier ordre) portant sur ces variables. L'idée est d'écrire le type d'équations utilisées en cinétique chimique : imaginez qu'on aurait deux réactions chimiques, la réaction d'infection S + I → I + I (une personne infectée en infecte une autre) et la réaction de rétablissement, I → R (les personnes infectées se rétablissent toutes seules avec le temps, je rappelle une fois de plus que rétablir ici compte les décès, tout ce qui m'intéresse est que ces personnes ne puissent plus en contaminer d'autres). Ce qu'on fait en cinétique chimie (de façon ultra-simplifiée…) pour modéliser des réactions de type X + Y → Z est qu'on va écrire que l'occurrence d'une telle réaction, i.e., la variation de concentration due à cette réaction (qui va compter positivement dans la concentration de Z et négativement pour X et Y) est proportionnelle à une certaine constante cinétique (positive) fois le produit des concentrations de X et de Y à des puissances appelées l'ordre de la cinétique dans chacun de ces réactifs, typiquement 1. Dans le modèle épidémiologique SIR, les deux réactions d'infection et de rétablissement seront supposées d'ordre 1. On va appeler β et γ leurs constantes cinétiques respectives : les termes de vitesse de l'infection et du rétablissement seront donc β·i·s et γ·i respectivement. Autrement dit :

Si je note x′ la dérivée dx/dt par rapport au temps (t) de la variable x, les équations du modèle SIR seront :

• s′ = −β·i·s
• i′ = β·i·s − γ·i
• r′ = γ·i

(La somme de ces trois quantités fait évidemment zéro, comme il se doit puisqu'on doit conserver s+i+r=1 : comme en chimie, rien ne se crée, rien ne se perd, mais tout se transforme.) La première équation, donc, modélise le fait que la population non encore infectée décroît par la vitesse infection dans le temps β·i·s qui est proportionnelle à une constante β fois les proportions de personnes infectées i et susceptibles de l'être s : si l'on préfère, cela signifie qu'une personne susceptible a une probabilité β·i de devenir infectée par unité de temps (très petite) ; la troisième modélise le fait que les personnes infectées deviennent rétablies avec la vitesse γ·i : si l'on préfère, cela signifie qu'une personne infectée a une probabilité γ de devenir rétablie par unité de temps (très petite) ; et l'équation du milieu, donc, assure l'équilibre s+i+r=1.

La nouvelle (et énorme !) hypothèse simplificatice qu'on a faite en écrivant ces équations, c'est de supposer que le comportement « local » de l'épidémie et de la population ne change ni avec le temps ni avec le progrès de l'épidémie : la probabilité d'infection par rencontre S+I, ou de guérison, ne changent pas : ceci exclut, par exemple, le fait que la population changerait ses habitudes avec la progression de l'épidémie (prendrait des mesures prophylactique), que le système de santé soit débordé (ce qui jouerait possiblement sur le temps de guérison), que le pathogène mute pour devenir plus ou moins virulent, et toutes sortes d'autres scénarios sortant de notre modèle extrêmement basique.

Les constantes cinétiques β et γ ont pour grandeur l'inverse d'un temps : il s'agit essentiellement de l'inverse du temps espéré d'infection si toute la population est infectée et du temps espéré de guérison. Remarquons donc qu'en changeant l'échelle de temps on multiplie β et γ par la même constante : le seul paramètre sans dimension dans le modèle est le rapport κ := β/γ, qu'on interprète comme le nombre de personnes qu'une personne infectée infectera en moyenne dans une population entièrement susceptible avant d'être elle-même rétablie. Comme il s'agit du seul paramètre sans dimension, toute discussion doit se faire sur κ. C'est ce κ = β/γ qu'on appelle nombre de reproduction et qui est souvent noté R₀, mais que je préfère noter κ ici pour éviter la confusion avec la variable r.

[Lire la suite…]

Je m'étonne de ne pas trouver d'endroit où je me serais déjà plaint à ce sujet sur ce blog. Peut-être que je sais mal chercher et qu'un petit gnome serviable va me déterrer ça, mais même si j'ai déjà ranté à ce sujet, ça ne fait pas de mal de me répéter, après tout, radoter est un de mes super-pouvoirs :

Le théorème d'incomplétude de Gödel est sans doute le théorème mathématique le plus abusé par les non-mathématiciens. Cela tient certainement au fait qu'on peut en donner des versions dangereusement approximatives et alléchamment sensationnelles comme on ne pourra jamais tout prouver à partir desquelles il est tentant de faire un pas vers la métaphysique pour tirer des conclusions encore plus fantabuleuses. Je crois avoir vu passer des tentatives d'invoquer ce théorème pour prouver :

• l'inexistence de Dieu (sur l'air de Gödel assure qu'on ne peut jamais tout savoir, or Dieu est censé être omniscient, donc Dieu n'existe pas),
• l'existence de Dieu (sur l'air de Gödel assure que la logique et le raisonnement humains ne peuvent pas arriver à toute vérité, donc la vérité est au-delà de l'humain, et c'est qu'elle est divine ; ça me fait penser à cet extrait du film Ridicule)[#],
• la supériorité de l'humain sur la machine (sur l'air de Gödel montre qu'on ne peut pas mécaniquement arriver à la vérité, mais l'intuition humaine arrive à voir que l'énoncé de Gödel est vrai, c'est donc qu'elle est supérieure à la machine),
• l'existence de la conscience (je ne sais plus les détails, mais ça devait recouper le raisonnement précédent),
• l'inexistence de la conscience,
• que la vérité est inaccessible au seul raisonnement, ou inaccessible tout court,
• que la quête d'une théorie ultime de la physique est futile,
• etc.

[#] Une ironie supplémentaire dans l'invocation du théorème d'incomplétude de Gödel pour argumenter pour l'existence de Dieu, c'est que Gödel lui-même a inventé une « preuve » de l'existence de Dieu (ou plus exactement, une formalisation en logique modale de l'argument ontologique de Saint Anselme). Cette preuve ressemble plus à une blague qu'à un argument sérieux, en fait (Gödel introduit une série d'axiomes plus hasardeux les uns que les autres, et dont on sait maintenant qu'ils sont, en fait, sinon contradictoires, au moins amenant des conclusions complètement délirantes, et il en déduit l'existence d'un truc vérifiant la définition de Dieu), et il n'est pas clair si Gödel lui-même la prenait au sérieux. Enfin, bref.

Tous ces raisonnements sont bien sûr du pur pipo. Plus généralement, toute tentative pour donner un sens philosophique (au-delà de la philosophie des mathématiques, bien sûr : métaphysique, théologique, ou même épistémologique si on s'éloigne des mathématiques) au théorème d'incomplétude de Gödel doit être considérée comme hautement suspecte.

Ce que dit le théorème précisément, je ne vais pas le rappeler ici, je l'ai expliqué notamment ici et là, avec quel succès je ne sais pas, mais en tout cas ce n'est pas mon propos ici : mon propos est que ce théorème est un énoncé technique sur la logique du premier ordre, et que toute tentative pour le faire sortir de son cadre technique est certainement une arnaque.

Même si on ne comprend pas ce que ceci signifie, peu importe : le théorème d'incomplétude affirme que

• tout système formel en logique du premier ordre
• qui soit récursivement (= calculablement) axiomatisé
• et qui contient (un fragment suffisant de) l'arithmétique

ne peut pas être à la fois consistant [← anglicisme pratique pour cohérent] et complet, i.e., s'il ne prouve jamais simultanément P et ¬P (:= la négation de P), alors il y a un P pour lequel il ne prouve aucun des deux.

Ce que je veux souligner là, c'est qu'il y a des hypothèses techniques (essentiellement trois, celles que je viens de lister), et que si on omet ces hypothèses, on est probablement en train de dire des bêtises.

Plus exactement, ce que j'ai cité est plutôt le théorème d'incomplétude de Gödel-Rosser. Le théorème d'incomplétude de Gödel, ce serait que tout système formel en logique du premier ordre qui soit récursivement axiomatisé et qui contient (un fragment suffisant de) l'arithmétique ne peut pas être à la fois ω-consistant et complet, mais l'ω-consistance est une hypothèse pénible à expliquer (autant supposer le système arithmétiquement vrai, à ce compte-là) et je ne veux pas chercher des noises à ceux qui ne feraient pas la différence entre Gödel et Gödel-Rosser. (Enfin, si on veut ergoter, le théorème d'incomplétude de Gödel, il dit : Zu jeder ω-widerspruchsfreien rekursiven Klasse ϰ von Formeln gibt es rekursive Klassenzeichen r, so daß weder v Gen r noch Neg (v Gen r) zu Flg(ϰ) gehört (wobei v die freie Variable aus r ist) — et j'avoue que j'ai beau connaître l'allemand, avoir lu l'article par le passé, et avoir une bonne idée de ce que c'est censé vouloir dire, ce n'est pas super clair pour autant pour moi. Mais je pense qu'il est raisonnable de qualifier l'énoncé ci-dessus de théorème d'incomplétude de Gödel.)

L'absence de mention de ces trois hypothèses doit être un drapeau rouge à double titre. D'abord, que le raisonnement est suspect (si on invoque un théorème sans vérifier ses hypothèses, alors que celles-ci sont indispensables, c'est sans doute que le raisonnement est incorrect — bien sûr il peut arriver qu'on ne le dise pas explicitement parce que la satisfaction de telle ou telle hypothèse est évidente et se passe de commentaire, mais dans le cas présent, j'ai du mal à imaginer que ce soit possible). Ensuite, que la personne qui tient le raisonnement ne comprend probablement pas bien le théorème qu'elle prétend appliquer si elle n'en connaît pas les hypothèses exact et le sens de celles-ci. Un autre signe à cet égard est d'ailleurs quand on parle du théorème de Gödel comme s'il n'y en avait qu'un (alors que, sans aller chercher loin, Gödel a aussi pondu un théorème de complétude qui très superficiellement et mal interprété pourrait avoir l'air de dire exactement le contraire du théorème d'incomplétude) ; ceci dit, il ne faut pas non plus accorder trop de valeur à ce signe parce que beaucoup de mathématiciens tout à fait sérieux sont susceptibles de parler du théorème de Gödel (ou d'autres auteurs : je parle régulièrement du théorème d'Euler — pour l'affirmation que a^φ(m)≡1 (mod m) si a est premier à m — alors qu'Euler a démontré des milliers de théorèmes).

[Lire la suite…]

Je me livre ici à quelques réflexions (un peu décousues, je dis toujours ça), autour de la question à quoi servent les maths pures, et les sciences fondamentales en générales ?, sur la notion d'utilité et d'applications pratiques. Pas sûr que tout ce que je dise soit très cohérent (je passe sans véritable transition du rapport entre lettres et sciences au rapport entre enseignement et recherche sans développer adéquatement ni l'un ni l'autre), mais j'espère au moins arriver à faire passer l'idée qu'il ne faut pas accepter sans broncher les préjugés les plus banals à ce sujet.

J'ai l'impression que dans l'esprit de beaucoup de gens[#], il y a une dichotomie (assez claire même si elle n'est pas forcément clairement énoncée) entre : d'un côté les sciences et techniques, dont l'importance dans la société et notamment dans l'enseignement est justifiée par leur utilité pratique, et d'autre part les arts et aux lettres et autres humanités, dont l'importance est justifiée par leur rôle culturel. Si je reformule cette idée dans des termes qui sentent bon la fin du 19e siècle et que je mets quelques majuscules d'emphase : on aurait d'un côté ce qui meut l'Humanité sur le chemin du Progrès, et de l'autre ce qui Éclaire ce chemin en montrant la voie vers le Progrès et le distinguant des Ténèbres alentours. Ou quelque chose comme ça. Ce que je veux dire, c'est que dans cette vision des choses, on a d'un côté des domaines comme la médecine ou la physique qui apportent des bienfaits à l'Homme, et de l'autre, ceux comme la philosophie et l'Histoire qui doivent en quelque sorte alimenter son sens moral.

[#] J'accepte bien volontiers que j'énonce peut-être ici un métapréjugé (i.e., un préjugé sur les préjugés que peuvent avoir les gens) : mais ce n'est pas bien grave si je dénonce une idée qui, en fait, n'existe pas vraiment.

Peut-être que je caricature un peu, mais je pense au moins que l'idée est assez répandue que la raison pour laquelle on doit enseigner l'Histoire et la géographie au lycée est que ces disciplines feraient partie de la « culture générale » que tout bon citoyen doit avoir, tandis que la raison pour laquelle on doit enseigner les mathématiques est qu'elles seraient utiles pour toutes sortes de choses.

Bref, je pourrais m'appesantir à dénoncer le stéréotype du littéraire qui considère que la culture générale se limite aux choses qu'il connaît ; qui pense qu'il est indispensable que tous les lycéens français sachent que Le Cid est une pièce de Corneille, que la cinquième république a été établie en 1958 et que les Pyrénées sont à la frontière entre la France et l'Espagne ; mais qui ne sait pas citer une loi de Newton ou de la thermodynamique, ignore si les plantes sont des eucaryotes ainsi que la différence entre une bactérie et un virus, n'a absolument aucune idée du fonctionnement d'Internet ou du Web, et ne sait peut-être même pas dire combien il y a de millimètres cubes dans un mètre cube ; et si on lui montre du doigt ces incohérences, répondra qu'il a fait des études littéraires et que ces questions techniques sont bien plus pointues et d'ailleurs ne lui servent à rien puisqu'il n'est pas scientifique ; et consentira peut-être à donner comme exemple de culture générale scientifique à peu près la seule chose qu'il sait, disons, que la Terre tourne autour du Soleil et pas le contraire. Je caricature ? En fait, non : j'en ai rencontré plus d'un, comme ça, qui se plaignaient que les jeunes ne savaient plus rien de nos jours, et qui démontraient immédiatement après une ignorance crasse et assumée dans tout domaine scientifique (j'ai le souvenir, par exemple, de quelqu'un qui ne savait pas de quoi était fait un atome, et qui avait l'air de trouver totalement fantaisiste la suggestion que cela pouvait faire partie de la culture générale de le savoir). Mais j'ai déjà parlé de ça dans cette entrée passée, et je ne veux pas la répéter ici. J'écrirai Un Jour® une entrée sur la culture générale et l'effet de perspective dont tout le monde est victime — et je m'inclus dans le tout le monde — qui fait qu'on croit toujours indispensables les savoirs qu'on a soi-même et superflus ceux que l'on n'a pas[#2]. [Mise à jour : c'est ici.] Nous avons tous des trous énormes dans notre « culture générale », et c'est normal : ce qui me dérange plus, en fait, est qu'à une époque où nous avons tous tout le savoir du monde à la portée de nos doigts, l'attitude consistant à ne pas se précipiter sur Wikipédia quand on découvre l'existence d'un de ces trous. Mais tout ça est une digression par rapport au sujet général de cette entrée, est je la referme maintenant.

[#2] Ceci vaut d'ailleurs encore au sein d'un domaine : les mathématiciens, par exemple, croient toujours que les outils et théorèmes mathématiques qu'ils connaissent et manipulent sont centraux dans les mathématiques et qu'il est indispensable de les connaître, alors que tout ce qui sort de leur domaine de prédilection est quelque chose d'arcane.

Toujours est-il que cette attitude consistant à imaginer que les sciences doivent être jugées à l'aune de leur utilité déteint au sein des sciences elles-mêmes, et que les scientifiques se retrouvent à justifier leur travail, notamment leur recherche pour ceux qui sont chercheurs, en expliquant que ça peut servir à quelque chose (et disons-le franchement, la plupart de ces justifications sont bidon, ce qui est normal parce que quand on découvre des choses nouvelles, on ne peut pas encore savoir où elles nous mèneront). Et ce n'est pas tout : la notion d'utilité est elle-même insidieusement réduite à celle d'applications.

Dans ces conditions, les sciences pures sont dans une situation très inconfortable d'apparence paradoxale : puisqu'elles sont des sciences, elles sont censées servir à quelque chose, mais puisqu'elles sont pures, elles n'ont pas d'applications ; donc à force d'accepter les différentes idées stupides que j'ai énoncées plus haut, on en revient à devoir trouver des justifications comme ah, mais on ne peut pas encore savoir si ceci aura un jour des applications. Avec comme exemple représentatif la théorie des nombres, que Gauß ou je ne sais qui considérait comme la reine des mathématiques parce qu'elle n'avait pas d'applications et qui finit par en avoir, et d'importance économique absolument capitale, à travers la cryptographie. Cet exemple est juste mais il est trompeur : je veux dire qu'au lieu d'essayer de trouver des justifications dans des exemples pareils, on ferait mieux de rejeter les prémisses idiotes que les sciences sont justifiées par leur utilité et que la seule forme d'utilité est dans les applications pratiques.

Au lieu de ça, la comparaison que j'aime donner est la suivante : imaginer qu'on puisse se passer des sciences pures pour se focaliser sur les applications est comme imaginer qu'on puisse couper les racines d'un pommier parce qu'il n'y a pas de pommes qui poussent dessus. Ce que je veux dire par là est que les sciences, et le savoir humain en général, est comme un être vivant : les différentes parties s'irriguent conceptuellement les unes les autres ; certaines produisent des applications directes, d'autres non, mais s'imaginer qu'on peut amputer des parties sans ruiner la santé de l'ensemble est tout simplement stupide.

[Lire la suite…]

Le contenu de cette entrée est presque complètement inclus dans le très classique, et remarquablement bien écrit, livre de Leonard Gillman & Meyer Jerison, Rings of Continuous Functions (1960), qui contient d'ailleurs bien d'autres choses intéressantes. Mais j'en avais assez de perdre du temps à retrouver des choses contenues dans ce livre à chaque fois que je les oublie, donc je voulais me faire un aide-mémoire, et à ce moment-là autant le mettre en ligne sur mon blog, d'autant plus qu'il s'agit là de culture générale mathématique (que, selon moi, tout mathématicien devrait avoir, — au moins pour les grandes lignes de ce que je raconte, évidemment, disons les « spoilers » ci-dessous, pas les détails un peu arcanes sur les espaces d'Urysohn et les réelcompacts). Mais mon exposition est assez différente de celle de Gillman & Jerison, et pas seulement parce que le fait de ne pas donner de preuves permet de réorganiser les résultats dans un ordre parfois plus satisfaisant, mais aussi parce que j'ai cherché à développer autant que possible les parallèles entre les faits annoncés, et j'ai une approche un tout petit peu plus « catégorique ».

Comme j'ai écrit énormément de choses très rapidement, y compris des choses qui ne sont pas verbatim dans la littérature (je ne m'en éloigne guère, mais parfois je change un peu les hypothèses ou les conventions, et il faut donc adapter les énoncés : par exemple, Gillman & Jerison supposent les espaces complètement réguliers quand il s'agit de décrire le compactifié de Stone-Čech, ce qui me déplaît énormément ; parfois aussi, quand j'interpole des résultats, je fais une démonstration dans ma tête, mais je n'ai pas tout vérifié avec le soin le plus absolu), il est probable que j'aie fait un certain nombre d'erreurs. On va dire que le but du jeu est de les retrouver !

Je suppose que le lecteur sait déjà ce qu'est un espace topologique et une fonction continue entre espaces topologiques (ainsi que les autres termes de base de la topologie générale : ouverts, fermés, voisinages, intérieur, adhérence, homéomorphisme, sous-espace / topologie induite, topologie produit, espace compact [:= compact séparé], ce genre de choses — cf. par exemple ce glossaire ou différentes pages de ce wiki). Mais je ne suppose pas que le lecteur sait ce qu'est, par exemple, un espace complètement régulier. Je suppose aussi connues les notions d'anneau [sous-entendu : commutatif], ou plutôt de ℝ-algèbre [commutative], et d'idéal d'un tel anneau (et je rappelle qu'un idéal maximal d'un anneau est un idéal ≠(1) et maximal pour l'inclusion parmi les idéaux ≠(1), ou, ce qui revient au même, un idéal tel que quand on quotiente l'anneau par lui on obtient un corps).

❀

Remarque informatique : J'utilise dans ce qui suit les caractères ‘𝔪’, ‘𝔬’, ‘𝔭’, ‘ℱ’ et ‘𝒰’ pour, respectivement, un ‘m’ gothique minuscule, un ‘o’ gothique minuscule, un ‘p’ gothique minuscule, un ‘F’ cursif et un ‘U’ cursif. Comme ces caractères peuvent parfois manquer dans des polices j'ai prévu un peu de magie en JavaScript qui remplacera en un seul clic tous ces symboles par des lettres latines toutes bêtes : donc, si vous ne voyez pas les caractères que je viens de nommer, cliquez ici pour activer ce remplacement.

❀

✱ Si X est un espace topologique, on note C(X) l'ensemble des fonctions réelles continues X→ℝ, avec l'addition et la multiplication point à point (c'est-à-dire que f+g est la fonction x↦f(x)+g(x) et que f⁢g est la fonction x↦f(x)⁢g(x)) ; chaque réel c est identifié à la fonction constante x↦c dans C(X). (C'est donc un anneau commutatif et même une ℝ-algèbre commutative. On peut le munir d'autres structures, notamment un ordre partiel défini par f≤g lorsque f(x)≤g(x) pour tout x∈X, qui est d'ailleurs un treillis avec f∨g la fonction x ↦ f(x)∨g(x) := max(f(x),g(x)) et f∧g la fonction x ↦ f(x)∧g(x) := min(f(x),g(x)), et une valeur absolue |f| = f∨(−f). On peut éventuellement aussi introduire une ou plusieurs topologies sur C(X), mais ce n'est pas ce qui va m'intéresser ici ; en revanche, je souligne qu'on n'a pas de norme intéressante sur C(X).)

À côté de C(X), on a C*(X) qui est formé des fonctions réelles continues bornées c'est-à-dire les f∈C(X) telles qu'il existe un B∈ℝ tel que pour tout x∈X on ait |f(x)|≤B. Il est évident que la somme et le produit de deux fonctions bornées sont bornés, si bien que C*(X) est un sous-anneau de C(X).

On peut par ailleurs noter que C et C* sont des foncteurs contravariants des espaces topologiques vers les ℝ-algèbres commutatives, ce qui signifie que donnée une application continue h:X→Y on fabrique de façon évidente des morphismes C(Y)→C(X) et C*(Y)→C*(X) (remarquer le sens des flèches !), simplement par composition à droite par h, c'est-à-dire qu'elles envoient une fonction continue f:Y→ℝ [éventuellement bornée] sur la composée f∘h:X→ℝ. On peut noter C(h):C(Y)→C(X) et C*(h):C*(Y)→C*(X) pour ces deux morphismes de « composition à droite par h ». La « fonctorialité » signifie simplement que (i) si id:X→X est l'identité alors C(id) et C*(id) sont aussi l'identité, et (ii) si h:X→Y et k:Y→Z alors C(k∘h)=C(h)∘C(k) et C*(k∘h)=C*(h)∘C*(k).

✱ La problématique qui m'intéresse est de décrire le rapport entre l'espace X et son C(X) et son C*(X), comment on peut retrouver l'un à partir de l'autre, ce genre de choses.

Plus précisément, parmi les questions qu'il est naturel de se poser :

• La ℝ-algèbre C(X) caractérise-t-elle l'espace topologique X ? Permet-elle de le retrouver (autrement dit, si X₁ et X₂ ont « le même » C(X), c'est-à-dire que C(X₁) et C(X₂) sont isomorphes en tant que, disons, ℝ-algèbres, alors X₁ et X₂ sont-ils homéomorphes) ? Dans les cas où c'est possible, comment peut-on reconstruire X à partir de C(X) ? Par ailleurs, peut-on identifier les ℝ-algèbres qui apparaissent comme des C(X) ? Peut-on, d'ailleurs, retrouver la structure de ℝ-algèbre (i.e., les fonctions constantes et leur isomorphisme avec ℝ) à partir de celle d'anneau ?
• Mêmes questions pour C*(X).
• Quel est le rapport entre C(X) et C*(X) ? Peut-on identifier les fonctions bornées de façon purement algébrique ? Pour quel genre d'espace a-t-on C(X) = C*(X) (toutes les fonctions continues sont bornées) ? Comment les ℝ-algèbres qui apparaissent comme des C(X) se situent-elles parmi ceux qui apparaissent comme des C*(X) ? Peut-on notamment trouver un espace Xˆ (en fonction de X) pour lequel on aurait C(Xˆ) = C*(X) (ou le contraire) ?

(Digression : J'ai essayé d'écrire là les questions qu'il me semble qu'on « devrait » vraiment spontanément se poser — et donc chercher à résoudre — dès qu'on introduit ce genre de constructions, sans préjuger de celles qui ont une réponse plus ou moins intéressante. Je trouve toujours agaçants les livres qui traitent d'un sujet mathématique et qui omettent une question qui me semble « évidemment naturelle », ne serait-ce que pour dire qu'on ne connaît pas de réponse satisfaisante ou que les auteurs n'en connaissent pas.)

Quelques spoilers :

• La ℝ-algèbre C*(X) caractérise l'espace X pour les espaces compacts [séparés]. On pourra alors reconstruire X comme l'ensemble des idéaux maximaux de C*(X). Je crois qu'on ne sait pas caractériser de façon algébrique satisfaisante les ℝ-algèbres C*(X). En revanche, donné un espace topologique X, il y a un unique espace compact βX pour lequel C*(βX) = C*(X) (c'est donc un choix canonique d'espace X′ ayant ce C*(X)) : on l'appelle le « compactifié de Stone-Čech » de X. En général, dire que C*(X₁) et C*(X₂) sont isomorphes va signifier que les espaces ont le même compactifié de Stone-Čech.
• La ℝ-algèbre C(X) caractérise l'espace X pour tous les espaces dits « réelscompacts » (ce qui inclut énormément de choses, par exemple tous les espaces métriques). On pourra alors reconstruire X comme l'ensemble des idéaux maximaux de C(X) tel que le quotient soit ℝ. Je crois qu'on ne sait pas caractériser de façon algébrique satisfaisante les ℝ-algèbres C(X). En revanche, donné un espace topologique X, il y a un unique espace réelcompact υX pour lequel C(υX) = C(X) (c'est donc un choix canonique d'espace X′ ayant ce C(X)) : on l'appelle le « réelcompactifié [de Hewitt-Nachbin] » de X. En général, dire que C(X₁) et C(X₂) sont isomorphes va signifier que les espaces ont le même réelcompactifié.
• Les C*(X) sont des cas particuliers des C(X), par cela je veux dire que pour tout espace topologique X il existe un espace Xˆ pour lequel on a C(Xˆ) = C*(X), et (d'après ce qui précède) ceci caractérise complètement Xˆ si on lui impose de plus d'être compact : c'est là aussi le compactifié de Stone-Čech de X (noté βX). On peut caractériser algébriquement les fonctions bornées au sein de C(X) puisqu'on peut même caractériser l'image de f∈C(X), à savoir l'ensemble des c∈ℝ tels que f−c ne soit pas inversible dans C(X). Les espaces pour lesquels C(X) = C*(X), ou simplement pour lesquels C(X) est un C*(X′), sont les espaces dits « weierstrassiens » ou « pseudocompacts » (et c'est notamment le cas des espaces compacts).

[Lire la suite…]

Cela fait un certain temps que je me dis que je devrais écrire une ou plusieurs entrées sur ce blog sur des sujets tournant autour de la logique intuitionniste et des mathématiques constructives. La présente entrée est une sorte de TODO étendu où je mélange, de façon malheureusement confuse et désorganisée, des remarques introductives voire vulgarisatrices sur le sujet (et expliquant de quoi il est question), des remarques d'ordre méta (où je dis que je devrais parler de ceci ou de cela, ou bien me demande comment je pourrais le faire, ou encore me dis que je ne comprends pas bien telle ou telle chose) et des explications de fond assez disparates (et faites à des niveaux de prérequis, il faut bien le dire, complètement incohérents). Même l'ordre dans lequel je dis les choses est assez bizarre (à la limite, je me demande s'il ne vaut pas mieux lire cette entrée en commençant par la fin). Je pense que ça vaut quand même la peine de publier tout ça, en conseillant au lecteur de simplement sauter les passages qui lui semblent obscurs (puisque de toute façon il y a très peu de dépendances dans ce que je vais raconter).

★

En fait, au départ, je me suis surtout dit que ce serait intéressant d'écrire quelque chose sur le topos effectif et la réalisabilité de Kleene. Je peux au moins recopier l'introduction informelle que j'ai commencé à rédiger à ce sujet :

Pour dire très très très sommairement et très très très vaguement de quoi il est question,

• un topos est une sorte de « monde mathématique alternatif » régi par les lois de la logique intuitionniste (une logique plus faible que la logique usuelle, ou classique, dans laquelle on a essentiellement supprimé la loi du tiers exclu qui affirme que toute formule logique est soit vraie soit fausse, ou, de façon équivalente, que tout ce qui n'est pas faux est vrai) ; de façon un peu plus précise, un topos est une catégorie (peu importe ce qu'est exactement une « catégorie ») qui possède un certain nombre de propriétés communes avec la catégorie des ensembles, ce qui permet d'y mener un certain nombre de constructions mathématiques usuelles, mais dont le comportement va néanmoins être différent sur un certain nombre de choses, et notamment la logique ; et
• le topos effectif est un topos particulier qui présente un intérêt particulier en calculabilité : il présente un monde alternatif dans lequel toutes les fonctions ℕ→ℕ sont calculables, ce qui nous offre un regard neuf sur la calculabilité par rapport à sa présentation classique, où la logique intuitionniste éclaire ce que sont les raisonnements effectifs (voir à ce sujet cet article introductif d'Andrej Bauer, qui ne parle pas du topos effectif mais explique en quoi travailler en logique intuitionniste peut rendre plus facile ou plus naturelle la calculabilité).

Mais reculons d'un cran : pour parler du topos effectif, je me suis dit qu'il fallait d'abord que j'écrive quelque chose sur la réalisabilité de Kleene, qui en est en quelque sorte le prélude. (Si vous voulez savoir très très très sommairement et très très très vaguement de quoi il est question, S. C. Kleene a introduit dès 1945 une notion appelée « réalisabilité », en tentant de donner un sens précis à l'intuitionnisme, et — en très très très gros — le fait qu'une formule arithmétique φ soit « réalisable » [par un entier naturel n] signifie que n en apporte une sorte de « témoignage algorithmique », par exemple, si φ est une formule du type ∀x.ψ(x) affirmant que ψ(x) est vraie pour tout x, alors « réaliser » cette formule va se faire en apportant un programme qui prend en entrée un entier k et en sortie calcule un entier qui réalise ψ(k) ; pour un peu plus de détails, voir le début de cette question que j'ai posée sur MathOverflow, ou pour encore plus, voir le texte Realizability: An [sic] Historical Essay de Jaap van Oosten.) Le lien entre la réalisabilité de Kleene et le topos effectif est très fort : disons que le topos effectif est défini en cherchant une généralisation assez directe de la réalisabilité à des formules plus complexes que celles de l'arithmétique (et les formules arithmétiques qui sont réalisables sont exactement celles qui sont vraies dans le topos effectif).

Ajout : voir cette entrée ultérieure au sujet de la réalisabilité de Kleene, où je la définis proprement ; en voici depuis un sur la réalisabilité propositionnelle. Nouvel ajout : le billet sur le topos effectif est ici.

Bon, mais je me suis alors rendu compte que ce serait commencer in media res de parler du topos effectif ou même de réalisabilité si je ne commençais pas par parler d'intuitionnisme ou de mathématiques constructives. Et là, je suis embêté par le fait que j'ai à la fois trop de choses à dire et pas assez (trop, parce que ça touche à énormément de sujets ; pas assez, parce qu'en ce faisant ça touche aussi à trop de questions sur lesquelles je ne sais pas grand-chose).

Ajout : ce nouveau billet est une tentative de réécriture complète de celui qui suit, et il est peut-être plus clair (ou peut-être que les deux s'éclairent l'un l'autre, je ne sais pas).

★

La logique intuitionniste est une logique plus faible que la logique classique dans laquelle on s'interdit la loi du tiers exclu (qui dit que tout énoncé P est soit vrai soit faux ; c'est-à-dire : P∨¬P) ; cela revient essentiellement à s'interdire le raisonnement par l'absurde (ou plus exactement, le raisonnement par l'absurde de la forme je veux montrer P : supposons par l'absurde que P soit faux <…>, j'arrive à une contradiction, donc P ne peut pas être faux, c'est-à-dire qu'il est vrai — c'est la dernière partie qui coince en logique intuitionniste ; en revanche, on peut toujours dire je veux montrer que P est faux : supposons par l'absurde que P soit vrai <…>, j'arrive à une contradiction, c'est-à-dire que P est faux, parce que P est faux signifie précisément que la vérité de P est absurde). Faire des maths sans le tiers exclu peut ressembler à un exercice aussi futile qu'essayer de boxer avec les deux mains attachées derrière le dos, et dans une certaine mesure ça y ressemble effectivement, mais cela présente néanmoins un certain intérêt : non seulement c'est intéressant du point de vue de la pure logique de se demander ce qu'on peut faire sans cet axiome (et cette question a des connexions inattendue avec toutes sortes d'autres parties des mathématiques) ; mais par ailleurs, une démonstration en logique intuitionniste apporte véritablement plus de contenu qu'une démonstration classique : pour commencer, elle est valable de façon plus large (et notamment dans les topoï [pluriel de topos]), mais aussi, elle est constructive (au moins si on part de certains axiomes), c'est-à-dire qu'elle exhibe les objets dont elle affirme l'existence.

Une des idées centrales des maths constructives (qui sont à peu près, quoique pas forcément exactement, la même chose que les mathématiques exercées dans le cadre de la logique intuitionniste) est que si on veut prouver P ou Q (en symboles, P∨Q), il devrait être suffisant mais aussi nécessaire de prouver soit P, soit Q (et notamment, de savoir lequel des deux est vrai !) : ceci va manifestement complètement à l'encontre du tiers exclu qui postule que pour tout énoncé P, soit P est vrai soit ¬P l'est, sans qu'on puisse forcément trancher lequel (et parfois, effectivement, on ne peut prouver ni l'un ni l'autre). De même, si on veut prouver il existe un x tel que P(x) (en symboles, ∃x.P(x)), il devrait être suffisant mais aussi nécessaire d'exhiber un x pour lequel on peut prouver P(x) : de nouveau, ceci va à l'encontre des raisonnements par l'absurde qui ressemblent à supposons qu'aucun tel x n'existe <…>, j'arrive à une contradiction, donc un tel x doit exister (mais au final ne donnent aucune information pour en construire un).

Ajout (2019-04-15T23:37+02:00) : Juste après avoir publié cette entrée je me rends compte que j'ai oublié d'insérer un paragraphe que je comptais écrire sur l'interprétation de Brouwer-Heyting-Kolmogorov qui tente d'expliquer au moins informellement le sens des connecteurs de la logique intuitionniste. Spécifiquement, il s'agit de variations autour des explications suivantes :

• une preuve de P∧Q (conjonction) est un couple formé d'une preuve de P et d'une de Q,
• une preuve de P∨Q (disjonction) est la donnée d'une preuve de P ou d'une preuve de Q (avec, bien sûr, l'information de laquelle des deux),
• une preuve de P⇒Q (implication) est une manière de transformer une preuve de P en une preuve de Q,
• une preuve de ⊤ (le vrai) est triviale,
• une preuve de ⊥ (le faux) n'existe pas,
• une preuve de ∀x.P(x) est une manière de transformer un x en une preuve de P(x),
• une preuve de ∃x.P(x) est la donnée d'un t particulier et d'une preuve de P(t).

[Lire la suite…]

Méta : J'ai écrit un fil un peu long sur Twitter pour tenter d'expliquer le théorème de Gödel, qui reprend grosso modo des idées de cette entrée passée (au moins la partie sur Gödel de celle-ci) mais en mettant l'accent un peu différemment et donnant plus de détails sur les conditions de prouvabilité. Comme ça peut être un complément intéressant et que tout le monde n'aime pas le format Twitter, je reproduis ici ce que j'y ai dit, en reformatant un minimum (en revanche, mon style sur Twitter est sans doute un peu différent de mon style sur ce blog, et je n'ai pas le courage de reformuler plus qu'a minima) :

Je fais d'abord une tentative pour lever la confusion au sujet formalisme. Quand on formalise les [raisonnements] mathématiques, on les décrit sous forme de manipulations de suites de symboles (« syntaxe ») qui obéissent à des règles bien précises. Il est évident que si on demande que les règles de raisonnement elles-mêmes soient formalisées en mathématiques, on a une régression infinie : si quelqu'un prétend ne comprendre que ce qui est formel, c'est turtles all the way down, on ne peut rien démarrer… Pour que le bootstrap soit possible, il faut bien accepter l'idée de décrire les règles de manipulation de la logique en français, ou en faisant appel à des notions mathématiques elles-mêmes pas formalisées (mais néanmoins précises) ! (Refuser cette idée ce serait comme refuser qu'on puisse jouer aux échecs sous prétexte que les règles des échecs n'ont pas été formalisées dans ZFC. Or personne ne pense qu'on a besoin de ZFC pour jouer aux échecs !)

En revanche, ce qu'on peut faire, c'est une fois qu'on a accepté ces règles et construit un système formel avec, utiliser ce système formel pour revisiter (« refléter ») les règles, cette fois-ci formellement : autrement dit, on reconstruit tout le système qu'on a déjà construit, mais on le fait cette fois-ci à l'intérieur du système « externe » qui a été construit informellement. Il y a une mise en abyme. Je parlerai de système interne pour celui qu'on construit ainsi.

Typiquement, ça se fait avec un truc appelé codage de Gödel : si le système externe contient l'arithmétique, on dit qu'on peut refléter toutes les règles formelles comme des manipulations arithmétiques pour fabriquer le système informel. Le code de Gödel d'une formule, c'est l'entier qui représente cette formule (et qui devient, du coup, manipulable par le système externe). Du coup les énoncés comme P est prouvable (qui sont, à la base, informels, parlant du système externe) deviennent des énoncés formels du système externe et qui parlent du système interne. Des énoncés arithmétiques. (Je noterai □P plus bas pour P est prouvable.)

Et là, il y a une sorte de postulat épistémologique, qui est que ce que :

Les règles du système interne (formalisées dans le système externe) reflètent correctement les règles du système externe lui-même.

Donc si on croit que le système externe ne dit pas de conneries, et s'il dit que le système interne ne peut pas prouver <ceci-cela>, alors effectivement le système externe ne peut pas prouver <ceci-cela>. (Un ultra-formaliste pourrait rejeter ce postulat et dire : pour moi, les maths formelles sont juste un jeu typographique dénué de sens, le système externe ce sont les règles du jeu, le prétendu système interne n'a pas de sens, pas plus qu'aucun énoncé du jeu. Mais en vrai, les gens font des maths parce qu'ils croient qu'une preuve du fait que 2+2=4 apporte quelque information sur le monde réel, donc il y a bien une connexion entre le système externe, qui vit dans le monde réel, et le système interne, formalisé.)

Accessoirement, les systèmes externe et interne n'ont pas vraiment besoin d'être les mêmes : en fait on a besoin de très peu d'axiomes pour faire fonctionner Gödel. Mais je ne sais pas si ça aide de dire ça. Donc restons dans l'idée que ce sont « les mêmes ».

Maintenant, de quels ingrédients a-t-on besoin pour prouver Gödel ? On a besoin des trois « conditions de prouvabilité de Hilbert-Bernays » (que je noterai (A), (B), (C)), et de l'astuce de Quine. Expliquons ça successivement :

Les conditions de prouvabilité de Hilbert-Bernays remplacent le postulat épistémologique dont j'ai parlé plus haut par quelque chose de précis et de formel. En gros, elles font le lien entre les niveaux externe et interne (et interne², cf. plus bas).

Première chose : (A) si le système externe prouve un énoncé P, alors il prouve que le système interne prouve P [ou plutôt, le code de Gödel de P]. Pourquoi ? Parce que si on a une preuve de P, on peut « refléter » cette preuve : la réécrire comme une preuve formelle dans le système interne, et ceci fournit une preuve de son existence dans le système externe. Bien sûr, tout ce que je viens de dire est informel, puisque (A) est par essence informel ! Mais si on applique ça à un P bien précis et une preuve de P formelle explicite, la recette que je viens de dire donne une preuve tout à fait explicite et formelle (dans le système formel externe) de l'existence d'une preuve dans le système interne. Donc, si on veut, (A) est un métathéorème informel : en soi il n'est pas formel, mais il s'instancie en des théorèmes formels (du système externe) dont on a la recette de construction.

Maintenant on peut refaire tout ça avec un niveau de plus (on a alors trois systèmes : l'externe est informel, l'interne est formalisé dans le système externe, et l'interne² dans le système interne — ça s'arrêtera là) : Tout ce que j'ai dit sur le (A) vaut de nouveau et donne, cette fois, une preuve formelle (dans le système externe) du fait (B) suivant : si le système interne prouve P alors il prouve que le système interne² prouve P. Cette fois c'est un vrai théorème du système externe, pas juste un métathéorème informel.

Enfin, (C) dit que si le système interne prouve [le code de Gödel] de P⇒Q et [celui de] P, alors il prouve [celui de] Q. Ça c'est juste le fait qu'on a la règle de modus ponens dans le système interne (c'est presque une définition).

Bref, si je note □P l'énoncé (du système externe) qui dit qu'il existe une preuve de P dans le système interne, mes conditions de prouvabilité sont :

• (A) si P est un théorème alors □P en est un,
• (B) □P⇒□□P est un théorème,
• (C) □(P⇒Q)⇒□P⇒□Q est un théorème

(tous ces théorèmes dans le système externe ! et ce, quels que soient les énoncés P et Q).

Maintenant, l'astuce de Quine (en fait, le procédé diagonal), c'est quelque chose qui permet de fabriquer un énoncé G tel que G⇔¬□G (démontrablement dans le système externe !), autrement dit un énoncé qui dit je ne suis pas un théorème.

L'astuce fonctionne exactement comme la manière dont on écrit des programmes qui écrivent leur propre code, chose que j'explique en détails dans cette page web consacrée aux quines. On fabrique une formule R(x) (du système externe) qui dit si x est une formule du système interne ayant une variable libre, et qu'on remplace cette variable par le code de Gödel de x elle-même, alors le résultat n'est pas un théorème (du système interne), ou de façon encore plus informelle, R(x) signifie x(‘x’) n'est pas un théorème (soit ¬□x(‘x’)) en notant ‘x’ le code de Gödel de x. Mais du coup, R(‘R’) équivaut à R(‘R’) n'est pas un théorème (soit ¬□R(‘R’)), et c'est ça que je note G.

[Ajout par rapport au fil Twitter:] Dans la présentation informelle proposée par Hofstadter, G est en gros la phrase suivante : Si on prend le morceau de phrase suivant et qu'on le fait suivre (après deux points) de lui-même entre guillemets, on obtient quelque chose qui n'est pas un théorème : Si on prend le morceau de phrase suivant et qu'on le fait suivre (après deux points) de lui-même entre guillemets, on obtient quelque chose qui n'est pas un théorème — l'astuce est de dire cet énoncé n'est pas un théorème sans passer par une référence à cet énoncé que notre système formel ne permet pas de faire ; ceci est exactement parallèle au mécanisme des quines qui permettent de coder imprimer ce programme dans un langage qui ne permet pas une référence à ce programme.

Une fois qu'on a ces ingrédients, la preuve de Gödel est pure manipulation formelle. Tout le raisonnement est tenu dans le système externe (mais parle du système interne — voire interne² quand il y a des □□) :

Supposons □G. Alors □□G d'après (B). Mais la preuve (explicite !) de G⇒¬□G donne □(G⇒¬□G) d'après (A). Or □G et □(G⇒¬□G) donnent □¬□G par (C). Or □□G et □¬□G (i.e. □(□G⇒⊥)) donnent □⊥ d'après (C). Bref, on a prouvé □G⇒□⊥ soit ¬□⊥⇒¬□G. C'est-à-dire (qu'on a prouvé dans le système externe) que si le système interne prouve G alors il prouve ⊥ (c'est-à-dire 0=1). I.e., si le système interne est consistant (¬□⊥), il ne peut pas prouver G (soit : ¬□G)… …donc G, qui équivaut à ¬□G, est vrai ! (c'est-à-dire, est un théorème du système externe, prouvé sous l'hypothèse (¬□⊥) que le système interne est consistant. C'est le premier théorème d'incomplétude.

Maintenant, en appliquant (A) à cette preuve (explicite !) de ¬□⊥⇒¬□G, on obtient □(¬□⊥⇒¬□G) donc □¬□⊥⇒□¬□G (par (C)). Comme ¬□G⇒G donne □(¬□G⇒G) par (A) donc □¬□G⇒□G par (C), les implications □¬□⊥⇒□¬□G, □¬□G⇒□G et □G⇒□⊥ mises bout à bout donnent finalement □¬□⊥⇒□⊥, ou encore ¬□⊥⇒¬□¬□⊥. C'est le second théorème d'incomplétude : si le système (interne) est consistant (¬□⊥) alors il ne prouve pas la consistance du système interne² (¬□¬□⊥). Et comme en fait tous ces systèmes sont le même, le postulat épistémologique évoqué ci-dessus permet de lire ce théorème formel ¬□⊥⇒¬□¬□⊥ sous la forme si Peano est consistant, il ne prouve pas sa propre consistance (idem pour ZFC).

Évidemment, l'ultra-formaliste dont j'ai parlé plus haut objectera et dira que j'ai juste prouvé un énoncé cabalistique ¬□⊥⇒¬□¬□⊥ sans aucun sens dans le monde réel et qui ne dit rien sur mon système externe (lequel vit dans le monde réel). Mais si on croit que les « vrais » entiers naturels ont un sens et que Peano en dit des choses vraies, on est forcé de conclure que Peano est incomplet et ne sait pas prouver certaines choses vraies (essentiellement, il ne sait pas qu'il dit lui-même la vérité).

(Je n'ai pas de poisson d'avril à proposer cette année, mais je vous donne deux entrées pour le prix d'une.)

Même s'il a déjà été signalé hier en commentaire à cette vieille entrée, je ne peux pas ne pas écrire une petite entrée sur ce magnifique problème qui continue à narguer mon intuition — il s'agit d'un de ces cas où les mathématiques font quelque chose qui devrait être très sérieusement impossible, et j'ai beau arriver à prouver (et à comprendre la preuve intellectuellement) que c'est possible, je reste incapable de me faire intuitivement à l'idée que ça l'est. (Je sais, je sais : In mathematics you don't understand things. You just get used to them.)

Le problème est très simple (mais je l'écris de façon un peu longue pour qu'il n'y ait aucune ambiguïté sur les règles du jeu) :

Le cruel Docteur No a capturé deux mathématiciens, que nous appellerons Alice et Bob. Après avoir permis à ceux-ci de se concerter sur leur stratégie, il va les soumettre à son épreuve dont il leur communique les termes : chacun des deux pourra observer une suite binaire infinie aléatoire uniformément distribuée (c'est-à-dire une suite de 0 et 1 dont chaque terme vaut 0 ou 1 avec probabilité ½, indépendamment les uns des autres ; on peut imaginer une suite de résultats de tirages de pile ou face), les deux suites (celle qu'Alice observe et celle que Bob observe) étant indépendantes. Pour fixer les idées, mettons que les termes de chaque suite sont numérotés par les entiers naturels (0, 1, 2, 3, etc.) : appelons (A_n) la suite observée par Alice et (B_n) la suite observée par Bob. Alice et Bob ne peuvent pas communiquer entre eux (une fois finie la concertation initiale sur leur stratégie commune, mais celle-ci est antérieure à l'observation des suites). Alice, après avoir observé sa suite choisit un entier naturel a qui sera le numéro d'un terme dans la suite de Bob ; de même, Bob, après avoir observé sa suite, choisit un entier naturel b qui sera le numéro d'un terme dans la suite d'Alice. Alice et Bob gagnent (un gentil petit cadeau de la part du Docteur No) si chacun a choisi un terme valant 1 dans la suite de l'autre, c'est-à-dire, si la valeur A_b du terme de la suite d'Alice numéroté par l'entier b choisi par Bob et la valeur B_a du terme de la suite de Bob numéroté par l'entier a choisi par Alice valent tous les deux 1.

Quelle stratégie Alice et Bob peuvent-ils employer pour maximiser leur chance de gain ?

(Formellement : une stratégie d'Alice est une fonction borélienne α:{0,1}^ℕ→ℕ et une stratégie de Bob est une fonction borélienne β:{0,1}^ℕ→ℕ. La probabilité de succès est la mesure de l'ensemble des couples (A,B) ∈ {0,1}^ℕ × {0,1}^ℕ tels que A(β(B)) = B(α(A)) = 1, pour la mesure de probabilité uniforme sur {0,1}^ℕ × {0,1}^ℕ (les valeurs α(A) et β(B) sont les entiers noté a et b). Et on demande de maximiser cette probabilité.)

Remarque : Si on est gêné par les suites infinies (et c'est vrai que c'est agaçant de parler de l'observation d'une suite infinie), on peut ramener le problème à niveau fini : soit N un entier, Alice verra le résultat de N tirages de pile ou face uniformes et indépendant, Bob verra le résultat de N autres tels tirages (indépendants entre eux et indépendants de ceux d'Alice), et chacun devra choisir un entier entre 0 inclus et N exclu faisant référence à un tirage de l'autre, les deux gagnant s'ils ont choisi un tirage valant 1 chez l'autre. La situation paradoxale décrite ci-dessous est la même pour N fini que pour des suites infinies, c'est juste que les nombres sont moins ronds. (Formellement, dans le cas fini, une stratégie d'Alice est une fonction α:{0,1}^N→{0,…,N−1} et une stratégie de Bob est une fonction β:{0,1}^N→{0,…,N−1}. La probabilité de succès est la mesure de l'ensemble des couples (A,B) ∈ {0,1}^N × {0,1}^N tels que A(β(B)) = B(α(A)) = 1, pour la mesure de probabilité uniforme sur {0,1}^N × {0,1}^N.)

Une stratégie évidente consiste à ce qu'Alice et Bob choisissent tous les deux l'entier 0 (faisant référence au premier terme de la suite de l'autre). Dans ce cas, ils gagnent avec probabilité ¼, puisque chacun de A₀ et de B₀ vaut 1 avec probabilité ½, indépendamment l'un de l'autre. Choisir d'autres entiers constants (par exemple si Alice choisit 42 et Bob choisit 1729) donne toujours exactement la même chose.

L'idée intuitive qu'on a spontanément (en tout cas que j'ai eue, et dont je n'arrive toujours pas vraiment à me défaire) est qu'on ne peut pas faire mieux que ¼ :

Raisonnement incorrect : Alice et Bob ne peuvent pas communiquer, n'ont aucune information sur la suite de l'autre, et leurs deux suites sont indépendantes, donc il est impossible que l'observation de sa propre suite puisse aider Alice à faire quoi que ce soit d'utile sur la suite de Bob. Donc il n'y a rien de mieux à faire que de choisir des a et b constants (dont la valeur n'a pas d'importance).

Raisonnement incorrect (variante) : Quelle que soit la manière dont Alice choisit a, la valeur B_a vaudra 0 avec probabilité ½ et 1 avec probabilité ½ (puisque le choix de a ne peut dépendre que de A, qui est indépendant de B), et de même A_b vaudra 0 avec probabilité ½ et 1 avec probabilité ½. Puisque les suites A et B sont indépendantes et que (du coup) les variables a et b le sont, on a A_b = B_a = 1 avec probabilité ¼, et on ne peut pas faire mieux.

Et pourtant, c'est faux.

Et ce n'est même pas très compliqué de faire mieux que 1/4. Voici une stratégie simple qui donne une probabilité 1/3 de succès à Alice et Bob : Alice choisit pour a l'indice du premier 1 dans sa propre suite, et Bob choisit de même pour b l'indice du premier 1 dans la sienne. La probabilité d'avoir a=b est la somme de 1/4 (probabilité d'avoir a=b=0) plus 1/4² (probabilité d'avoir a=b=1) plus 1/4³ (probabilité d'avoir a=b=2), etc., c'est-à-dire la somme des 1/4^k, qui vaut 1/3 ; et lorsque c'est le cas, par construction, A_b = B_a = 1 ; par ailleurs, si a≠b, alors Alice et Bob perdent (par exemple, si a<b, on a B_a = 0 puisque b est l'indice du premier 1 dans la suite B). Donc la probabilité de succès de cette stratégie est exactement 1/3.

J'ai beau avoir écrit cette preuve. Je n'arrive vraiment pas à me faire une idée intuitive de comment il est possible que cette stratégie fonctionne.

Mais je peux quand même dire ceci : la raison pour laquelle les raisonnements ci-dessus (tendant à « prouver » l'impossibilité) sont incorrects, c'est que s'il est bien vrai que chacun de A_b et B_a vaut 0 ou 1 avec probabilité ½, ils ne sont pas indépendants (puisque a dépend de A et b de B), et plus exactement, Alice et Bob peuvent s'arranger (et c'est ce qu'ils font dans la stratégie ci-dessus) pour que les deux événements A_b = 1 et B_a = 1 soient corrélés. Autrement dit, si on ne peut pas améliorer la chance d'avoir A_b = 1, on peut au moins s'arranger pour que, lorsque c'est le cas, ceci apporte des informations sur a ou sur B qui font que B_a = 1 a plus de chances de se produire. Je continue à trouver ça peu clair intuitivement, mais c'est déjà ça.

Maintenant, ce qui est amusant (et presque un peu décevant ?), c'est que cette jolie stratégie donnant 1/3 n'est toujours pas optimale : comme il est expliqué sur le fil MathOverflow lié au début de cette entrée (dans la réponse de mihaild), on peut faire 7/20 (c'est-à-dire 35%). Mais on ne sait pas si c'est optimum, et on n'a pas (au moment où j'écris, d'après de fil de discussion) de borne supérieure autre que le ½ évident.

Référence croisée : ce fil Twitter.

Mise à jour (2019-04-04) : La borne supérieure a été améliorée à 3/8 dans le fil MathOverflow avec un argument très simple (quand j'aurai le temps, j'essaierai de mettre à jour ce paragraphe pour le donner). Par ailleurs, il apparaît que problème était déjà discuté (de façon un peu généralisée) dans ce papier, qui prouve une borne supérieure de 3/8, et annonce mais sans preuve une borne supérieure de 81/224.

Complément (2019-04-07) : Pour la complétude de cette entrée, je reproduis en la paraphrasant la preuve de la borne supérieure par 3/8 de la probabilité de succès. Si on note a l'entier choisi par Alice et a′ l'entier qu'elle choisirait avec la même stratégie si elle observait la suite (1−A_n) au lieu de (A_n) (i.e., si on échange les 0 et 1 dans ce qu'Alice observe), et de même b et b′ pour Bob, alors on peut remarquer que l'espérance E(A_b B_a) de A_b B_a (qui est la probabilité de succès p qu'on cherche à maximiser) est aussi égale à l'espérance de (1−A_b′) B_a (puisque 1−A est une variable distribuée comme A et toujours indépendante de B) ou de A_b (1−B_a′) ou encore de (1−A_b′) (1−B_a′). La somme de ces quatre espérances (qui est 4p) est donc l'espérance de (A_b+1−A_b′) (B_a+1−B_a′), soit 4p ≤ E((A_b+1−A_b′) (B_a+1−B_a′)) = 1 + E(A_b−A_b′) + E(B_a−B_a′) + E((A_b−A_b′) (B_a−B_a′)) soit encore 1 + E((A_b−A_b′) (B_a−B_a′)) puisque E(A_b) = E(A_b′) et E(B_a) = E(B_a′) (en fait, chacune de ces quatre espérances vaut ½). Enfin, comme A_b−A_b′ vaut +1 ou −1, l'espérance E((A_b−A_b′) (B_a−B_a′)) est majorée par E(|B_a−B_a′|), elle-même majorée par ½ (si i≠j alors E(|B_i−B_j|)=½). Au final, on a prouvé 4p≤1+½, soit p≤3/8 comme annoncé.

Je traîne depuis longtemps l'idée de vulgariser quelques notions de logique linéaire. Du point de vue de la vulgarisation, la logique linéaire a ceci de sympathique que c'est quelque chose mathématiquement à tellement « bas niveau » que je n'ai besoin de présupposer aucune sorte de connaissance mathématique préalable pour en parler : en principe, on peut la considérer comme un pur petit jeu syntactique dont les règles ne sont pas très compliquées — même si, présenté sous cette forme, il risque de ne pas apparaître comme très intéressant, et même s'il est bon d'avoir du recul pour avoir une idée de quelles règles appliquer à quel moment, la compréhension des règles elles-mêmes ne nécessite pas de savoir particulier. Du point de vue personnel, la logique linéaire est quelque chose qui me frustre beaucoup parce que, d'un côté, je la trouve extrêmement élégante et joliment symétrique, de l'autre, à chaque fois qu'elle semble avoir une application ou une interprétation quelque part, on se rend compte qu'il y a une note en bas de page qui fait que ce n'est pas vraiment la logique linéaire (il y a par exemple un axiome en plus, ou un connecteur en moins, ou seulement un fragment du système, ou quelque autre variation), et l'élégance est rompue ; et aussi, pour cette raison, l'intuition qu'on peut se former est brouillée.

De quoi s'agit-il ? D'un système formel inventé par le logicien français Jean-Yves Girard en 1987. J'avoue ne guère avoir d'idée de ce qu'il voulait faire avec, parce que les textes de Girard sont… un peu inhabituels… bourrés de mots qu'il ne définit pas, de références cryptiques, et de blagues dont on se demande si ce sont des blagues (comme l'intervention insistante du brocoli dans beaucoup de ses papiers). Mais depuis, elle a trouvé diverses applications et connexions : en logique, en informatique théorique ou plus appliquée, en algèbre et théorie des catégories, en théorie des jeux et même en physique quantique (sauf qu'à chaque fois, comme je le dis ci-dessus, il y a quelque chose en plus ou en moins) ; mais je ne compte pas essayer de décrire ces applications et connexions, qui sont pourtant sans doute ce qu'il y a de plus intéressant dans l'histoire, parce que je n'ai pas l'espace ni le temps pour ça.

Bref. Avant d'expliquer quelles sont les règles du jeu, il faut que j'essaye de donner une idée de ce dont il s'agit (en agitant les mains). On parle de logique linéaire, et il s'agit effectivement d'une généralisation de la logique classique, mais ce terme risque de donner une impression tout à fait fausse, et on devrait peut-être plutôt s'imaginer que ça s'appelle formalisme d'échanges ou synallagologie universelle ou quelque chose de ce genre (le seul problème du mot synallagologie est que personne ne sait ce qu'il veut dire puisque je viens de l'inventer… mais à part ça, il est parfait). La différence essentielle est la suivante : en logique usuelle, si on fait un raisonnement tendant à démontrer une conclusion X à partir d'hypothèses A, B et C, disons, on peut utiliser librement A, B et C dans le cours du raisonnement, chacune aussi souvent qu'on veut (on peut aussi, d'ailleurs, ne pas du tout utiliser une hypothèse) ; la logique linéaire, pour sa part, exige que chacune des « hypothèses » (qu'il vaut mieux, du coup, ne pas considérer comme des hypothèses) soit utilisée une et une seule fois : on ne peut ni les multiplier ni les faire disparaître (évidemment, il y aura des moyens de marquer des hypothèses spéciales qu'on peut multiplier et/ou faire disparaître, mais ce n'est pas le cas par défaut) ; dans ces conditions, il vaut mieux, donc, considérer qu'on n'a pas du tout à faire à une logique, à des raisonnements et à des hypothèses et conclusions, mais à des échanges (gestion de ressources abstraites, transactions économiques, réactions chimiques, que sais-je encore) qui ont des entrées (réactifs) et des sorties (produits), ou quelque chose comme ça. Par exemple, la logique linéaire pourrait concevablement servir à formaliser des contrats financiers (j'avais déjà évoqué quelque chose de ce genre), mais il ne faut pas s'imaginer que la logique linéaire elle-même dira grand-chose d'intéressant : de même que la logique classique ne fournit que le langage le plus basique au-dessus duquel on peut bâtir des raisonnements (il faut ajouter des axiomes intéressants pour obtenir quelque chose d'intéressant), la logique linéaire n'est qu'un cadre, en lui-même extrêmement primitif pour possiblement décrire des échanges.