David Madore's WebLog

This WebLog is bilingual, some entries are in English and others are in French. A few of them have a version in either language. Other than that, the French entries are not translations of the English ones or vice versa. Of course, if you understand only English, the English entries ought to be quite understandable without reading the French ones.

Ce WebLog est bilingue, certaines entrées sont en anglais et d'autres sont en français. Quelques-unes ont une version dans chaque langue. À part ça, les entrées en français ne sont pas des traductions de celles en anglais ou vice versa. Bien sûr, si vous ne comprenez que le français, les entrées en français devraient être assez compréhensibles sans lire celles en anglais.

Note that the first entry comes last! Notez que la première entrée vient en dernier !

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

(vendredi)

Encore des aventures avec le commerce en ligne

Bienvenue sur ce blog pour un nouveau numéro de First World Problems dans le grand cycle des ronchonneries de Gro-Tsen.

Acheter des choses sur Internet (quelque chose que je fais beaucoup) marche merveilleusement bien quand ça marche : tout est automatisé, on va sur un site marchand, on cherche le produit qu'on veut, clic clic clic on saisit son adresse, un numéro de carte bancaire (dans mon cas, comme je le disais récemment, toujours un numéro de carte temporaire à usage unique valable pour le seul montant que je dois payer, ça apporte une grande tranquillité d'esprit si on décide d'acheter des choses sur des sites chinois suspects), et le produit arrive quelque temps plus tard. Mais le revers de ce système totalement automatisé, c'est que s'il y a un problème, on est vite pris dans un monde kafkaïen où il est impossible de communiquer avec un humain. (Une des choses, d'ailleurs, qui fait le succès de l'employeur de mon poussinet auprès de leurs clients, c'est justement qu'ils mettent les ressources humaines nécessaires pour répondre aux mails des gens qui ont un problème. Au lieu de, par exemple, déléguer ça à un call-center outsourcé très loin. Mais ils sont l'exception et pas la règle.)

Alors certes, on est facilement remboursé. Depuis le temps que j'achète des choses en ligne, y compris, je le disais, parfois sur des sites un peu suspects et mal traduits depuis le chinois, il ne m'est encore jamais arrivé que je paie, que le produit n'arrive jamais et que je n'obtienne pas de remboursement. Il m'est arrivé que le produit soit merdique, ne colle pas avec sa description, que la réexpédition soit trop chère et que je me dise que tant pis autant prendre ce qu'on m'a envoyé. Mais quand je ne reçois rien, je suis toujours remboursé (au moins jusqu'à présent : peut-être que j'ai eu énormément de chance, après tout ; d'un autre côté, les choses que j'achète ne sont jamais très chères, donc même si ça m'arrivait, ce ne serait pas un drame).

Et de fait, il arrive relativement souvent que je ne reçoive rien. Parce que le problème avec le processus tout automatisé du commerce en ligne, c'est la dernière étape : la livraison. Dans la course effrénée à diminuer les coûts, on s'est mis à faire appel à des transporteurs dont l'incompétence s'apparente véritablement à de l'escroquerie (ils ne font aucun effort pour livrer le colis, ne passent pas sonner chez vous ni laisser un avis de passage, ils décident simplement que vous n'êtes pas là et renvoient le colis à l'expéditeur qui en est quitte pour les frais de livraison). Dans le meilleur des cas il faut passer la journée chez soi, dans le pire, même ça ne suffit pas : c'est pour ça que je préfère, quand c'est possible, faire livrer à un point de retrait (commerçant du quartier ou bureau de poste), mais ce n'est pas toujours, justement, possible. Bon, je vais éviter de réécrire ce que j'ai déjà raconté, tout le monde sait déjà ça.

Le truc, c'est qu'être remboursé n'est généralement pas ce qu'on veut. Ce qu'on veut, c'est le produit qu'on achetait : si on a fait la démarche de l'acheter, c'est qu'on estime que ce produit avait une valeur (une utilité, au sens microéconomique) supérieure au prix demandé par le vendeur plus le temps consommé à passer la commande. Donc si on reçoit le remboursement au lieu du produit, on n'est pas content du tout. À cela s'ajoute un effet psychologique : dès lors qu'on a passé commande et payé pour quelque chose, on passe dans le modèle mental où on en est propriétaire, et il y a un attachement qui se crée qui fait qu'on donne à l'objet une valeur plus grande que celle qu'on a payée — du coup, on ne sera plus prêt à le revendre pour le même prix. Le scénario suivant sera peut-être éclairant : si on organise une vente aux enchères d'un artefact historique inestimable (disons, le gobelet MacDonalds dans lequel Jésus a bu son Coca-Cola lors de son dernier repas avec ses douze potes préférés), que les enchères atteignent des niveaux stratosphériques, et que finalement on annonce que c'était une blague et que l'objet n'existe pas, celui qui pensait avoir remporté l'enchère sera furieux d'être privé de la victoire qu'il pensait avoir reportée.

Or quand j'achète des choses en ligne, souvent le problème n'est pas le prix, c'est la disponibilité. La loi de la distribution logarithmique fait que dans l'ensemble des prix de l'Univers il y a essentiellement deux catégories : les choses qui sont trop chères pour que je puisse me les payer, et les choses qui sont tellement peu chères que le prix m'importe très peu — évidemment, il arrive qu'on tombe entre les deux, mais c'est finalement assez rare. Ce qui limite mes achats en ligne, c'est donc souvent d'autres choses que l'argent : l'espace de stockage dans mon appartement, ou la disponibilité des produits en ligne (ou parfois, aussi, la flemme de passer commande, ce qui implique souvent de créer une adresse mail pour le site, générer un mot de passe bidon, etc.).

Récemment j'avais acheté un foobar bleuté dont j'étais particulièrement content. Je voulais en acheter un deuxième, si possible exactement identique. Malheureusement, entre temps, beaucoup des sites marchands vendant des foobars avaient cessé d'avoir ce modèle. Et le problème quand on cherche un terme dans Google c'est qu'on tombe sur plein de pages qui décrivent le produit en question juste pour dire qu'il n'est plus disponible : on a beau ajouter -"épuisé" -indisponible -"sold out" -"out of stock" -unavailable -ausverkauft -"nicht verfügbar" et plein d'autres choses comme ça à la fin de la recherche, ça ne marche jamais complètement. Quand on ajoute la difficulté à filtrer uniquement les sites qui veulent bien livrer dans l'Union européenne, les choses se compliquent encore. J'ai donc passé un temps considérable à dénicher le site qui avait encore mon foobar bleuté : une petite entreprise familiale appelée Amazon.fr. (Je ne plaisante pas, le produit était bien sur Amazon, enfin, ce n'est pas Amazon qui le vend, ils font juste les intermédiaires-qui-se-sucrent-au-passage, mais je ne sais pas pourquoi c'était très difficile à trouver chez eux.) J'ai passé commande en mettant mon adresse professionnelle comme adresse de livraison, espérant qu'elle soit un peu plus fiable (l'avantage est qu'il y a toujours quelqu'un pour réceptionner). Mais le colis n'est quand même pas arrivé. Je n'ai aucune explication, bien sûr : le site Web de Colissimo me dit juste successivement Votre colis est arrivé sur son site de distribution (le 19 avril) puis Votre colis n'a pas pu être livré, il est retourné à l'expéditeur (le 20 avril), et enfin Votre colis est livré à l'expéditeur suite à un retour (le 21 avril) ; je n'ai aucune idée de ce qui s'est passé. Peut-être la poste a-t-elle buggué, peut-être l'expéditeur a-t-il mal imprimé mon adresse, peut-être est-ce un gag comme ceci (j'ai donné mon adresse professionnelle avec un cedex, ne sachant pas que l'expéditeur était en Allemagne : peut-être que ça embrouille les choses). [Mise à jour : Il semble que le problème était dans le transfert de l'adresse entre Amazon et l'expéditeur.]

Je vais sans doute être remboursé. Je m'en fous, ce n'est pas ça mon problème. Mon problème est que je voulais le foobar bleuté. Et que le temps que je m'aperçoive de l'échec de la livraison, il est passé de très difficile à trouver en ligne à quasiment impossible à trouver en ligne.

J'ai bien sûr essayé d'écrire à l'expéditeur pour demander s'ils pouvaient renvoyer le colis ou me le mettre de côté, au lieu de simplement me rembourser. Mais bien sûr, ce n'est pas possible « pour des raisons techniques » (je suppose qu'ils ont une organisation extrêmement compartimentée, et les gens qui gèrent les retours et l'inventaire ne parlent jamais aux gens du support client : c'est précisément ce type d'organisation qui conduit à des situations ubuesques ; en tout cas, retour⇒remboursement, il n'y a pas d'autre solution). J'ai demandé si le produit redeviendrait disponible lorsque mon retour serait pris en compte, j'ai eu une réponse très vague dont la signification était sans doute que celui qui m'écrivait n'en savait pas plus que moi : est-ce qu'il a déjà été acheté par quelqu'un d'autre ? est-ce qu'il s'est perdu dans leur stock ? mystère. Il faut dire aussi que ma communication avec l'expéditeur passe obligatoirement par Amazon, qui fait tout son possible pour nous empêcher de nous parler directement ou simplement (par exemple, il nous est interdit d'échanger une adresse mail, il faut passer par un formulaire sur le site d'Amazon, accompagné d'un gros avertissement comme quoi tout ce que je dirai sera censuré par Amazon pour ma protection — tout ceci a un côté délicieusement kafkaïen).

Du coup, j'ai essayé de développer un plan B, ou plutôt des plans B, C et D.

Plan D : j'ai trouvé un foobar identique, mais pas de la bonne couleur (il est bleu au lieu d'être bleuté) ; bon, j'ai quand même passé commande de ça, on verra bien si ça arrive, même si je suis un peu sceptique parce que la version en français du site Web marchand avait tellement d'erreurs de traduction et de liens cassés que j'ai dû manuellement changer trois fois d'URL juste pour commander, il y a des bonnes chances que mon paiement soit parti dans l'espace. (Le site original doit être en suédois. Moi je n'ai pas de problème pour commander sur un site en suédois, sauf qu'il refuse de me laisser entrer une adresse de livraison en France : il faut passer par le site en français pour ça.) Plan C : j'ai mis en place des scripts Perl qui téléchargent régulièrement la page décrivant le foobar bleuté sur le site d'Amazon et le site principal du vendeur qui n'avait pas réussi à me l'expédier, et qui m'enverront un mail s'il redevient disponible. Mais j'y crois assez peu.

Plan B : j'ai quand même trouvé un site marchand, ça semble être une toute petite boutique, qui prétend encore avoir le foobar bleuté ; seulement, ils ne livrent qu'en Allemagne, Suisse, Autriche et Luxembourg. (Je n'ai jamais compris la raison de ce genre de choses : est-ce pour des raisons légales ? parce qu'ils ont la flemme de faire un site Web en autre chose qu'en allemand ? mais même dans ce cas, pourquoi interdire aux germanophones qui habiteraient en France de passer commande ?) Plan B₁ : je leur ai envoyé un mail dans mon meilleur allemand en leur demandant s'ils pouvaient quand même m'autoriser à passer commande chez eux et en disant que je suis bien sûr prêt à payer tous les frais supplémentaires qui pourraient en résulter. Pour l'instant, ils n'ont pas répondu, et je commence à douter qu'ils le feront. Plan B₂ : trouver quelqu'un habitant dans un de ces pays qui veuille bien recevoir et réexpédier le foobar bleuté ; seulement, en fait, je ne connais personne qui habite dans un pays germanophone et à qui je pourrais raisonnablement demander ce service, donc peut-être que je devrais aller passer une petite annonce sur Reddit (avec des chances de tomber sur quelqu'un de malhonnête, mais bon, ce n'est pas non plus un drame). L'arbre des plans et sous-plans se divise sérieusement. À ce stade-là, ce n'est plus une question de combien je veux avoir mon foobar bleuté, c'est un peu un défi de voir si je vais m'en sortir.

(Pour ceux qui sont vraiment curieux de savoir ce que je cherche à acheter, ce n'est pas vraiment passionnant : voyez ici, , ou . Oui, d'accord, bleuté veut dire gris et noir. Et tous ces liens s'autodétruiront certainement dans quelques mois vue la fugacité du Web marchand — ceci dit, pour des produits de toute façon indisponibles, ce n'est pas forcément un mal.)

(mardi)

Le lemme de Higman expliqué aux enfants

Ceci est un peu une expérience de vulgarisation scientifique : je voudrais essayer d'expliquer et de démontrer un résultat mathématique non-trivial en m'adressant aux gens n'ayant aucune connaissance mathématique particulière (même pas, en principe, ce qu'est un nombre), mais seulement un peu de patience pour lire des explications plutôt verbeuses (bon, OK, si je demande de la patience, ce n'est pas vraiment pour les enfants, mais je ne sais pas quoi dire d'autre). Je pense que cela peut servir d'exemple pour illustrer ce à quoi peut ressembler le travail d'un mathématicien et les raisonnements qu'il fait, et surtout, pourquoi il peut s'agir de tout autre chose que de formules et de calculs. (Ceci étant, la vulgarisation mathématique est quelque chose de difficile parce qu'en plus de chercher à expliquer les concepts ou les outils eux-mêmes, il faut trouver quelque chose à répondre aux gens qui demanderont des choses comme à quoi ça sert de se poser ce genre de question ? de façon plus ou moins agressive.) Ai-je réussi à rendre les choses compréhensibles ? À vous de me le dire — enfin, à ceux d'entre vous qui ne sont pas déjà mathématiciens.

C'est aussi un petit exercice un peu oulipien : expliquer une démonstration mathématique sans utiliser de « variables » (je veux dire des choses comme le nombre n, le mot w, le langage L, l'ensemble S, etc., ou a fortiori la suite (vi)) pour désigner les objets, puisque je ne suppose pas mon lecteur familier avec cette façon de désigner les choses. (Ce petit exercice est peut-être complètement stupide, d'ailleurs, parce qu'il n'est pas clair que m'obliger à utiliser des périphrases comme le mot qu'on considérait ou le langage dont on était parti aide vraiment à comprendre, et je pense même le contraire : mais cet exercice à l'intérêt de m'obliger à limiter le nombre d'objets manipulés dans une phrase donnée, à donner des exemples, etc., donc je pense qu'il a du bon.) J'ai quand même réécrit la démonstration une deuxième fois avec ce genre de langage, pour comparer (là aussi, aux non-mathématiciens de me dire si c'est plus ou moins clair).

J'ai choisi pour l'exercice un théorème de combinatoire : le lemme de Higman. Pourquoi précisément le lemme de Higman ? Parce que c'est un résultat important, relativement récent (1952), que je trouve très joli, et dont la démonstration, simple, élégante et pas trop longue, ne fait appel à aucun concept sophistiqué, mais est un bon exemple de raisonnement pas du tout trivial aboutissant à une conclusion peut-être surprenante. Mais aussi parce que cette démonstration contient des idées mathématiques importantes (un raisonnement par l'absurde qui est une forme de descente infinie), et parce que le résultat lui-même admet des myriades d'applications et de généralisations dans toutes sortes de directions, dont certaines sont des sujets de recherche actifs, et dont certaines utilisent une démonstration relativement proche de celle que je vais présenter.

Alors, de quoi s'agit-il ?

Je commence par présenter le contexte.

On va d'abord parler de mots, et je vais expliquer exactement ce que j'entends par là. Un mot est une succession (finie) de lettres de l'alphabet. Par exemple : abracadabra est un mot (d'une longueur de 11 lettres, mais peu importe, j'ai dit qu'il n'était pas nécessaire de savoir compter). Un mot n'est pas obligé d'avoir un sens en français ou dans une quelconque autre langue : kvtyeohegwnfth est un mot valable. Un mot peut être arbitrairement long : anticonstitutionnellementologiepouettruc est un mot valable. Il peut aussi être arbitrairement court : a est un mot. On va même autoriser le mot, appelé mot vide, qui n'a aucune lettre dedans (de longueur zéro) : il y a juste un petit problème pour l'écrire parce qu'il ne se voit pas, d'où l'intérêt de mettre des guillemets autour pour qu'on le voie quand même : (est le mot vide). Une lettre peut être répétée autant de fois qu'on veut : aaaaaaaaaaaaaa est un mot parfaitement valable (et différent de aaaaaaaaaaaaa).

En revanche, on n'a pas le droit à autre chose que des lettres : pouet42truc n'est pas autorisé. Ou du moins il ne l'est pas si on est convenu à l'avance que l'alphabet est formé des lettres ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’, ‘l’, ‘m’, ‘n’, ‘o’, ‘p’, ‘q’, ‘r’, ‘s’, ‘t’, ‘u’, ‘v’, ‘w’, ‘x’, ‘y’ et ‘z’ à l'exclusion de toute autre : en fait, le lemme de Higman marchera tout aussi bien si je veux ajouter les chiffres dans l'alphabet, ou les caractères accentués, ou les majuscules ; ou si je prends l'alphabet grec, ou russe, ou sanskrit, ou tous les caractères chinois : la seule chose qui importe est que l'alphabet soit fini et décidé à l'avance et qu'on n'y touche plus (et on pourra toujours appeler lettres les choses qu'on a mises dans l'alphabet) ; mais pour fixer les idées dans cette explication, on va dire qu'il s'agit de l'alphabet latin minuscule, c'est-à-dire exactement des — 26 mais peu importe — caractères que je viens d'énumérer.

Ce concept étant (j'espère) clair, on va jouer à un petit jeu (à seul ou à plusieurs) consistant à écrire des mots les uns à la suite des autres.

La seule règle du jeu est la suivante : une fois qu'un mot a été écrit, il n'est plus autorisé d'écrire un mot qui s'obtient en ajoutant des lettres dans le mot en question (au début, à la fin, n'importe où au milieu, ou tout ça à la fois). Par exemple, si le mot truc a été joué, on ne peut plus jouer trucage, mais pas non plus trouc ni structure ni autruche ni tirebouchon (eh oui, dans tirebouchon il y a truc, voyez : tirebouchon) ni introductif (idem : introductif), ni cturtutrcu (cherchez bien, il y a moyen de retrouver truc dans cet ordre en retirant les bonnes lettres : cturtutrcu). Et, bien sûr, on ne peut pas rejouer truc lui-même. Si le mot a a été joué, on ne peut plus jouer aucun mot comportant un ‘a’ n'importe où. (Et si le mot vide a été joué, plus aucun mot n'est jouable et le jeu doit s'arrêter.) • Pour parler de façon plus concise, un mot qui s'obtient à partir d'un autre en ajoutant des lettres s'appellera un sur-mot, et inversement, l'autre (qui s'obtient en retirant des lettres n'importe où) s'appellera un sous-mot : donc truc est un sous-mot de tirebouchon et tirebouchon est un sur-mot de truc (et tout mot contenant la lettre ‘a’ est un sur-mot de a, et tout mot est un sur-mot du mot vide). On convient que tout mot est un sur-mot et un sous-mot de lui-même. La règle du jeu est donc : on ne peut pas jouer un mot dont un sous-mot a déjà été joué, ou encore, jouer un mot « grille » (consomme, interdit, bannit) définitivement tous ses sur-mots. C'est là la seule règle.

Évidemment, si on veut vraiment faire un jeu intéressant à partir de l'histoire, il faudra ajouter des règles décidant qui gagne (par exemple, en disant que celui qui joue le mot vide perd — si on décide qu'il gagne, le jeu n'est vraiment pas bien palpitant ; en fait, même si on décide qu'il perd, il y a une stratégie gagnante très facile). Mais ce n'est pas tellement ça qui va m'intéresser.

Pour que la règle soit claire, voici une petite application bricolée en JavaScript qui doit l'appliquer (on entre des mots en bas, il vérifie qu'ils sont bien des mots sur l'alphabet latin ‘a’–‘z’ et qu'ils n'ont pas un sous-mot déjà joué) :

Entrer un mot:

Tout ceci ayant été expliqué, que dit ce fameux lemme de Higman ? C'est très simple : il affirme que quoi qu'on fasse, le jeu terminera toujours au bout d'un nombre fini de mots (au sens où on ne pourra plus rien jouer). Autrement dit, en principe, quoi que vous tapiez dans le petit gadget JavaScript ci-dessus, en théorie, il arrivera forcément un moment où vous ne pourrez plus rien jouer (auparavant, il arrivera un moment où vous ne pourrez plus rien jouer sauf le mot vide, et une fois celui-ci joué, plus rien n'est possible du tout).

Ou, pour dire les choses autrement : si on prend une liste infinie de mots (sur l'alphabet latin ‘a’–‘z’), quelle que soit la manière dont ils sont générés, il y a toujours un mot dans la liste qui a un sous-mot en amont dans la liste, ou de façon équivalente, il y a toujours un mot qui a un sur-mot en aval (rendant la liste illégale dans le jeu que j'ai exposé). C'est généralement sous cette forme que le lemme est énoncé, mais je trouve plus clair de décrire le petit jeu qui interdit de jouer un mot qui a un sous-mot en amont, et d'énoncer le résultat sous la forme le jeu s'arrête forcément.

C'est assez théorique, bien sûr. Si on expérimente avec l'application ci-dessus, on se rend compte qu'il est très facile de jouer longtemps… très longtemps. Et on n'a pas vraiment l'impression que ça doive s'arrêter. Il faut dire que déjà avec les mots de trois lettres on a beaucoup de possibilités (17 576 mais peu importe), donc rien qu'en jouant tous les mots de trois lettres un par un (dans l'ordre alphabétique, par exemple : aaa puis aab, puis aac et ainsi de suite jusqu'à zzz), on peut tenir très longtemps — car un mot de trois lettres ne peut jamais avoir un autre mot de trois lettres comme sous-mot si ce n'est le même. Et la même chose vaut avec quatre lettres, donc en jouant les mots de quatre lettres à la place de trois, on peut tenir encore plus longtemps (456 976 pour être exact, mais peu importe ; par contre, pour que les choses soient claires, si on a déjà joué tous les mots de trois lettres, il est trop tard pour jouer ceux de quatre, ils ont tous un sous-mot de trois lettres déjà joué, donc sont eux-mêmes injouables).

C'est l'occasion de souligner la différence en mathématiques entre forcément fini et borné : on ne peut pas dire a priori, combien de temps le jeu durera (ce serait ça qu'on appellerait borné : si on pouvait mettre une borne a priori sur le nombre de mots). Si on joue le mot vide au premier coup, le jeu s'arrête immédiatement. Si on se met à énumérer tous les mots de mille lettres systématiquement, il durera très longtemps. Le lemme de Higman dit juste que quoi qu'on fasse, même si on essaye d'augmenter la longueur des mots, on finira par tomber à court de mots à jouer — il ne dit rien sur le temps que ça durera.

J'aurais d'autres commentaires à faire sur le lemme de Higman, et sur la question de savoir s'il est intuitif ou non, mais je vais garder ça pour une autre fois.

Maintenant je vais essayer de présenter une démonstration du lemme de Higman qui soit compréhensible sans aucune connaissance mathématique particulière. Comme je le disais initialement, je vais aussi rédiger la démonstration sans utiliser aucune notation mathématique, uniquement en français (je la re-rédigerai juste après avec des notations mathématiques, pour permettre de comparer).

Mon but est de montrer qu'il n'y a pas moyen de produire une suite (=liste) infinie de mots qui respecte la règle du jeu que j'ai énoncée plus haut, autrement dit, dans laquelle aucun mot ne soit un sous-mot d'un mot ultérieur. Pour dire les choses de façon plus concise, j'appellerai miraculeuse une telle suite de mots : une suite miraculeuse est donc une partie infinie (=qui ne termine jamais) du jeu expliqué ci-dessus. L'objectif est de montrer qu'il n'existe pas de suite miraculeuse. Pour ça, je vais utiliser une technique utilisée raisonnement par l'absurde dans laquelle je suppose que mon objet existe (ou plus généralement, que la conclusion que je veux atteindre est fausse), j'en tire des conclusions jusqu'à arriver à quelque chose de manifestement impossible, et j'en conclus que puisque l'existence de mon objet est absurde, c'est qu'il n'existe pas.

Supposons donc « par l'absurde » qu'il existe une suite miraculeuse. Maintenant, pour arriver à une contradiction, mon plan va être le suivant : je vais construire une suite miraculeuse « minimale » (et expliquer ce que j'entends par minimale), puis je vais montrer que je peux trouver une autre suite miraculeuse qui contredit sa minimalité parce qu'elle est en un certain sens plus petite (là aussi, il faut expliquer ce que ça veut dire).

Puisque j'ai fait l'hypothèse (dont je cherche à prouver l'absurdité…) qu'il existe une suite miraculeuse, il y a certains mots qui peuvent apparaître comme premier mot d'une suite miraculeuse, c'est-à-dire qu'en jouant un tel mot en premier on peut continuer à jouer indéfiniment ; il y en a aussi d'autres qui ne peuvent pas, c'est-à-dire qu'en jouant un tel mot en premier le jeu sera forcément bloqué : de tels mots existent, parce que le mot vide en est un (si on joue le mot vide, on est immédiatement bloqué, donc il ne peut apparaître nulle part dans une suite miraculeuse, et en particulier, pas en premier).

Considérons un mot qui peut commencer (=apparaître en premier dans) une suite miraculeuse : essayons de lui retirer sa première lettre : soit il peut encore commencer une suite miraculeuse (éventuellement complètement différente), soit non ; si oui, on retire encore sa première lettre ; et on continue à à retirer la première lettre du mot jusqu'à ce qu'en se faisant on arrive à un mot qui ne commence aucune suite miraculeuse (comme je l'ai dit, cela va forcément se produire, parce que le mot vide ne commence pas une suite miraculeuse). Arrêtons-nous juste avant : on a ainsi fabriqué un mot qui commence une suite miraculeuse, mais qui est tel que si on retire sa première lettre ce ne soit plus le cas. (Par exemple, peut-être qu'il existe une suite miraculeuse qui commence par abracadabra, et encore une, peut-être complètement différente mais peu importe, qui commence par bracadabra et encore une qui commence par racadabra, par acadabra, par cadabra mais pas par adabra : alors on s'arrêtera au mot cadabra, qui commence une suite miraculeuse mais tel que si on retire sa première lettre ce ne soit plus le cas ; c'est-à-dire, si on joue cadabra en premier il est possible de jouer indéfiniment, mais si on joue adabra en premier ce n'est pas possible.) Écrivons le mot qu'on a obtenu (dans mon exemple, cadabra), et on ne va plus y toucher : ce sera le premier mot de la « suite miraculeuse minimale » qu'on essaie de construire progressivement.

Maintenant, on va faire pareil en cherchant les suites miraculeuses qui commencent par le mot qu'on vient d'écrire, et en considérant le mot suivant (i.e., juste après dans la suite). On sait qu'il y a une suite miraculeuse qui commence par le mot qu'on a écrit (dans mon exemple, c'était cadabra) : il est donc possible de mettre un second mot après qui permette de jouer indéfiniment, i.e., de former une suite miraculeuse (peut-être izebulon). On va de nouveau retirer sa première lettre jusqu'à ce que ce ne soit plus le cas, et s'arrêter juste avant (donc par exemple, peut-être qu'il y a façon de jouer indéfiniment après les deux mots cadabra, izebulon et aussi après cadabra, zebulon, mais plus après cadabra, ebulon : dans ce cas, on s'arrête à zebulon). Écrivons le mot qu'on a obtenu (dans mon exemple, zebulon) : on a maintenant deux mots, on sait qu'en jouant ces deux mots on peut jouer indéfiniment, mais si on retire la première lettre du premier il n'y a pas moyen de jouer indéfiniment en commençant comme ça, et pareil, après avoir joué le premier, si on retire la première lettre du deuxième. (Dans mon exemple, il y a une suite miraculeuse commençant par cadabra, zebulon, mais aucune qui commence par cadabra, ebulon, ni par adabra.)

On continue le procédé de la même manière : quand on a écrit un certain nombre de mots, qui à chaque fois peuvent commencer une suite miraculeuse, on cherche un mot qu'on peut mettre après eux et qui permette de jouer indéfiniment (i.e., après les précédents, il commence une suite miraculeuse), et on retire sa première lettre jusqu'à ce que ça ne commence plus une suite miraculeuse, et on s'arrête juste avant. On obtient ainsi une suite infinie de mots.

La suite que j'ai écrite est elle-même miraculeuse : en effet, si on peut la compléter à partir de n'importe quel point en une suite miraculeuse, c'est-à-dire si le jeu n'est jamais perdu, c'est bien que la suite elle-même est miraculeuse, c'est-à-dire que la règle du jeu n'est jamais enfreinte. En revanche, si on jouait les premiers mots de la suite puis le un mot qui vient juste après privé de sa première lettre, on se retrouverait forcément bloqué après. C'est cette suite que j'appelle une suite miraculeuse minimale : une suite miraculeuse telle qu'en retirant la première lettre d'un quelconque de ses mots, je ne puisse pas compléter à partir de là pour obtenir une suite miraculeuse.

À ce stade-là de la démonstration, j'ai donc montré l'existence de cette suite miraculeuse minimale à partir de la seule existence d'une suite miraculeuse, je n'ai pas eu besoin d'autre hypothèse (s'il existe une suite miraculeuse, il en existe une minimale, et j'ai expliqué comment la fabriquer ; on ne peut pas dire que j'aie donné un « algorithme » pour obtenir ma suite miraculeuse minimale, parce que j'ai dû faire certaines choses qui sont algorithmiquement impossibles, mais j'ai bien montré son existence).

Maintenant on va fabriquer une nouvelle suite à partir de la suite miraculeuse minimale. (Je l'appellerai toujours la nouvelle suite dans ce qui vient.)

Pour construire cette nouvelle suite, regardons la première lettre de chacun des mots de ma suite miraculeuse minimale. Comme il y a une infinité de mots dans la suite, et qu'il n'y a qu'un nombre fini de lettres dans l'alphabet, il y en a forcément (au moins !) une qui revient infiniment souvent comme première lettre. (En effet, si chacune des lettres n'apparaissait qu'un nombre fini de fois comme première lettre, ça ne ferait qu'un nombre fini de mots au total, or nos suites sont infinies.) Choisissons une lettre qui revient infiniment souvent comme première lettre des mots de ma suite miraculeuse minimale, et appelons cette lettre lettre-clé.

Maintenant, on va considérer une nouvelle suite formée à partir de la suite miraculeuse minimale : cette nouvelle suite est formée de (a) tous les mots qui viennent dans la suite miraculeuse minimale (strictement) avant le premier mot commençant par la lettre-clé, et (b) tous les mots de la suite miraculeuse minimale commençant par la lettre-clé, mais auxquels on a retiré la première lettre en question. (Par exemple, si ma suite miraculeuse minimale était quelque chose comme cadabra, zebulon, mumble, zork, corge, zygmund, zazie… et qu'il y a une infinité de mots commençant par ‘z’ et que j'ai décidé de la prendre pour lettre-clé, je vais construire la suite cadabra, ebulon, ork, ygmund, azie… : j'ai gardé (a) tous les mots venant avant le premier mot commençant par ‘z’, et (b) à partir de lui, seulement les mots commençant par ‘z’ moins leur lettre initiale.)

Maintenant, pour arriver à la contradiction, je vais expliquer deux choses : primo, ma nouvelle suite est aussi miraculeuse ; et secundo, elle ne peut pas être miraculeuse. Bref, une contradiction.

Pourquoi ma nouvelle suite est-elle miraculeuse ? Imaginons au contraire qu'un mot de la nouvelle suite soit un sous-mot d'un mot ultérieur. Alors (vais-je expliquer) c'est forcément aussi le cas dans la suite suite miraculeuse minimale : en effet, on obtient des mots de la suite suite miraculeuse minimale en ajoutant peut-être la lettre-clé au début des mots correspondants de la nouvelle suite ; peut-être, c'est-à-dire, si elle avait été supprimée, c'est-à-dire, si on était dans le cas (b) ci-dessus. Mais des deux mots en question, soit ils sont tous les deux dans le cas (a) (i.e., ce sont des mots de la suite miraculeuse minimale qui ne commençaient pas par la lettre-clé), auquel cas il n'y a rien à rajouter et le premier est bien un sous-mot du second ; soit ils sont tous les deux dans le cas (b) (i.e., ils commençaient par la lettre-clé, elle a été retirée), auquel cas en remettant la lettre-clé au début, le premier est bien encore un sous-mot du second ; soit le premier est dans le cas (a) et le second dans le cas (b), auquel cas le premier est bien un sous-mot du second a fortiori quand on remet la lettre-clé au début du second ; et ce n'est pas possible que le premier soit dans le cas (b) et le second dans le cas (a) car le premier doit venir avant le second. Bref, dans tous les cas, si un mot de la nouvelle suite était sous-mot d'un mot ultérieur, ce serait encore le cas dans la suite miraculeuse minimale : or on sait que ce n'est pas le cas pour celle-ci (précisément parce qu'elle est miraculeuse), donc ce n'est pas non plus le cas pour celle-là, qui est donc elle-même miraculeuse.

Mais inversement, la nouvelle suite ne peut pas être miraculeuse : ceci résulte de la minimalité de la suite miraculeuse minimale ; en effet, considérons le premier mot de la suite miraculeuse minimale qui commence par la lettre-clé : ce mot avait justement été choisi de sorte qu'en retirant la première lettre il n'y ait aucune suite miraculeuse qui commence de la sorte ; mais la nouvelle suite est justement une suite qui commence de la sorte. Donc elle n'est pas miraculeuse.

Donc contradiction.

Donc il n'y a pas de suite miraculeuse du tout.

Et on a donc prouvé le lemme de Higman !

Voici comment on dirait cette démonstration en langage plus mathématique, et surtout avec les notations qui vont avec, donc c'est un peu moins verbeux, mais sans doute plus difficile à lire pour un non-mathématicien :

Notons ww′ pour w est un sous-mot de w. On veut montrer par l'absurde que pour toute suite (infinie) wi de mots, il existe i₁≤i₂ tels que wiwi : appelons miraculeuse une suite qui vérifie le contraire, et supposons par l'absurde qu'il en existe une.

Soit w₀ un mot qui commence une suite miraculeuse mais tel qu'en retirant la première lettre ce ne soit plus le cas (un tel mot w₀ existe bien, comme on le voit en retirant successivement les premières lettres jusqu'à tomber sur le mot vide). Et par récurrence sur i, si les wj pour j<i sont déjà définis, soit wi tel que les wj pour ji commencent une suite miraculeuse mais que ce ne soit plus le cas en retirant la première lettre de wi (un tel wi existe pour la même raison que w₀). On définit ainsi une suite wi, qui est manifestement elle-même miraculeuse (puisque quel que soit i, les wj pour ji commencent une suite miraculeuse : autrement dit, quel que soit i il n'existe pas i₁≤i₂≤i tels que wiwi) ; de plus, elle est telle qu'en retirant la première lettre de wi sans changer les précédents, il n'y ait pas moyen de choisir les termes >i pour former une suite miraculeuse à partir de là.

Soit x une lettre qui commence un nombre infini des wi (une telle lettre existe car l'alphabet est fini et que l'ensemble d'indices est infini), disons que wki soit le i-ième terme de la suite wj commençant par x. Notamment, k₀ est le plus petit indice tel que wk commence par x. Définissons vi par vi=wi si i<k₀, et sinon, vi est obtenu en retirant le x initial du terme wj pour j=k(ik₀) (c'est-à-dire du (ik₀)-ième terme de de la suite wj commençant par x), bref, wj=xvi pour j=k(ik₀).

Montrons que la suite (vi) est miraculeuse. S'il existe i₁≤i₂ tels que vivi, alors soit i₁≤i₂<k₀, auquel cas wi=vi et wi=vi d'où wiwi, ce qui n'est pas ; soit k₀≤i₁≤i₂, auquel cas wj=xvi et wj=xvi (pour j₁=k(i₁−k₀) et j₂=k(i₂−k₀) qui vérifient j₁≤j₂) d'où wjwj, ce qui n'est pas ; soit i₁<k₀≤i₂, auquel cas wi=vi et wj=xvi (pour j₂=k(i₂−k₀) qui vérifie i₁≤j₂) d'où wiwj, ce qui n'est pas. La suite est donc bien miraculeuse.

Mais ceci contredit la minimalité de (wi) : en effet, wk était censé être choisi tel qu'en en retirant la première lettre (ce qui donne vk), aucune suite miraculeuse ne puisse commencer ainsi, i.e., aucune suite miraculeuse ne peut commencer par les vi pour ik₀.

Là j'ai laissé tous les détails. Dans un vrai article de maths, on en omettrait un certain nombre, et ce serait encore environ deux fois plus court. Généralement, la démonstration est plutôt écrite en prenant wi de longueur minimale plutôt que minimale pour l'opération de retirer la première lettre : c'est plus court à écrire, mais c'est inutilement fort, et peut-être plus difficile à expliquer au non-mathématicien, donc j'ai préféré utiliser la construction que j'ai faite. (Par ailleurs, la terminologie standard dans cette démonstration est plutôt de parler de mauvaises séquences pour celles que j'ai qualifiées de merveilleuses, mais mon esprit se rebelle contre cette terminologie : ce qui n'existe pas, c'est justement le merveilleux, mais le mauvais.)

Je voudrais encore essayer d'expliquer une ou deux conséquences du lemme de Higman qui aident peut-être à voir en quoi il est intéressant. Pour ça, il faut que je définisse encore un concept, celui de langage : mathématiquement, un langage est juste un ensemble de mots, mais le terme d'ensemble n'étant pas forcément le plus intuitif, je devrais peut-être plutôt le présenter comme une propriété qu'un mot peut ou ne pas avoir ; par exemple, être un mot français est une propriété, qu'on peut identifier au langage [ensemble des mots] français ; l'ensemble des mots se terminant par un ‘z’ est aussi un langage, qu'on peut identifier à la propriété se terminer par un ‘z ; et ainsi de suite. (Aux deux extrêmes, il y a aussi l'ensemble de tous les mots, ou propriété « trivialement vraie », c'est-à-dire toujours vérifiée, et l'ensemble vide, ou propriété « trivialement fausse », c'est-à-dire jamais vérifiée.)

Donné un langage, on peut construire un nouveau langage qu'on appelle langage des sur-mots du langage de départ, et qui est formé, tout à fait logiquement, des mots qui sont un sur-mot d'un mot du premier langage (i.e., qui ont un sous-mot dans le langage en question). Par exemple, le langage des sur-mots du français est l'ensemble des mots tels qu'en retirant certaines lettres on obtienne un mot français (utfnrcraripbjbubmne en est un, par exemple parce qu'il contient le mot français tribun ou plus simplement parce qu'il contient le mot a, lui aussi français). Si on réfléchit un peu, on peut se convaincre qu'en refaisant cette opération (i.e., si on part d'un premier langage, qu'on considère son langage des sur-mots, et qu'on considère le langage des sur-mots de ce langage-), la deuxième fois ne sert à rien : le langage des sur-mots du langage des sur-mots est juste le langage des sur-mots ; un langage de cette sorte est appelé clos par sur-mots, c'est-à-dire qu'il s'agit d'une propriété des mots qui, quand elle est vérifiée par un mot, est vérifiée par tous ses sur-mots.

Une conséquence du lemme de Higman est le fait suivant : tout langage clos par sur-mots est le langage des sur-mots d'un nombre fini de mots. Autrement dit, si je prends n'importe quel ensemble de mots (=langage) et que je considère tous leurs sur-mots (=langage des sur-mots), en fait je pouvais obtenir le même résultat en partant d'un ensemble fini de mots. Pourquoi ? Parce que je peux lister tous les mots de mon langage de départ (dans un ordre quelconque), et retirer de cette liste tous ceux qui sont un sur-mot d'un mot antérieur, c'est-à-dire exactement ceux qui étaient interdits dans le jeu par lequel j'ai expliqué le lemme de Higman ; en ce faisant, je ne change pas le langage des sur-mots (puisque si un mot est un sur-mot d'un mot de la liste qui est lui-même un sur-mot d'un mot antérieur, le premier mot est directement un sur-mot du mot antérieur de la liste), mais je ne garde qu'un nombre fini de mots puisque le lemme de Higman me dit que toute suite vérifiant la règle du jeu est forcément finie.

Pour ceux qui ont manipulé des outils informatiques comme grep, cela veut dire, aussi, que tout langage clos par sur-mots est rationnel (=définissable par une expression régulière, ou de façon équivalente, par un automate fini), ou ce qui revient au même, qu'en partant de n'importe quel langage et en prenant le langage de ses sur-mots, on obtient toujours un langage rationnel. (Pour faire le lien avec ce que j'ai dit juste avant, si on a un nombre fini de mots, disons corge, grault et flarp, le langage de leurs sur-mots peut se définir par l'expression régulière .*c.*o.*r.*g.*e.*|.*g.*r.*a.*u.*l.*t.*|.*f.*l.*a.*r.*p.* donc il est bien rationnel.)

Ce qui est amusant, c'est qu'à peu près la même chose marche aussi pour les sous-mots. Je prends la peine de l'écrire, parce que j'ai dû me gratter la tête pour retrouver ça (j'étais tout embrouillé par le fait que des gens écrivissent tout langage clos par sur-mots est rationnel et d'autres tout langage clos par sous-mots est rationnel — il s'avère que les deux sont vrais) :

On appelle langage des sous-mots d'un langage celui qui est formé, tout à fait logiquement, des mots qui sont un sous-mot d'un mot du langage donné (i.e., qui ont un sur-mot dans le langage donné). Par exemple, le langage des sous-mots du français est l'ensemble des mots tels qu'en ajoutant certaines lettres on obtienne un mot français (rbn en est un, par exemple parce qu'il est un sous-mot du mot tribun). De même que pour le langage des sur-mots, on peut se convaincre qu'en refaisant cette opération (i.e., si on part d'un premier langage, qu'on considère son langage des sous-mots, et qu'on considère le langage des sous-mots de ce langage-), la deuxième fois ne sert à rien : le langage des sous-mots du langage des sous-mots est juste le langage des sous-mots ; un langage de cette sorte est appelé clos par sous-mots, c'est-à-dire que c'est une propriété des mots qui, quand elle est vérifiée par un mot, est vérifiée par tous ses sous-mots.

Par ailleurs, le complémentaire d'un langage est la propriété contraire : c'est-à-dire, les mots qui n'appartiennent pas au langage donné. (Ainsi, le complémentaire du [langage des mots] français est l'ensemble des mots qui ne sont pas français.) Fait : le complémentaire d'un langage clos par sous-mots est clos par sur-mots (pourquoi ? parce qu'un sous-mot d'un mot du complémentaire ne peut pas être dans le langage de départ, sinon le mot de départ, qui en est un sur-mot, y serait aussi, or justement il est dans le complémentaire).

Du coup, n'importe quel langage clos par sous-mots a un complémentaire qui est l'ensemble des sur-mots d'un nombre fini de mots : cela signifie que pour n'importe quel langage clos par sous-mots, il existe un nombre fini de mots tels que les mots du langage initial sont exactement ceux qui ne sont pas des sur-mots d'aucun des mots de cette liste finie. Ce n'est peut-être pas très parlant dit comme ça, mais, de nouveau, si on sait ce qu'est un langage rationnel, cela signifie que tout langage clos par sous-mots est rationnel : et ça, c'est vraiment loin d'être évident.

Je pourrais en dire encore énormément sur le lemme de Higman, sur ses généralisations (par exemple au cas où l'alphabet n'est plus fini mais bel-ordonné ; ou aux mots parenthésés, ce qui revient plus ou moins au théorème de Kruskal sur les arbres ; ou encore au monumental théorème de Robertson-Seymour), mais je vais m'arrêter là, au moins pour le moment.

Mais s'il y a des gens qui veulent réfléchir à des problèmes de ce genre, en voici un dont j'aimerais bien avoir la réponse.

(lundi)

Les malheurs des mots de passe

Les mots de passe sont une calamité de l'informatique. Rectification : l'authentification des humains est une calamité de l'informatique, et les mots de passe sont la moins mauvaise solution connue — et cette solution est quand même pourrie. Les solutions plus technologiques au problème de l'authentification, par exemple avoir un gadget embarqué contenant les clés d'authentification, qu'on déverrouille par un PIN (et qui s'autodétruit ou demande un PUK si on entre quatre PIN incorrects) sont encore inutilisables en pratique, faute de standards, faute de support matériel généralisé, faute de protocoles de communication établis, etc., sans compter les difficultés pratiques accrues en cas de perte, d'oubli ou de casse du gadget. Les idées comme les empreintes digitales sont des conneries : une empreinte digitale n'a rien de secret (on la laisse traîner partout, justement, même sans le vouloir), peut se récupérer à partir d'une photo et se reproduire de manière à tromper les lecteurs, et elle ne peut pas être changée en cas de fuite, bref, ce n'est certainement pas un secret d'authentification, c'est au mieux un identifiant (login). On est donc coincés avec les mots de passe.

Or les mots de passe sont sujets à un nombre incroyable de contraintes contradictoires. Ils doivent être mémorisables par un humain et faciles à taper, et en même temps être essentiellement impossibles à trouver par essais successifs, donc contenir beaucoup de hasard (d'entropie). Ils ne doivent pas être partagés entre différents systèmes, ou en tout cas entre différents niveaux de sécurité, mais en même temps l'humain a une mémoire très limitée et ne peut pas en retenir plus qu'une poignée. Il doit y avoir moyen de les réinitialiser en cas de perte, mais en même temps cette procédure ne doit pas permettre des attaques. Etc. Toutes ces contraintes se contredisent les unes les autres, et il n'est pas surprenant que les gens fassent des choses mauvaises.

Une question, par exemple, est celle du choix entre l'utilisation d'un petit nombre de caractères un peu exotiques (ponctuation et autres ASCII non-alphabétiques) et un grand nombre de caractères moins exotiques (on a tendance à appeler ça une passphrase, par opposition à password dans ce cas). Un célèbre dessin d'xkcd recommande la passphrase (à partir de l'exemple de correct horse battery staple, très facile à mémoriser). Ce dessin oublie pourtant un paramètre majeur : la difficulté à taper. Ma passphrase PGP est constituée de 8 mots choisis parmi un dictionnaire d'environ 100000 mots, pour une entropie de 8×log₂(100000)>128 bits. Eh bien 8 mots aléatoires (donc pas courants du tout) à taper à l'aveugle, c'est extrêmement difficile, il m'est arrivé de devoir m'y reprendre à plus de trente fois avant d'y arriver ; même si j'essaie de taper lentement, lettre par lettre, je me retrouve souvent à ne plus savoir où j'en suis, à être coincé entre ma mémoire procédurale et ma tentative de faire les choses lentement. Bref, ce conseil est catastrophique, au moins pour moi : je ne comprends pas qu'il soit si souvent répété.

La frappe pose ses propres problèmes, même pour des mots de passe courts. Parfois on croit avoir un bon mot de passe et on se rend compte que le taper sur un smartphone est insupportablement pénible parce qu'il y a des caractères qu'il faut chercher à des endroits introuvables sur le clavier. Ou alors le mot de passe est très pénible à taper sur un clavier français, ou au contraire sur un clavier américain. Ou alors il comporte une succession entre un caractère shifté et un caractère non-shifté, et en tapant vite on relâche trop lentement la touche shift (j'ai eu plein de problèmes avec ça). Le problème de la vitesse de frappe est vraiment crucial : je dois taper des mots de passe parfois des dizaines et des dizaines de fois d'affilée pour faire des mises à jour sur plein de machines (je ne veux pas les rendre dépendantes d'une seule machine, ou accessibles depuis une seule clé d'authentification, pour ne pas avoir un point d'attaque unique).

Et que dire des caractères spéciaux ? Il est recommandé d'en mettre beaucoup dans un mot de passe court, mais plein de caractères peuvent poser problème. J'ai eu, ou j'ai eu vent de, toutes sortes de difficultés avec des caractères particuliers. L'espace, par exemple, que beaucoup de gens imaginent impossible dans un mot de passe. Ou encore, le caractère ~ (tilde) en début de mot de passe pose un problème pénible avec ssh, je laisse les geeks essayer de deviner lequel (indice : on tape souvent son mot de passe juste après la touche entrée). Et bien sûr, il est une mauvaise idée d'avoir des caractères non-ASCII dans un mot de passe. Que de contraintes contradictoires !

Je fais souvent aux gens qui ont des problèmes de mémoire la recommandation suivante pour les mots de passe importants : coupez votre mot de passe en deux : mémorisez-en une moitié que vous ne changerez pas, ou pas trop, et qui ne soit pas trop difficile à retenir, et écrivez l'autre moitié sur un morceau de papier dans votre portefeuille, laquelle moitié peut donc contenir des caractères vraiment exotiques, et aussi varier d'une machine à une autre ou d'un système d'authentification à un autre. Ce n'est pas idéal, mais il vaut mieux avoir un mot de passe comme implant^97w:C qu'une seule moitié de ce truc.

Indépendamment de l'idée d'écrire la moitié sur un papier, couper un mot de passe en deux peut être une idée raisonnable : par exemple, avoir un bout commun aux mots de passe de tous les systèmes importants, et un bout qui varie d'un système à l'autre, pour que la connaissance d'un mot de passe ne donne pas trivialement les autres (de nouveau, ce n'est pas parfait, parce que si c'est répandu ça simplifie les attaques — mais rien d'humainement faisable n'est parfait).

On peut aussi recycler les mots de passe : avoir plusieurs niveaux de sécurité, et à chaque fois qu'on change de mot de passe, l'introduire au niveau de sécurité le plus important, et reprendre le précédent de ce niveau-là pour le mettre au niveau un peu moins important, etc. (ou au moins, faire ça avec la partie qu'on retient vraiment, ou la partie commune à différents systèmes). Ça diminue l'effort de mémoire sans trop compromettre la sécurité.

Les mots de passe sans importance, il vaut mieux les confier au navigateur ou les écrire dans un simple fichier protégé contre la lecture, et ne pas chercher à les retenir. Je ne sais combien de sites Web marchands m'obligent à avoir un mot de passe pour un compte chez eux, je déteste ça, je génère un truc aléatoire avec pwgen et je le stocke dans un simple fichier texte. Je me fous pas mal que quelqu'un puisse accéder à mon compte Amazon, ou même mon compte Facebook (je précise que je ne stocke aucun numéro de carte de crédit sur Amazon, il faut être fou pour ça : j'utilise des numéros de carte de crédit à usage unique, et le mot de passe utilisé pour ça ne sert que pour ça et n'est inscrit que dans ma mémoire ; si je l'oublie, ma banque m'en enverra un nouveau par recommandé). Ceci étant, mon PC est accessible en permanence si j'ai besoin de retrouver un mot de passe « faible » : je ne sais pas ce que je ferais si ce n'était pas le cas et que j'avais besoin d'en lire un.

Il existe des gestionnaires de mots de passe qui stockent ces machins pour vous en les chiffrant (déjà, les navigateurs Web ont ça, mais il en existe aussi comme applications séparées) : encore faut-il avoir une bonne clé, donc une bonne passphrase, pour chiffrer les mots de passe eux-mêmes. Et il faut un système qui rende les mots de passe accessibles tout le temps. Ça peut marcher pour certains, mais quand il s'agit de mots de passe qui doivent marcher tout le temps, même quand la machine est dans un mode de secours, il peut y avoir problème.

Bref, que de contraintes impossibles à réconcilier.

La raison qui m'amène à raconter tout ça, c'est qu'aujourd'hui j'ai été obligé de changer de mot de passe : je n'arrivais pas à accéder à un service Web interne de mon école, il a été suggéré que c'était peut-être à cause d'un caractère exotique dans mon mot de passe, j'ai donc essayé de le changer pour tester (en fait, ce n'était pas le problème) ; mais quand j'ai voulu remettre l'ancien, pas moyen : il ne passait pas un des tests à la con pour les mots de passe faibles (je dis à la con, parce que je suis absolument certain que ce mot de passe était très bon selon toute mesure raisonnable de force des mots de passe). Je n'ai donc pas le droit de revenir à mon ancien mot de passe.

Est-ce grave ? Je n'en mourrai pas, mais c'est pénible. Parce que pour des raisons de cohérence (et pour ne pas devoir retenir des choses inutiles en plus), j'ai dû, du coup, changer mon mot de passe sur quinze ordinateurs ou systèmes différents. Dont des portables que j'ai dû retrouver dans mon foutoir chez moi : rien que ça m'a fait perdre de bonnes heures. Les nouveaux mots de passe que j'ai mis sont moins commode à taper (ne serait-ce que parce qu'il est plus long que l'ancien) : ça va me faire perdre plein de temps en plus à chaque fois que je serai sur le clavier tactile pourri de mon smartphone. Et même s'ils étaient aussi bons, d'ici que je m'y habitue, je vais aussi perdre énormément de temps à me tromper. Et ce n'est pas tout : le mot de passe sur les ordinateurs de mon école servait aussi d'authentification wifi (ce qui est d'ailleurs un grave problème de séparation des niveaux de sécurité[#]), par exemple sur le système Eduroam — tout ça est donc aussi à re-rentrer, et le plus souvent on ne peut pas juste re-rentrer le mot de passe, il faut aussi re-rentrer tout un tas de paramètres barbares avec des noms comme identité d'itinérance et, pour commencer, trouver à quel endroit il faut entrer ces choses-là.

Je suis donc assez furieux, et je me défoule en rantant sur mon blog.

[#] Voici le problème : je veux que mon téléphone mobile puisse se connecter au réseau Wifi quand je suis dans mon école. D'un autre côté, je ne veux pas entrer dans mon téléphone mobile, qui est relativement facilement volable, le mot de passe qui permet de lire mes mails (professionnels). D'où contradiction, si c'est le même mot de passe qui permet de lire mes mails et de me connecter au Wifi. Ou alors il faudrait chiffrer mon téléphone : mais dans ce cas, il demandera un PIN à chaque fois que je voudrai m'en servir, ce qui d'une part est excessivement pénible (encore, si j'avais des choses à protéger, ce serait une chose, mais je fais justement attention à ne rien stocker de vraiment confidentiel sur mon téléphone, précisément pour ne pas avoir à le chiffrer : ce serait idiot d'avoir à le faire uniquement pour le mot de passe du Wifi de mon école !), et d'autre part cela voudrait dire que des tiers ne pourraient pas s'en servir pour contacter mes proches s'il m'arrive un accident, et je trouve ça inacceptable. Que de tracas !

(vendredi)

Réflexions encore plus décousues sur les romans d'Umberto Eco

Puisqu'on me le demande explicitement dans un commentaire de l'entrée précédente, je peux dire un mot sur les romans d'Umberto Eco et moi (ça tombe bien, parce que j'avais écrit quelque chose à ce sujet dans un forum d'anciens de l'ENS donc je n'ai en gros qu'à recopier et reformater).

J'ai énormément d'admiration pour Umberto Eco, qui avait une culture si vaste et si érudite, un sens de l'humour si subtil, et une intelligence extraordinaire. Je lui dois certainement beaucoup, comme ma fascination pour le thème du faux (et la manière dont le faux peut devenir vrai, ou influencer le vrai, la manière dont la fiction peut se retourner sur la réalité), ou encore pour les crackpots et complotistes. Je lui ai rendu hommage à différentes reprises, explicitement ou de façon cachée, dans ce blog ou ailleurs : je ne peux certainement pas tout citer, mais je mentionnerai par exemple le troisième paragraphe de ce fragment. (Beaucoup de gens se sont énervés que Dan Brown ait énormément de succès avec des livres qui sont du sous-Eco, mais étant moi-même auteur de sous-Eco je me dois de le défendre : le fait de faire du faux Eco est quelque chose d'on ne peut plus ecoïen ; et la toute petite scène que je décris est inspirée d'une — vraie — interview d'Eco que j'ai lue quelque part, où il raconte qu'il a lu le Da Vinci Code dans l'avion parce que tout le monde lui en parlait, et qu'il s'est demandé si ce Dan Brown n'était pas lui-même une sorte de complot ou de personnage imaginaire.)

Eco m'a convaincu que l'analyse littéraire et sémiotique n'est pas juste de l'invention d'interprétations imaginaires. Et c'est aussi à travers lui que j'ai découvert d'autres auteurs que j'ai beaucoup appréciés, et eux-mêmes grands manipulateurs des liens entre le vrai et le faux, je pense à Italo Calvino et Jorge Luis Borges (comme je l'écrivais il y a longtemps : quand on m'a fait remarquer qu'il y a dans Le Nom de la rose un dénommé Jorge de Burgos à la tête d'une bibliothèque en forme de labyrinthe, je me suis frappé le front en me disant rhâ, mais comment ai-je pu ne pas voir ça ?). Je pourrais aussi mentionner de Nerval et son Voyage en Orient, ou les Mille et Une Nuits.

Pourtant, mon admiration pour Umberto Eco écrivain reste modérée. Je crois qu'en bref le problème est qu'il est trop cultivé, il connaît trop bien l'Histoire, que parfois cela gêne sa capacité à inventer, à créer du nouveau, ou simplement à raconter des choses qui ne soient pas trop indigestes (pour ne pas dire, ennuyeux à en mourir) pour le commun des mortels. Il semble d'ailleurs qu'il le fasse un peu exprès : j'avais lu quelque part qu'il rendait parfois le début de ses romans délibérément ardu pour perdre tout de suite les lecteurs qui ne s'accrocheront pas jusqu'au bout. Je me suis toujours accroché jusqu'au bout, mais je n'ai pas toujours été emballé. Voilà ce que j'ai pensé de chacun de ses romans :

Le Nom de la Rose
Je me souviens d'avoir énormément aimé, mais mon souvenir est aussi un peu lointain, donc je ne peux pas en dire beaucoup plus, d'autant que je suis influencé par le film (que j'ai dû voir trois ou quatre fois). L'intrigue policière, en tout cas, marche bien, l'ambiance du Moyen-Âge et de ses débats théologiques est très bien rendue, et le lien entre les deux n'est pas du tout mal fait (l'un n'est pas juste un prétexte pour l'autre).
Le Pendule de Foucault
Il y a des idées que je trouve absolument géniales (la manière dont la théorie du complot est démontée mais revient quand même mordre ses auteurs ; et aussi plein de digressions qui sont à mourir de rire), mais l'ensemble est incroyablement brouillon, et franchement beaucoup trop long. Je recommande de le lire en diagonale : dès qu'on trouve que c'est ennuyeux, surtout vers le milieu du livre, sauter ou lire en pointillés jusqu'à la fin du chapitre, on ratera probablement peu de choses importantes.
L'Île du jour d'avant
J'ai trouvé celui-là, il faut le dire, carrément chiant. Quelques idées intéressantes, une discussion très instructive sur le problème de la détermination des longitudes en mer (j'ai appris des choses sur l'histoire des sciences, c'est sûr), les passages « politiques » (avec Richelieu et Mazarin) sont amusants, mais l'intrigue-cadre est quasi inexistante, et les digressions philosophiques interminables m'ont semblé vraiment pénibles.
Baudolino
C'est mon préféré (quoique même dans celui-là le récit du voyage fantastique vers l'Orient me semble trop long et pas très intéressant). La manière dont Eco arrive à placer Baudolino à l'origine de quantité de légendes ou de faits historiques est vraiment extraordinaire, et en plus il y a une histoire « policière » dont j'ai maintenant oublié le fin mot mais que j'avais trouvée aussi bonne que dans Le Nom de la Rose. (J'en avais fait une critique plus longue ici sur ce blog.)
La Mystérieuse Flamme de la Reine Loana
Sans doute très intéressant pour les Italiens de la génération d'Eco, mais pas vraiment pour moi, à qui au moins 90% de ce qu'il racontait n'évoquait strictement rien. L'intrigue-cadre est très bien, mais trop fine pour un livre aussi épais si on ne s'intéresse pas à tout ce qui est raconté à côté.
Le Cimetière de Prague
Extrêmement bien écrit et construit, mais je crois qu'Eco est tombé dans le piège de faire trop de recherches historiques qui, du coup, l'ont empêché d'inventer assez de choses pour faire une histoire vraiment palpitante : en refusant de s'écarter de la réalité, il se retrouve avec un personnage principal qui ne peut que côtoyer plein d'événements célèbres sans, finalement, jouer un rôle proéminant dedans (en tout cas, rien de comparable avec ce qui se passe dans Baudolino).
Numéro Zéro
Il est tellement court qu'on aura du mal à trouver qu'il y a des passages ennuyeux (il faut avouer qu'on en trouve dans tous les autres), mais finalement je n'ai pas été emballé par l'intrigue, qui m'a semblé faible.

Incontestablement, Eco avait une culture hors du commun, donc en écrivant sept romans liés à à peu près sept périodes historiques différentes (Le Pendule de Foucault n'est pas vraiment bien situé, il fait le lien entre plein de choses à la fois), il est toujours incroyablement bien renseigné, non seulement sur l'histoire, mais aussi sur l'historiographie (il y a plein de méta dans ses livres, où on parle des erreurs que les différentes époques faisaient sur les autres époques) ; et on trouve dans tous ses romans ce fameux thème du faux, de la falsification, de l'imposture, et plus largement de la confusion et du complot qui traverse les époques. Mais pour intéresser le lecteur, ou en tout cas pour m'intéresser moi, un romancier doit avoir une intrigue qui serve à autre chose qu'à donner un prétexte, aussi savant soit-il, à parler de telle ou telle époque : et plus d'une fois il m'a semblé que l'imagination d'Eco se laissait dévorer par sa culture.

Si on veut l'humour d'Eco, il vaut peut-être mieux le chercher dans ses petits textes comme dans le recueil Comment voyager avec un saumon.

Et si on veut sa science, il y a un livre que j'aime énormément, c'est Six promenades dans les bois du roman ou d'ailleurs (je crois que la VO est en anglais : Six Walks in the Fictional Woods, c'est tiré de leçons qu'il a données à Harvard au début des années '90). Parce que là, au lieu que sa culture déborde dans tous les sens comme dans une oeuvre de fiction, il la canalise sous forme d'un enseignement, et c'est vraiment passionnant. Et pourtant je n'aime pas trop la critique littéraire en général.

(vendredi)

Quelques réflexions décousues au sujet d'Isaac Asimov et de Frank Herbert

J'avais écrit il y a quelques mois une petite introspection sur l'influence que la lecture du Seigneur des Anneaux de Tolkien a eue sur moi. Je voudrais dire quelque chose de semblable au sujet de l'œuvre d'Isaac Asimov, sauf que j'écris ceci surtout pour me détendre après trop de temps passé à préparer des cours, donc je ne vais pas être très cohérent ni très systématique dans mon analyse.

Ce qui me motive à en parler, c'est que je viens de relire la trilogie centrale de Fondation (soit : Foundation, Foundation and Empire et Second Foundation). Mais ce qui me pose une difficulté pour en parler, c'est que je n'arrive pas à me rappeler quand je l'ai lue pour la première fois. (Il m'arrive d'écrire la date en première page quand j'achète un livre, mais là je ne l'ai pas fait.) Mon édition de Foundation and Empire prétend dater de 1994, et c'est bizarre parce que j'ai un souvenir assez net de l'avoir lu pendant que j'étais aux États-Unis avec mes parents à l'été 1993 (le souvenir est assez net : je me revois lisant des passages précis du livre dans un hôtel dans les Rocheuses, et je sais avec certitude que ce je suis allé dans l'Ouest des États-Unis en 1993 et jamais depuis), donc peut-être que je suis tombé dans une faille spatio-temporelle ou peut-être que j'ai encore un cas de souvenirs bizarrement faussés. Mais bon, ça doit bien être vers 1993–1995 (j'ai des textes écrits vers 1994 qui sont manifestement fortement inspirés de Foundation).

Je ne me rappelle pas non plus ce que j'ai pensé en lisant ces livres pour la première fois, ni ce qui m'a poussé à les lire. Bizarrement, je me rappelle ce que j'ai pensé en voyant les couvertures pour la première fois : c'était dans une librairie à Londres, probablement autour du moment où j'ai lu The Hitch-Hiker's Guide to the Galaxy de Douglas Adams, et j'ai vu l'intégrale de la série Foundation (intégrale qui faisait, à l'époque, six volumes puisque c'était avant que paraisse Forward the Foundation), l'édition était celle, par Grafton je crois, dont la couverture porte les jolis dessins de Tim White qui n'ont absolument rien à voir avec le contenu des livres mais qui, dans mon esprit, sont restés inextricablement liés à eux. (D'ailleurs, mon sens de la symétrie est agacé par le fait que quand j'ai, plus tard, acheté tous les livres de la série, ils n'étaient pas dans la même édition.) Je me souviens avoir pensé, ouhlà, six volumes, je ne lirai jamais un truc pareil ; en même temps que, malgré moi, j'ai dû commencer à me demander ce qu'il pouvait y avoir dedans (et à m'en construire une représentation bizarre, comme je le disais au sujet de Tolkien), parce que j'aimais bien les titres et les illustrations. Toujours est-il que je ne sais absolument plus ce qui m'a poussé, finalement, à essayer quand même de les lire.

Pour ceux qui n'ont pas lu ces œuvres, disons rapidement (et presque sans spoiler) qu'il s'agit d'une histoire de science-fiction qui se passe au moment du déclin et de la chute d'un empire galactique (peuplé d'humains) qui a régné sur toute la galaxie pendant environ 12000 ans ; un mathématicien nommé Hari Seldon développe une science appelée psychohistoire, au croisement de la psychologie, de la sociologie, de l'histoire et de la physique statistique, qui permet de modéliser le comportement des grands ensembles d'individus et donc d'en prédire l'évolution : grâce à cette science, il prédit la chute de l'empire galactique et un interrègne chaotique qui doit durer 30000 ans, mais qu'il trouve le moyen (le Plan Seldon) de raccourcir à seulement 1000 ans en établissant une Fondation au bord de la galaxie, qui portera les graines à l'établissement d'un second empire galactique. Les trois volumes centraux que je viens de relire (Foundation, Foundation and Empire et Second Foundation) racontent le début de l'histoire de cette Fondation, ses démêlés avec ses voisins, et la recherche de la plus mystérieuse Seconde Fondation dont on sait seulement qu'elle a été établie à l'autre bout de la galaxie et dont le rôle n'est pas clair (je n'en dirai pas plus pour ne pas spoiler, parce qu'il y a beaucoup de coups de théâtre à ce sujet). Les deux volumes qui suivent dans l'histoire interne et qui ont été publiés longtemps plus tard (Foundation's Edge et Foundation and Earth) prennent un point de vue très différent sur le but ultime de la Fondation, évoquent la recherche de la Terre, la planète sur laquelle l'humanité est née, et concluent le cycle un peu en queue de poisson. Encore plus tard, Asimov a écrit deux romans supplémentaires (Prelude to Foundation et Forward the Foundation) dont l'action se déroule avant Foundation et qui ont pour thème le développement de la psychohistoire, sur la planète qui sert de capitale à l'Empire, Trantor, avant l'établissement de la Fondation.

J'ai énormément aimé les trois volumes centraux. Sans doute l'idée même de la psychohistoire me plaisait-elle, et/ou le fait d'avoir un héros mathématicien. Même s'il faut admettre que la psychohistoire ne tient pas vraiment debout dès qu'on y réfléchit un peu, même dans la logique interne des livres (il y a vraiment trop d'éléments dus au hasard, et vraiment trop de prédictions qui sont faites avec une précision complètement cinglée) ; et même s'il est clair qu'Asimov a une idée assez fantaisiste des mathématiques (il imagine plein de formules compliquées : or même si une science comme la psychohistoire devait exister, ce serait certainement surtout plein de calculs numériques).

Mais plus encore que la psychohistoire et le héros mathématicien, je crois que j'étais fasciné par l'empire galactique, qu'on ne fait qu'entre-apercevoir dans Foundation et Foundation and Empire, et dont la chute m'avait causé un certain chagrin, toute prédite qu'elle était. Je crois que, comme Asimov et comme tant d'autres gens, je suis hanté par l'idée (sans doute plus l'idée fantasmée que la réalité) de l'empire romain, et surtout de son déclin et de sa chute, notamment à travers l'influence de l'œuvre célèbre de Gibbon (que, un peu comme le cycle de Foundation, j'ai toujours regardée en me disant, ouhlà, c'est trop long, je ne lirai jamais un truc pareil). Ce qui est certain, c'est qu'énormément des textes que j'ai écrits, que ce soit de la science-fiction ou d'autres genres de fantastique, tournent autour du thème de l'empire et de l'empereur, pas juste des royaumes et des rois mais bien des empires et des empereurs : c'est une idée qui m'obsède presque (artistiquement, je précise : je n'ai certainement pas de sympathie politique pour cette forme d'organisation de l'État !). Et puis, il y a la planète-capitale, Trantor, qui est elle aussi assez fascinante : qu'Asimov réussit à rendre fascinante, lui qui a manifestement une sainte horreur des descriptions. Et il y a spécifiquement l'empereur Cléon I dans Prelude to Foundation et Forward the Foundation, que je trouve extraordinairement attachant pour un personnage finalement assez secondaire.

Et enfin, il y a les coups de théâtre. J'ai déjà dit que j'étais un grand fan des coups de théâtre, mais la trilogie centrale de Fondation est un orgasme théâtral multiple. La fin de chacune des deux parties de Second Foundation est presque une caricature du coup de théâtre à répétition, c'est du Agatha Christie à la puissance cent. J'ai dû grandir depuis 1994, ou simplement ça marche moins bien quand il n'y a plus l'effet de surprise, parce que j'ai trouvé ça un peu exagéré à la relecture. Mais bon, c'est amusant et il y a des signes clairs qu'Asimov ne se prend pas (complètement) au sérieux.

La trilogie centrale de Fondation m'a énormément plu. Les deux livres qui suivent (Foundation's Edge et Foundation and Earth) m'ont, en revanche, beaucoup déçu : j'ai cru qu'Asimov avait perdu son talent pour le calcul politique sophistiqué qui est à la base de la psychohistoire et des coups de théâtre du Plan Seldon ; j'ai été agacé par sa façon d'essayer de recoller artificiellement ses histoires de robots avec le monde de Fondation ; et surtout, je me suis senti trahi par une réinterprétation, pour ne pas dire un abandon, du Plan Seldon (je n'en dirai pas plus pour ne pas spoiler). Les deux livres qui ont été écrits encore après, mais qui servent de préquelles dans la chronologie interne (Prelude to Foundation et surtout Forward the Foundation) m'ont partiellement réconcilié avec lui : même s'il y avait encore à mon goût un peu trop d'histoires autour des robots, ou de la possible existence de robots, au moins l'histoire de Hari Seldon est-elle intéressante et assez pleine de rebondissements et de calculs politiques intelligents.

J'ai lu beaucoup d'autres œuvres d'Asimov, donc je ne vais pas faire le catalogue complet. La trilogie de l'Empire (The Currents of Space, le mal-aimé Tyrann/The Stars like Dust, et Pebble in the Sky) m'a également bien plu ; comme beaucoup de ses nouvelles (je pense par exemple à Profession), et d'autres de ses romans (je mentionnerai juste The End of Eternity, pour une approche originale du voyage temporel et la manière dont on passe tout le roman à se demander où il veut en venir avant un dénouement assez épatant).

Mais je n'ai jamais été tellement emballé par ce qui fait sans doute le plus la célébrité d'Asimov, auquel le OED attribue la paternité du mot robotics : les histoires de robots, et les fameuses trois lois. Certes, l'exploration de toutes les façons de contourner ces lois, de les annuler, de les réinterpréter, etc., est amusante, mais une chose que j'ai du mal à comprendre, c'est qu'Asimov n'ait jamais vraiment fait le lien entre robots et ordinateurs : il est parfois question d'ordinateurs dans ses œuvres, ce sont généralement des machines monstrueuses, souvent appelées Multivac, et en tout cas ontologiquement différentes des robots — on se demande comment il a pu ne pas identifier un robot à un ordinateur sur pattes.

Bref, ce qui m'intéressait le plus, moi (au moins il y a 20–25 ans : peut-être plus tant maintenant), c'était les histoires d'empires galactiques, et les manœuvres politiques qui allaient avec. J'ai passé un certain temps à écrire du sous-sous-Asimov qui en est presque un plagiat, et de qualité abominable : pièce à conviction nº1, pièce à conviction nº2, pièce à conviction nº3. Je n'ai appris que récemment l'existence d'histoires qui ne sont pas d'Asimov mais autorisés par lui, spécifiquement Foundation's Friends, dont il faudra que je voie ce que ça vaut.

🌠

Mais j'en viens à un autre auteur : Frank Herbert. Parce qu'au rayon des complots politiques dans des empires galactiques dans des sagas de livres de science-fiction, il était difficile d'échapper à la série Dune. Et là, je n'ai pas du tout aimé. Pourtant, je partais d'un bon a priori : tellement bon, même, que j'ai lu deux volumes et demi de la saga, et encore un bout du quatrième, avant de me rendre compte que je détestais ce gloubi-boulga mystique.

Pourtant, si on en juge par ce que j'ai écrit avant, j'aurais aimer Dune, et en tout cas les parallèles avec Fondation sont frappantes. C'est de la science-fiction qui se passe autour de 10⁴ années dans le futur. Il y a un empire avec un empereur à la tête. Il y a quelqu'un qui a vaguement le pouvoir de prédire l'avenir, et qui s'inquiète pour ce que deviendra l'Humanité. Il y a des luttes de pouvoir compliquées et des complots dans tous les sens. Il y a des gens qui ont une sorte de pouvoir mental bizarre et qui ont un Plan à accomplir. Il y a quelqu'un qui a une sorte de super-pouvoir d'origine probablement génétique. Et il n'y a pas de robots parce qu'ils ont disparu, sauf peut-être à la fin, dans une certaine mesure. La fin, d'ailleurs, n'est pas vraiment une fin, et d'autres auteurs ont essayé d'en écrire une. (Je suis sûr que des gens un peu doués pour l'exercice de style pourraient écrire un petit résumé qui fonctionne à la fois pour Fondation et pour Dune. Oui, ceci est un défi. 😉) Sur un point plus superficiels, les deux ouvrent leurs chapitres par des citations fictives. Les deux parsèment leurs histoires de coups de théâtre et de rebondissements. Et de façon plus profonde, les deux posent des problèmes éthiques intéressants sur ce que doit être l'avenir idéal de l'Humanité et surtout qui est en droit d'en décider et ce qu'on a le droit de faire pour que cet avenir s'accomplisse ; et comment il est possible d'échapper à la prescience. Les deux posent un regard ambigu sur la religion (et peut-être aussi le commerce) comme moyen de contrôle des masses. Je suppose que Herbert avait lu Asimov, et qu'Asimov a lu Herbert pour la suite. Je suis étonné de ne pas trouver facilement sur Google plus de gens dressant des comparaisons entre deux sagas pourtant toutes deux immensément populaires : je ne trouve en fait qu'un seul article vaguement sérieux sur la question, John L. Grigsby, Asimov's Foundation Trilogy and Herbert's Dune Trilogy: A Vision Reversed, Science-Fiction Studies 8 (1981) 149–155, et il n'est pas bien profond.

Bref, si j'ai beaucoup aimé Fondation et pas du tout Dune, c'est qu'il faut creuser un peu plus profondément que ces ressemblances.

Je peux trouver des raisons superficielles pour lesquelles je n'aime pas Dune. Herbert écrit mal : je veux dire, son style est encore plus ridiculement pompeux que le mien, et ce n'est pas peu dire. Il ne se passe quasiment rien dans des volumes pourtant interminables à part des conversations complètement plates, des digressions qui ne servent à rien, et surtout du délire, beaucoup de délire, religio-philosophique. Ses coups de théâtre qui sont censés être des surprises sont tellement transparents qu'il est impossible d'être vraiment surpris. Ses personnages n'ont aucune profondeur psychologique, ils sont tous des caricatures d'eux-mêmes : Dune me fait penser de ce point de vue-là à une classe d'école primaire qui aurait décidé de représenter l'Électre d'Euripide et qui jouerait les rôles avec la crédibilité qu'on imagine. L'intrigue est totalement artificielle, tous les éléments sont complètement parachutés. Et le monde lui-même n'a aucune crédibilité (des hommes-calculateurs ? complètement grotesque ; tout le monde qui aurait le même livre religieux ? absurde ; des gens qui seraient conditionnés à ceci ou cela ? n'importe quoi ; des gens qui peuvent retrouver les mémoires de leurs ancêtres ? crétin et éculé ; une guerre sainte contre toute forme d'ordinateur qui aurait eu tellement de succès ? pas crédible une seule seconde). Enfin, Herbert semble avoir complètement perdu de vue la première moitié du mot science-fiction.

…Mais tout ça, ce ne sont que des raisons superficielles, et assez largement de mauvaise foi. Je pourrais certainement trouver des raisons analogues de ne pas aimer Fondation si je cherchais un peu. En tout cas, j'ai certainement des choses à lui reprocher : le style d'Asimov, s'il est plus naturel, n'est pas franchement plus brillant que celui de Herbert ; à part dans les préquelles, ses personnages n'ont guère plus d'épaisseur psychologique, ce qui est peut-être encore plus critiquable quand il est censément question de psychologie ; il y a aussi beaucoup de choses totalement parachutées, et les coups de théâtre que j'aime tellement sont totalement tarabiscotés. Et pour un reproche plus spécifique à Asimov : il n'y a aucune description de rien du tout, si bien qu'on a l'impression de lire une histoire racontée avec des personnages de xkcd, on ne sait pas à quoi ressemble quelque personnage que ce soit sauf Hari Seldon, ni quelque planète que ce soit sauf Trantor. Bordel, Asimov, c'est l'espace !, tu pouvais nous faire rêver avec des belles images. Pourtant, je lui pardonne tout ça et plus.

La vraie raison pour laquelle je n'aime pas du tout Dune et j'aime Fondation doit se chercher en moi et pas dans les œuvres elles-mêmes.

Je crois que quand je lis du Asimov, je ressens une profonde empathie pour l'auteur. Asimov n'est pas doué pour faire ressentir la psychologie de ses personnages, mais il est doué pour faire ressentir la sienne : ce n'est pas facile à expliquer, mais on sent parfaitement, en le lisant, que c'était un homme à la fois profondément bon, avenant, profondément rationnel, humaniste, et ayant une foi positiviste dans le Progrès telle que ce que j'évoquais dans cette entrée. Et les différents textes de non-fiction que j'ai lus de lui me confortent dans ce jugement (ne serait-ce, d'ailleurs, que son jugement sur l'attitude de Tolkien que je mentionnais précédemment). D'ailleurs, on a donné à Asimov le surnom de the Good Doctor. Sa forme particulière, non pas inconditionnelle mais néanmoins rassurante, d'optimisme, transparaît dans le fait que même les personnages « méchants » de ses œuvres, quand ils ne sont pas simplement stupides, restent rationnels, compréhensibles, et donnent l'impression de jouer le rôle du méchant parce qu'il faut bien que quelqu'un le joue. Le lecteur un peu candide que je suis aime bien ce genre de clarté.

Herbert, c'est tout le contraire. Enfin, je ne sais pas du tout quel genre de personne était Frank Herbert lui-même — j'ose espérer qu'il ne transparaît pas personnellement comme Asimov le fait — mais je parle de ce qu'il écrit. L'univers qu'il nous présente est intellectuellement, moralement et esthétiquement répugnant, et tous les personnages qui l'habitent le sont aussi. Si les « méchants » sont des méchants d'opérette gratuitement méchants, les « gentils » sont cinglés et/ou incompréhensibles, et à peine moins condamnables moralement. Et tous sont d'une arrogance insupportable. Dès les premières scènes, j'ai juste envie de foutre une baffe aux prétentieuses Bene gesserit avec leurs projets politiques et eugénistes à la con, et ça ne s'améliore pas par la suite. Et ces gens sont enfermés dans un univers aux coutumes odieuses à en vomir : il n'y a pas un seul aspect de cette société qui ne donne pas profondément la nausée — son système de classes sociales profondément barbare, ses interdits religieux débiles, ses règles arbitraires révoltantes, ses clans, castes et corporations pourris, sa mystique puante, son obsession pour la lignée génétique. Et tout le monde est à la même sauce, des puissantes familles nobles (qui ont chacune leurs propres règles crétines) aux pauvres Fremen en passant par les manipulatrices Bene gesserit. Comme si tout ceci n'était pas assez immonde, on en ajoute une couche dans l'esthétique, comme avec les navigateurs (certes, ces images viennent essentiellement du film de David Lynch, mais il est clair dans les romans qu'ils ne sont pas jolis-jolis à voir).

Alors on aura beau jeu de me dire que je suis un homme de ma société et qu'il est normal que j'en trouve une autre répugnante : que c'est le signe que Herbert a réussi à me dépayser. Je n'en suis pas convaincu : quand je lis des descriptions historiques réelles d'autres civilisations, j'atteins rarement un tel niveau de révulsion. Mais en tout état de cause, je ne prétends pas critiquer ici Dune, juste expliquer l'effet produit sur moi : j'ai besoin de voir un rayon de lumière de temps en temps (le monde et la société qui nous entourent sont assez déprimants, justement, je ne m'identifie pas à eux, et je ne tiens pas à lire des livres qui en rajoutent une couche en présentant largement pire).

Mais en fait, le point important est un peu différent : je peux apprécier une description d'un monde horrible à condition qu'il y ait des personnages qui se révoltent contre lui, avec lesquels je puisse m'identifier au moins un peu (même si, in fine, leur révolte échoue). Tout César doit avoir son Casca. J'ai bien apprécié, par exemple, The Handmaid's Tale de Margaret Atwood, qui décrit pourtant un monde de science-fiction comparablement horrible à celui de Dune. Chez Asimov, si une situation est absurde, quelqu'un dira inévitablement c'est absurde ! ; le monde ne sera pas toujours démocratique, mais il y aura toujours des démocrates, par exemple Ebling Mis dans Foundation and Empire, qui se comporte exactement comme j'aimerais me comporter dans certaines circonstances. Mais chez Herbert, le niveau de soumission à l'absurdité est hallucinant : il me semble qu'il n'y a pas un seul moment où quelqu'un dit ces règles sont vraiment connes, on devrait les enfreindre, les combattre ou les contourner ou même quel dommage que ces règles existent, ou, ce qui serait vraiment jubilatoire, je vais foutre une baffe à cette bande de connards imbus d'eux-mêmes. Hélas non : il y a bien des groupes qui combattent des éléments répugnants de cet univers où tout est répugnant, mais ce sont toujours pour les « mauvaises » raisons, par exemple pour leur pouvoir personnel, et en tout cas pour remplacer quelque chose de pourri par quelque chose d'aussi pourri.

(Friday)

Gratuitous Literary Fragment #152 (a council of wizards)

I was the last to arrive and, as our host ushered me in his office and announced we may now begin, with just a shade of impatience in his voice, I considered the three men and three women who were to be my co-conspirators of sorts. Lord Ardemond was known to me, of course, as well as the elderly lady seated at his right, whom I recognized as our Dean of Magic, Anastasia Aldert. As I took my place I was rapidly introduced to Aron Azoulay, experimental wizard from the University of Tel-Aviv, a big burly man with an enormous black beard; Adelheid Aloysius, mathematician from Göttingen, a tall woman with slender features; Anatole Auber, theoretical mage from the École Normale Supérieure of Paris, whose rotund and dark-skinned face looked so boyish that almost I mistook him for a child; and Ambrosia Allegri, enchantress from the Alma Mater Studiorum, elegant and intimidating.

You will all be wondering to what end I gathered you here in connection with the recent events. Let me cut to the chase so we can get the disbelief out of the way as soon as possible: I need your help in investigating what I believe may be a case of physics.

The last word obviously caused the stir that Lord Ardemond was expecting. The Israeli wizard laughed incredulously. The German mathematician raised her eyebrows in a calculated air of disapproval, but said nothing. The French mage raised his hand in what I assumed was an expression of protest. The Italian enchantress quoted Shakespeare, though I couldn't understand the relevance of the line: We are such stuff as dreams are made on; and our little life is rounded with a sleep. Dame Albert did not react, but I assume she had heard the speech beforehand. As for myself, I imagine my dubiousness showed in how I looked at each of them in turn. Ardemond made a conciliatory gesture.

I understand your puzzlement, he said, but I assure you, I would not waste your time with a sorry joke. I speak of physics in earnest.

Auber: I don't know why I have to say this, Lord Ardemond, but we are all thinking the same: there is no such thing as physics. Outside of children's books and cheap illusions, that is.

Allegri: Isaac Newton believed in the stuff, though.

Myself: Isaac Newton also thought he was a theologian beyond compare. Who knows, in a different world, he could have become the Primate of All England. So yes, the great alchemist may have dabbled in physics, but the fact that he was a genius in one domain does not make him a master of all.

Azoulay: During the Cold War, the United States and the Soviet Union probably had teams of magicians trying to come up with random stuff to get an edge over the other's stockpile of Armageddon spells, but it seems nothing came out of it except more destructive spells.

Aloysius: At the risk of stating the obvious, the very idea of physics does not even make any sense. The world obeys precise mathematical rules, as we all know. Magic leaves no room for anything else: what follows those rules is known, what is outside them is nonexistent.

Allegri: With due respect, the reproduction of rabbits does not follow any known rules, but rabbits persist in trying to multiply even when we do not conjure them into existence.

Aldert: Not to quibble, but the reproduction of rabbits would, I believe, be the province of biology, not physics.

Azoulay: You can call these fictional fields however you like, that doesn't make them any more real. I believe role-playing games like Advanced Poisons & Pythons have a discipline called chemistry as well, full of whimsical names for substances like praseodymium or thulium.

Auber: A good point. We have a perfectly good understanding of how the eight elements (Spirit, Life, Macrocosm, Fire, Air, Water, Earth and Time) relate to each other, and how they combine to make all the universe. This is not to say that, say, sulfur and mercury don't exist — of course they do — but it doesn't make sense to try to coerce them into being elements as the ancients might have thought, and as keeps popping up in so-called chemistry. There is simply no room for more elements or for a different way of arranging them: this would ruin all the beautiful symmetry of the eight that exist. Anyone who understands E8 cannot believe in chemistry.

Aldert: Physics could conceivably have its own set of rules, perhaps equally symmetric and mathematically elegant. One could even imagine those of physics and magic to be each interpretable in the other.

Aloysius: One is reminded of the famous quip by Arthur C. Clarke, any sufficiently advanced magic is indistinguishable from technology, I think it goes.

Azoulay: Indeed, who would have thought, a mere half-century ago, that we would be sending words, images and even spells across the planet almost instantly using the World Wide Weave? But why are we having this conversation?

Lord Ardemond let out an audible sigh.

Je reconnais que je rejoue-là un peu la même chose que dans ce fragment précédent (et puis toujours celui-ci), en même temps qu'il s'agit d'une sorte de continuation de celui-là et d'une exploration de ces thèmes : bref, j'aurais besoin de me renouveler. D'un autre côté, c'est amusant à écrire, et je n'exclus pas de reprendre ces idées sous la forme d'un texte un peu plus long et plus construit. Sinon, les noms des personnages sont une référence à un de mes premiers fragments.

(vendredi)

Sur l'Arénaire d'Archimède, et les grands nombres

J'ai déjà évoquéplusieurs reprises) ma fascination pour les grands nombres, et même la raison pour laquelle ils me fascinent (cette entrée parle d'ordinaux, mais les très grands nombres entiers sont fabriqués à partir d'ordinaux par des mécanismes d'écrasement et en tout cas l'attrait psychologique est le même), et aussi les objections que j'ai à la position philosophique selon laquelle ils n'ont pas de sens.

Maintenant je voudrais dire un mot d'histoire, pour parler d'un texte d'Archimède intitulé Ψαμμίτης, ce qu'on traduit en français par l'Arénaire. (Enfin, en français, c'est vite dit : c'est surtout une transcription de la traduction latine (H)arenarius ; le TLF définit le substantif un arénaire comme carrière souterraine d'où l'on extrait le sable ou la pouzzolane ou gladiateur qui combattait dans l'arène ou encore, une arénaire comme carrière de sable. Bref, c'est un mot jamais utilisé qui peut apparemment signifier n'importe quoi ayant un rapport avec le sable. Et ça semble être à peu près le cas du mot grec d'origine, donc pourquoi pas — mais je ne sais pas si le titre est d'Archimède ou si c'est une description plus tardive.) En anglais, on appelle ce texte The Sand Reckoner, le compteur de grains de sable, ce qui est plus descriptif.

Il s'agit d'un texte assez court (une dizaine de pages) dans lequel Archimède cherche à démontrer que le nombre de grains de sable dans l'Univers est fini. Je suppose que le terme infini (enfin, ἄπειρος, ce qu'il vaut peut-être mieux traduire par illimité) était utilisé de façon assez floue, pour dire plus grand qu'on ne peut le concevoir ou le décrire Un peu comme dans le titre d'un célèbre livre de vulgarisation scientifique de George Gamow, One, Two, Three… Infinity (que mon papa m'a lu quand j'étais petit, et qui a beaucoup contribué à mon éveil scientifique), c'est une référence au fait que certains peuples humains, comme beaucoup animaux, savent compter « un », « deux », « trois » et « beaucoup ». (Donc l'idée c'est que si une cane a quatre canetons et qu'il y en a un qui disparaît, elle le remarque parce que ça passe de « beaucoup » à « trois », mais si elle en a cinq au début, elle ne remarque pas de différence, parce que « beaucoup » égale « beaucoup ».) Bref, la thèse d'Archimède c'est que non seulement le nombre de grains de sables est fini, mais qu'on peut en donner un majorant tout à fait explicite.

Pour ceux qui veulent lire le texte lui-même, j'en ai trouvé plusieurs versions en ligne : ici un scan d'une traduction française tout à fait ancienne mais assez littérale et amusante à lire, ici un scan d'une édition moderne du texte grec original, ici un scan d'une édition plus ancienne du texte grec original accompagné d'une traduction latine (je suis sûr que ça aide beaucoup de gens, ça, la traduction latine), ici un scan d'une traduction/paraphrase/analyse anglaise, ici une version retapée en TeX du texte grec, ici une traduction anglaise suivie d'une analyse, ici une traduction française qui coïncide sans doute avec la première que j'ai liée, et ici une traduction intercalée de notes et de commentaires. On peut aussi chercher le début du texte dans Google.

Je ne suis pas historien, même pas historien des sciences, et je ne suis pas terriblement habitué à lire des textes « anciens », même si ça m'arrive. (J'ai lu les Éléments d'Euclide, par exemple, et un certain nombre de textes d'Euler, Lagrange, Gauß et Galois, mais pas énormément, et encore, c'était plus par curiosité qu'autre chose ; mes lectures véritablement mathématiques commencent plutôt avec Hilbert. Comme j'aime bien le faire remarquer, un matheux peut être spécialiste de la théorie de Galois sans jamais de sa vie avoir lu une ligne de Galois, alors qu'il est sans doute plus difficile pour un philosophe d'être spécialiste de la métaphysique de Kant et de ne jamais avoir ouvert un livre de Kant ; on peut sans doute en tirer des conclusions sur la différence d'approche entre domaines, notamment dans le rapport à l'Histoire du domaine.) Je ne peux donc pas vraiment replacer ce texte dans son contexte historique. Mais il me semble qu'il est à la fois extrêmement moderne et fécond en idées modernes, et pourtant bizarrement ancien par certains aspects.

Parmi les choses que je trouve très modernes dans l'Arénaire, il y a l'idée d'étudier des ordres de grandeur, et de faire des majorants, même grossiers, sur des quantités qu'on ne sait pas estimer. (Par exemple, Archimède signale que la circonférence de la Terre est estimée à 300000 stades — c'est-à-dire environ 60000km dans nos unités modernes, la vraie valeur étant 40000km — mais pour que personne ne mette en doute sa démonstration, il rajoute un facteur 10 et la majore donc par 3000000 stades.) Il y a l'utilisation des puissances de 10 (je vais y revenir) avec le fait que 10a×10b=10a+b, et il y a les grands nombres qu'il introduit.

Il faut se rappeler que les Grecs anciens avaient une notation particulièrement pourrie pour les nombres : ils utilisaient 27 symboles (les 24 lettres de l'alphabet plus 3 lettres anciennes), pour les unités de 1 à 9, les dizaines de 10 à 90 et les centaines de 100 à 900 ; puis ils reprenaient les symboles des unités pour les milliers de 1000 à 9000 avec un modificateur (quelque chose comme Ͳ) ; au-delà, les choses devenaient embrouillées : 10000 s'appelait une myriade, et on comptait les myriades et les unités séparément. Donc, en gros, le système permettait (mal) de noter les nombres jusqu'à une myriade de myriade, soit 10⁸, ou plutôt jusqu'à 99 999 999.

Archimède propose pour les grands nombres la terminologie suivante, qu'il avait apparemment exposée dans un texte antérieur (Principes, adressé à un certain Zeuxippe), lequel a été perdu, donc c'est une chance qu'il la réexplique — d'autant qu'il va beaucoup plus loin que ce dont il a besoin pour compter les grains de sable.

Les nombres de 1 à une myriade de myriade (10↑8) s'appelleront, nous propose Archimède, nombres premiers (rien à voir avec les nombres premiers en arithmétique) ; ensuite, les multiples du plus grand des nombres premiers (10↑8) s'appellent nombres seconds, jusqu'à une myriade de myriade de ceux-ci, c'est-à-dire (10↑8)↑2 = 10↑16 ; puis les multiples de ce nombre-là s'appellent nombres troisièmes, jusqu'à (10↑8)↑3 = 10↑24, et ainsi de suite jusqu'aux nombres myriade-de-myriadièmes, le plus grand desquels est donc (10↑8)↑(10↑8) = 10↑(8×10⁸). Ensuite, Archimède suggère qu'on peut aller encore plus loin, même s'il n'en aura aucun besoin pour compter les grains de sable (et il s'y prend un peu bizarrement) : il appelle nombres de la première période tous les nombres que je viens de décrire (jusqu'à 10↑(8×10↑8) donc), et il reprend les multiples de ce nombre-là pour former les nombres premiers de la seconde période (de 10↑(8×10↑8) à une myriade de myriade de fois ça, c'est-à-dire 10↑(8×10↑8+8)), puis il appelle seconds de la seconde période les multiples du plus grand nombre premier de la seconde période (de 10↑(8×10↑8+8) à 10↑(8×10↑8+16)), et ainsi de suite jusqu'aux nombres myriade-de-myriadièmes de la seconde période (qui se termine avec 10↑(16×10↑8)) ; et Archimède signale qu'on pourrait aller jusqu'à une myriade de myriade de périodes (le dernier nombre qu'il évoque est donc 10↑(8×10↑16)).

Pour dire les choses autrement, et c'est d'ailleurs ce qu'ajoute Archimède, si on compte juste les puissances de 10, les huit premières (=la première octade) appartiennent à ce qu'Archimède appelle les nombres premiers, les huit suivantes aux nombres seconds, etc., et ensemble les 800 000 000 premières (puissances de dix, c'est-à-dire une myriade de myriade d'octades) appartiennent à la première période, les 800 000 000 suivantes à la seconde période, et ainsi de suite jusqu'à 8×10↑16 = 80 000 000 000 000 000 (je parle toujours de puissances de dix) qui délimitent l'étendue des nombres considérés par Archimède. Jusqu'à 10↑(8×10↑16), donc (pour les non-mathématiciens, cela veut dire que le dernier nombre considéré par Archimède est un 1 suivi de 80 000 000 000 000 000 zéros).

Ce nombre est assez remarquablement grand, et il semble que personne, mathématicien ou autre, n'ait considéré ou décrit un nombre supérieur à 10↑(8×10↑16) jusqu'au XXe siècle. (On me souffle : jusqu'au livre de Hardy de 1910, Orders of Infinity — mais si quelqu'un trouve un exemple antérieur, ça m'intéresse. Ce texte d'introduction à la googologie suggère que Diophante a pu évoquer le nombre 10↑(10↑(10↑(10↑10))), mais je n'arrive pas à confirmer.)

Par ailleurs, le système d'écriture des nombres suggéré par Archimède n'est pas loin d'être un système positionnel (de base 10⁸) ; ceci dit, c'est un peu difficile à savoir parce qu'il ne mentionne pas explicitement, par exemple, qu'un nombre peut s'écrire comme la somme d'un nombre premier et d'un nombre second et d'un nombre troisième, etc. (ce qui serait véritablement l'écriture en base 10⁸). Peut-être de telles considérations étaient-elles dans les Principes qui ont été perdus.

Archimède évoque aussi les puissances de dix (la suite géométrique commençant par 1 et dont chaque terme est dix fois le précédent) : il démontre que 10a×10b=10a+b, formulé en gros de la façon suivante : le produit de deux termes de la série sera éloigné de l'unité d'autant de termes, moins un, que les deux facteurs le sont ensemble de l'unité (le moins un vient de ce qu'Archimède ne compte pas à partir de zéro, si bien que 10↑0=1 est le premier terme de la suite géométrique des puissances de dix, 10↑1=10 est le second, et ainsi de suite).

Il y a deux choses que je trouve bizarres dans l'histoire : la première est juste bizarre, la seconde l'est moins mais est assez dommage. Ce qui est vraiment bizarre, c'est que finalement Archimède introduit deux terminologies sur les nombres, l'une à base de 10⁸ (une myriade de myriades) et l'autre à base de 10, et il passe son temps à convertir entre les deux, ce qui revient essentiellement à multiplier ou diviser par 8 (laborieusement, parce qu'il y a des ±1 dans tous les sens à cause de cette histoire de zéro), par exemple il passe du cinquante-deuxième terme de la progression des puissances de 10 (soit 10↑51) à mille unités des nombres septièmes (de la première période) (soit 1000×(10⁸)↑6). Tout ça est fondamentalement inutile, surtout pour les calculs intermédiaires, et ça rend le texte lourd à suivre. Il aurait pu se contenter de puissances de 10 ou de celles de 10⁸, ou dire une fois pour toutes qu'il peut passer de l'un à l'autre en divisant ou multipliant par 8, mais au lieu de ça il refait plein de fois des décomptes d'octades. • L'autre chose qui est dommage aux yeux du gogolologue que je suis, c'est qu'il n'a pas eu l'idée d'appliquer les exposants aux exposants, par exemple mettre dans la seconde période autant d'ordres (=nombres premiers, deuxièmes, troisièmes, etc.) qu'il y avait de nombres dans la première période, et ainsi de suite : du coup, il aurait considéré des nombres non pas comme 10↑(8×10↑16) mais comme 10↑(8×10↑(8×10↑(8×10↑(8×10↑(⋯))))) avec 10⁸ exponentiations, ce qui aurait été encore plus impressionnant et encore plus en avance sur son époque.

Mais bon, les grands nombres ne sont pas vraiment l'objet du texte (je pense qu'il en parle un peu pour se vanter — et il a raison — d'avoir introduit des nombres qui dépassent considérablement le nombre de grains de sable dans l'univers) : il faut aussi que je résume un peu les calculs qu'il fait. Là aussi, il y a des choses extrêmement modernes et d'autres qui paraissent être des distractions.

Archimède cherche à estimer le nombre de grains de sable qui tiendront dans une boule dont le rayon est la distance Terre-Soleil (ce que d'après lui les astronomes/astrologues appellent univers, enfin, κόσμος, cosmos), même si ensuite il utilise une théorie d'Aristarque pour élargir jusqu'à une boule encore plus grosse, supposée aller jusqu'aux étoiles fixes. Il fait les hypothèses suivantes :

  1. La circonférence de la Terre ne dépasse pas 3 000 000 stades, c'est-à-dire que le rayon de la Terre est inférieur à 10⁸ mètres en unités SI. Il dit clairement que c'est une majoration grossière, et il a entièrement raison.
  2. Le diamètre la Terre est plus grand que celui de la Lune, et celui du Soleil est plus grand que celui de la Terre. Là, il a indiscutablement raison.
  3. Le diamètre du Soleil est au plus 30 fois celui de la Lune. En fait, la vraie valeur du rapport de taille Soleil/Lune est à peu près 400. Ceci dit, cette sous-estimation faite par Archimède va être compensée par les marges qu'il a prises ailleurs : d'une part, en fait, il combine cette estimation avec la première partie du point précédent pour dire que le diamètre du Soleil est au plus 30 fois celui de la Terre, ce qui est toujours faux mais moins (la vraie valeur est environ 100) ; d'autre part, comme il a volontairement surestimé d'un facteur plus que 10 la taille de la Terre, finalement son majorant fonctionne.
  4. Le diamètre du Soleil est plus grand que le côté d'un kilogone/chiliogone (:= polygone à mille côtés) régulier inscrit dans un cercle dont le rayon est la distance Terre-Soleil. (C'est-à-dire, dans des termes plus modernes, que le diamètre du soleil vaut au moins 2·sin(π/1000) fois la distance Terre-Soleil.) Là, ce n'est pas tant une hypothèse qu'une observation, à savoir la mesure du diamètre apparent du Soleil, qu'il estime entre 1/200 et 1/164 d'un angle droit, c'est-à-dire entre 27 et 33 minutes d'arc, ce qui est très bien mesuré (la bonne valeur est apparemment 32′), et Archimède prend le temps d'expliquer comment il a fait la mesure, y compris comment il a essayé de tenir compte du fait que son œil n'est lui-même pas un point. • Ensuite, il y a une démonstration géométrique qui paraît incroyablement fastidieuse au lecteur moderne que je suis, pour passer de cette estimation (diamètre apparent du Soleil entre (π/2)/200 et (π/2)/164 radians) à la conclusion annoncée sur le diamètre du Soleil (au moins 2·sin(π/1000) de la circonférence d'un cercle de rayon la distance Terre-Soleil) ; la raison pour laquelle ce n'est pas complètement évident est que l'observateur n'est pas au centre de la Terre, il est plus près du Soleil (d'au plus un rayon terrestre), donc Archimède explique pourquoi l'angle qui serait mesuré au centre de la Terre ne serait pas trop diminué : si je résume, le diamètre du Soleil est au plus (π/2)/164 < 1/100 de la distance Terre-Soleil, donc a fortiori (d'après la deuxième partie de l'avant-dernier point) le diamètre de la Terre est au plus 1/100 de la distance Terre-Soleil, donc la distance de l'observateur au Soleil (plus exactement, à un point du Soleil au bord de ce qu'on observe, i.e., un point de tangence) est au moins 99/100 de ce qu'elle serait au centre de la Terre, du coup l'angle qu'on observerait au centre de la Terre serait au moins 99/100 de l'angle de (π/2)/200 mesuré, et comme 99/20000 > 1/203, le diamètre apparent au centre de la Terre serait au moins (π/2)/203, conclut Archimède, or 4×203<1000, c.q.f.d.
  5. Le nombre de grains de sables dans le volume d'une graine de pavot ne dépasse pas 10000, et le diamètre d'une graine de pavot n'est pas moins de 1/40 de la largeur d'un doigt. La seconde estimation est très conservatrice (une graine de pavot doit faire dans les 2mm, c'est donc plutôt quelque chose comme 1/10 de la largeur d'un doigt selon les doigts qu'on a et ce qu'il appelle la largeur d'un doigt) ; la première, je ne sais pas bien, parce qu'il y a du sable de toutes sortes de tailles : pour du sable moyennement grossier, ça semble tourner autour de 5 grains par mm³, donc l'estimation d'Archimède serait de nouveau très conservatrice, mais il y a des poussières dont on ne sait pas si elles comptent comme des grains — en tout cas, si un grain de sable doit être visible à l'œil nu, Archimède a certainement raison qu'il y en a moins de 10000 dans le volume d'une graine de pavot.

On en déduit que le diamètre de l'« univers » (:= deux fois la distance Terre-Soleil) ne dépasse pas (1000/3) fois celui du Soleil (i.e., il minore 2·sin(π/1000) par 6/1000), donc ce diamètre dépasse 10000 fois le diamètre de la Terre (avec l'estimation d'Archimède ; le vrai rapport est plutôt dans les 20000), qui est lui-même d'au plus 10↑6 stades, ce qui donne un diamètre de l'« univers » d'au plus 10↑10 stades (soit 2×10↑12 mètres, la bonne valeur est de 3×10↑11 mètres).

À partir de là, il n'y a plus qu'à faire les calculs d'ordre de grandeur : en commençant par une boule de diamètre 1/40 de la largeur d'un doigt et en multipliant à chaque fois par 100, Archimède calcule un majorant du nombre de grains de sables qui peuvent tenir dans la boule en question : moins de 6.4×10⁸ < 10⁹ pour une boule de diamètre d'un doigt, donc moins de 10↑15 pour une boule de diamètre 100 doigts, donc moins de 10↑21 pour une boule de diamètre 10000 doigts, largeur qui est elle-même plus grande qu'un stade, donc moins de 10↑27 pour une boule de diamètre 100 stades, donc moins de 10↑33 pour une boule de diamètre 10↑4 stades, donc moins de 10↑39 pour une boule de diamètre 10↑6 stades, donc moins de 10↑45 pour une boule de diamètre 10↑8 stades, donc moins de 10↑51 pour une boule de diamètre 10↑10 stades, qui est la taille par laquelle il a majoré le diamètre de l'« univers ». Comme je le disais, à chaque multiplication par 100, il reconvertit de la puissance de 10 dans son système de grands nombres basé sur 10⁸, on se demande pourquoi.

Ensuite, Archimède rappelle la théorie d'Aristarque selon laquelle la sphère des étoiles fixes a une taille comparée à celle qu'il a appelé l'univers (i.e., de rayon la distance Terre-Soleil) comme celle-ci par rapport à la Terre (si on prend les mesures modernes, ça mettrait les étoiles fixes à environ un tiers d'année-lumière, ce qui est sous-estimé mais pas du tout ridicule ; cf. aussi ce que je racontais dans cette entrée sur l'expérience menée beaucoup plus tard par Huygens). Et même avec cette estimation, fait remarquer Archimède, le nombre de grains de sable qui remplirait la totalité de la sphère des étoiles fixes serait fini : puisque l'univers (i.e., la distance Terre-Soleil) est au plus 10000 fois la taille de la Terre (a-t-on estimé plus haut), il suffit de mettre encore deux facteurs 100, et au final Archimède arrive à moins de 10↑63 grains de sable dans cette sphère.

Ce que j'ignore totalement, c'est comment ce texte a été reçu. On a l'impression qu'il était à deux doigts d'inventer les logarithmes et le système d'écriture positionnel, et que si personne ne l'a fait pendant si longtemps c'est forcément que ce texte avait été oublié, ou n'avait pas été compris, et notamment que personne n'avait vraiment réfléchi à la magnitude des nombres décrits par Archimède. Mais est-ce le cas ? De nouveau, je ne suis pas historien, je n'en sais rien ; je suis étonné de voir que les quelques articles que je trouve qui étudient l'impact historique de l'Arénaire se concentrent sur l'héliocentrisme (franchement, ça ne me semble pas très intéressant comme question, et ça ne semble pas intéresser énormément Archimède). Ah, j'ai quand même trouvé cet article (Piero Delsedime, L'infini numérique dans l'Arénaire d'Archimède, Archive for History of Exact Sciences 6 (1970), 345–359), mais je le trouve assez vaseux. • En revanche, cet article (assez difficile à suivre) pourrait expliquer que les œuvres d'Archimède, et ce texte particulièrement, n'étaient pas très connus, voire pas connus du tout, jusqu'au milieu du XVe siècle.

Pour d'autres remarques sur l'histoire de la googologie (i.e., des grands nombres), je peux renvoyer à plusieurs articles de Craig Smoryński, par exemple “Big” news from Archimedes to Friedman (Notices Amer. Math. Soc. 30 (1983), 251–256), c'est d'ailleurs là où j'ai entendu parler de l'Arénaire, partiellement visible ici, ou bien Some rapidly growing functions (Math. Intelligencer 2 (1980), 149–154), disponible ici, et sa suite, The varieties of arboreal experience (Math. Intelligencer 4 (1982), 182–189), disponible ici.

(mardi)

Comment je corrige des copies

S'il y a un aspect du métier d'enseignant que je n'aime vraiment pas, c'est corriger des copies : à l'agacement de voir passer 25 fois la même erreur s'ajoute la frustration de ne pas pouvoir interagir avec celui qui l'a faite. (Au contraire, quand je fais passer un oral, les erreurs du candidats sont plutôt une source d'intérêt pour moi, parce que c'est l'occasion de comprendre la profondeur de l'erreur, de laisser des occasions de la découvrir et de la corriger, bref, d'interroger de façon personnelle.)

Le tout, donc, est de maximiser l'efficacité. Quand je corrige des copies que les étudiants ne demanderont pas à voir (ce qui, à Télécom ParisPloum, est presque toujours le cas), je ne mets aucune annotation dessus, sauf de très rares mentions pour moi-même s'il y a une faute qui risque d'être difficile à retrouver en cas de relecture. Ça fait gagner un temps important : j'ouvre un tableur avec la liste des élèves en colonne, la liste des questions en ligne, et je prends les copies une par une en entrant des nombres dans le tableau. On gagne encore plus de temps à ce que toutes les questions soient sur le même nombre de points (ça évite de regarder le barème à chaque fois) : par exemple, mettre un nombre entre 0 (=tout faux) et 1 (=tout juste) à chaque question, quitte à insérer une pondération plus tard (et tant pis si ça conduit à des notes bizarrement fractionnaires). Il est aussi bon, pour l'efficacité, qu'il y ait essentiellement une chose à dire par question (si ce n'est pas le cas, il vaut mieux subdiviser — sinon, on risque de se retrouver à mettre la totalité des points à une copie qui n'a répondu qu'à la moitié de la question).

Les premières copies prennent beaucoup plus de temps à corriger que les suivantes. Peut-être cinq fois plus pour la première copie, parce qu'on ne connaît pas encore le sujet, donc pas encore les choses à repérer dans chaque question — les réponses vraiment attendues, les fautes courantes. Parce que rapidement, la correction de chaque question se termine à vérifier un ou deux points-clés comme le nom du théorème à invoquer ou la présence de tel calcul intermédiaire ou quelque chose de ce genre ; inversement, tel ou tel signe rapidement familier, comme un théorème qui ne peut tout simplement pas s'appliquer, voudra dire que la question est fausse et on ne cherche pas plus loin. Il y a bien parfois quelques copies exceptionnelles qui arrivent à dire des choses justes ou fausses, peu importe, mais différemment des autres, et elles peuvent demander plus de temps que trois copies « normales », mais ça reste une infime minorité.

Pendant des années, j'avais l'habitude de corriger « transversalement », c'est-à-dire de corriger un bout du sujet (par exemple, un exercice) sur l'ensemble du paquet, puis un autre bout du sujet, etc. L'avantage est qu'on se familiarise d'autant plus vite avec les fautes courantes, et la notation est sans doute d'autant plus juste : on se rappellera parfaitement comment on a pénalisé telle ou telle faute vénielle sur la question ; on peut commencer la correction de chaque partie par une copie différente, ce qui diminue d'autant l'impact de l'effet « première copie » (cf. ci-dessous) ; et ça évite aussi de se laisser influencer dans la question 2 par le fait que la question 1 était bien traitée (ceci dit, ça peut être un avantage ou un inconvénient). Le problème avec cette façon de faire est surtout que les étudiants ne marquent jamais assez clairement où commence chaque question, et sont capables de semer des bouts de réponse un peu partout — donc on perd énormément de temps à les retrouver, et j'ai fini par arrêter de faire comme ça.

Vu que je ne corrige plus transversalement, il est possible que la première copie que je corrige soit favorisée, ou défavorisée, je ne sais pas : du coup, je la tire toujours au hasard (et je cycle ensuite dans l'ordre alphabétique — il reste sans doute un biais systématique parce qu'un élève qui arrive alphabétiquement juste après un élève très mauvais sera peut-être favorisé, ou défavorisé, je ne sais pas, mais je pense que c'est vraiment très mineur comme effet). J'essaie aussi de ne pas lire le nom de l'étudiant dont je corrige la copie (je vérifie que j'ai rempli la bonne ligne du tableau seulement après l'avoir fait), ne serait-ce que pour ne pas risquer de favoriser, ou défavoriser, les filles, ou les noms ayant telle ou telle consonance, ou bien sûr, dans les groupes d'étudiants que je connais, telle ou telle tête familière.

(dimanche)

L'histoire compliquée du salut-qui-n'est-pas-romain, et la destruction de Carthage

Je suis tombé sur la question du salut romain en regardant un épisode de QI qui, comme d'habitude, nous apprend à nous méfier de plein d'idées répandues, notamment :

La vérité est qu'on ne sait pas vraiment comment les Romains saluaient (outre qu'il n'y avait certainement pas une unique forme de salut dans tous les contextes et pendant toute l'histoire de la Rome même classique), et si certaines variantes du geste fait avec la main droite levée semblent effectivement avoir eu une signification particulière, ce qui est d'ailleurs difficilement évitable, ce n'était pas forcément un salut (cela peut être un geste accompagnant une prière, un serment, ou encore la marque d'autorité d'un empereur ou d'allocution à un groupe) comme dans la position de la statue d'Auguste Prima Porta, dont la main n'est d'ailleurs peut-être même pas d'origine, ou la statue équestre de Marc-Aurèle, dont le bras n'est pas franchement levé.

C'est certainement le tableau Le Serment des Horaces de David de 1784 et dans son Serment du Jeu de Paume (inachevé, mais néanmoins célèbre à travers son dessin préparatoire) où il reproduit consciemment le même geste, que le serment main droite tendue est devenu célèbre. Mais l'histoire de ce salut-qui-n'est-pas-romain est vraiment compliquée : des variantes sont devenu le salut de Bellamy États-Unis (1892–1942) pour le serment d'allégeance au drapeau, et le salut (ou geste du serment) olympique aux jeux de 1920 à 1936 ; il a été utilisé par Gabriele d'Annunzio dans le film Cabiria et ensuite comme signe d'adhésion pendant sa régence de Fiume en 1919, qui a ensuite inspiré Mussolini, puis Hitler, lequel n'était pas mécontent en 1936 de la quasi indistinguabilité avec le salut olympique (largement mise en scène par Leni Riefenstahl dans son Olympia), et ceci nous ramène d'ailleurs à ce dont je parlais au début de cette entrée.

Je ne vais pas raconter plus en détails cette histoire du salut « romain », parce que c'est fait dans l'article Wikipédia sur le sujet qui est lui-même un résumé assez long (et par endroits, une paraphrase, voire une (re)copie un peu douteuse) d'un livre de 235 pages publié sur le sujet, The Roman Salute (Cinema, History, Ideology) de Martin Winkler, disponible en ligne ici : un voyage assez fascinant à travers l'histoire, l'historiographie, l'iconographie et le cinéma pour retracer le cheminement bizarre de ce geste.

Je pense que c'est une histoire, d'erreurs ou falsifications historiques et d'inspirations aux conséquences inattendues, qui avait dû — ou aurait pu — énormément plaire à Umberto Eco (dont je salue au passage la mémoire) : il y a quelque chose de délicieusement ecoïen(?) et en tout cas ouroborien quand l'erreur historique devient elle-même histoire qu'on peut étudier et retracer.

J'en profite pour mentionner une autre erreur historique qui est devenu un lieu commun sur l'antiquité romaine et qui a même mordu des historiens sérieux. « Tout le monde sait » que quand Scipion Émilien a fait détruire Carthage, il a fait semer le sol de sel pour que rien n'y repousse jamais, en tout cas c'est ce qu'on m'a raconté quand j'étais au lycée et c'est un symbole souvent répété tellement l'image est forte. L'ennui — mais ce n'est peut-être pas un ennui puisque comme je le signale dans le fragment littéraire gratuit lié ci-dessus, la vérité historique n'est peut-être pas le point le plus important, ou, de façon plus concise, se non è vero, è ben trovato — l'ennui possible, donc, c'est que cette histoire est essentiellement inventée : aucun texte ancien ne confirme cette histoire de sel.

Retrouver l'origine de cette invention s'avère étonnamment difficile : R. T. Ridley de l'université de Melbourne a publié en 1986 un article (To be taken with a pinch of salt: the destruction of Carthage, Classical Philology 81, 140–146) retraçant cette « information » à l'historien Bertrand Hallward, dans la première édition du Cambridge Ancient History (volume VIII, p. 484), en 1930, mais d'autres ont retrouvé des sources plus anciennes et peut-être indépendantes. Notamment, on apprend dans un article de Warmington de 1988 (The Destruction of Carthage: a Retractatio, Classical Philology 83, 308–310) que le pape Boniface VIII, dans une bulle De civitate nova, sub nomine Civitatis Papalis, prope civitatis Prænestinæ destructæ locum constructo[#] datée à Anagni du 13 juin 1299, fait référence au sort réservé à la ville de Palestrina prise à la famille Colonna (qui avait déclaré l'élection du pape illégitime, et qui avait capitulé suite à la promesse que la ville serait épargnée) : ipsam aratro subjici[t] ad veteris instar Carthaginis Africanae, ac salem in ea etiam [Domnius papa] fecit et mandavit seminari ut nec rem nec nomen aut titulum habeat civitatis — bref, rasée et semée de sel comme l'ancienne Carthage. (Si vous trouvez ça révoltant et voulez une forme de justice : dans sa Divine Comédie, Dante imagine Guy I de Montefeltro en enfer pour avoir conseillé au pape de mentir aux Colonna en leur promettant l'amnistie.) Mais le pape suit certainement la référence à l'histoire biblique d'Abimélek qui une fois reprise la ville de Sichem dont il avait été chassé par ses habitants il en massacra la population, détruisit la ville et y sema du sel (Juges 9:45). Comme pour l'histoire du salut bras tendu, les comportements supposés des Romains inspirent des gens aux mœurs si sympathiques !

[#] Oh, que c'est pénible de retrouver en ligne une bulle papale du Moyen-Âge ! Moi je me suis dit naïvement je vais aller sur le site du Vatican, ils les ont certainement toutes numérisées sous un format recherchable, que nenni. Donc si vous voulez retrouver cette bulle, il faut aller récupérer le bouquin Les Registres de Boniface VIII (Recueil des bulles de ce pape publiées ou analysées d'après les manuscrits originaux des archives du Vatican) par Georges Digard, Maurice Faucon, Antoine Thomas & Robert Fawtier, tome deuxième, 1904, et chercher sous le numéro 3416 (page 587–588), numéro que Warmington se garde bien de donner quand il cite la bulle en qustion. J'ai bien fait de ne pas avoir fait des études d'histoire parce que ma première réaction devant ce genre de merde, c'est de dire bon, on arrête tout, on fait un site Web où ce genre de documents sera facile à trouver.

(vendredi)

Zootopia

Pour ceux qui sont en France il est probablement déjà difficile de trouver une séance du dernier Disney, surtout si on veut le voir en VO (ce que je recommande vivement) : mon poussinet y sommes allés hier soir, et il ne restait plus beaucoup de cinémas qui le diffusent à Paris. Mais si vous y arrivez, ou si vous attendez la sortie en DVD (ou tout autre moyen plus ou moins légal de le voir), toujours est-il que je le recommande très vivement.

Ce film est vraiment excellent. Et pas que pour les enfants (enfin, je suppose qu'il est bien pour les enfants, je ne sais pas trop juger, mais en tout cas il n'est pas besoin d'en être un pour apprécier). Peut-être que je suis bon public pour les films de Disney en général, mais en fait je ne crois pas (si je regarde la liste sur Wikipédia, il y en a énormément que je n'ai aucune envie de voir, et de ceux que j'ai vus mon avis n'est pas forcément des plus enthousiastes).

Bref. Je ne pense pas que ce soit vraiment utile que je fasse une critique. Comme beaucoup de films pour enfants de Disney ou Pixar[#] (genre Ratatouille[#2]), une des morales de l'histoire est on peut devenir ce qu'on veut en grandissant (mais ce ne sera pas facile et il faudra sans doute lutter pour y arriver), bref, rien de très original, même si la façon dont cette morale est amenée est plutôt intelligente, et il y a des rebondissements intéressants. Une autre morale est une leçon contre le racisme (un monde d'animaux[#3] s'y prête, évidemment, très bien), leçon qui n'est pas non plus originale, mais ça ne l'empêche pas d'être la bienvenue et zeitgemäß (comment on dit ça en français, déjà ?), et j'ai trouvé qu'elle était construite de façon assez subtile. J'ai eu la larme à l'œil plus d'une fois.

Mais c'est vraiment l'humour graphique et situationnel qui est absolument génial, et il n'y a pas beaucoup de films qui m'aient autant fait rire. Certes, ce n'est pas très difficile de trouver plein de blagues à faire sur un monde d'animaux, mais même les gags les plus faciles marchent vraiment bien (comme le service des permis de conduire où tous les employés sont des paresseux, le chef de la police qui dit devoir reconnaître the elephant in the room, ou encore l'héroïne qui passe devant une banque appelée Lemming Brothers). Chaque scène regorge de détails incroyablement bien trouvés.

Bref, je ne m'appesantis pas : allez-voir Zootopia si vous pouvez, vous ne le regretterez sans doute pas.

[#] Précisons que Zootopia n'est pas de Pixar (après, je ne comprends rien à l'organisation interne de Disney, et je soupçonne que comme toute grosse organisation, eux-mêmes ne doivent pas vraiment se comprendre, donc je ne sais pas exactement ce que ça veut dire, d'être ou de ne pas être de Pixar : mais en tout cas, parmi les quarante-douze logos qu'on voit défiler au début du film, il n'y a pas celui avec les fameuses lampes).

[#2] Contre-exemple notable : Monsters University. Sans doute pas un des meilleurs films de Disney ou Pixar, mais avoir eu l'audace de faire un film pour enfants dont la morale soit essetiellement non, on ne peut pas toujours devenir ce dont on rêve (mais ce n'est pas si grave) mérite d'être applaudi.

[#3] Enfin, de mammifères : le film est peut-être contre le spécisme, mais il est un peu classiste(?).

(lundi)

Deux cours que je donne

J'enseigne en ce moment, et jusqu'à fin avril, deux cours (je l'ai déjà mentionné ici), tous deux de niveau master : l'un intitulé théorie des jeux le lundi matin de 8h30 à 11h45, et l'autre intitulé courbes algébriques le lundi après-midi de 15h15 à 18h30.

C'est assez crevant : rien que le fait de soutenir la voix pendant six heures dans la même journée est usant pour la gorge, et mine de rien, écrire au tableau blanc finit aussi par fatiguer le bras. Mais le pire est surtout le cycle vicieux où le dimanche soir je me dis il faut que je dorme bien cette nuit sinon demain va être un enfer, et du coup je stresse, et du coup je ne dors pas bien, et je stresse encore plus (voir le 6º de cette liste). Et si la longue pause entre le cours du matin et le cours de l'après-midi me permet de me détendre un peu, je n'arrive pas à faire une sieste dans la journée, et au final ça fait des horaires assez longs. L'avantage, c'est que le lundi soir je suis un peu tranquille (enfin, le lundi soir je suis surtout crevé et tout juste bon à regarder des conneries sur YouTube, mais le mardi je suis tranquille). D'un autre côté, si je laisse passer trop de temps à souffler, je me rends vite compte qu'il me faut en gros toute la semaine pour préparer les cours du lundi suivant, donc ça peut vite redevenir la panique : du coup, je suis un peu débordé en ce moment.

Je suis très libre de décider ce que je mets dans ces deux cours, ce qui est très agréable (mais aussi potentiellement dangereux).

Pour le cours de théorie des jeux, dont j'ai expliqué à mes étudiants que j'aurais plutôt dû l'appeler théories des jeux, j'aimerais aborder toutes sortes de sujets différents — quitte à ne faire que les effleurer — pour donner une aperçu aussi varié que possible. Un de mes sujets d'énervement préférés est les gens qui utilisent le terme théorie des jeux pour désigner un tout petit sous-ensemble de la théorie : voyez par exemple ce cours en ligne dont la liste des sujets évoqués fait apparaître en creux la quantité de choses dont ils ne parlent pas (par exemple : toute la théorie combinatoire des jeux, aussi bien celle de Sprague-Grundy que celle de Conway, toutes les questions de calculabilité et de complexité adjacents, tous les problèmes de détermination des jeux infinis à information parfaite style Gale-Stewart, et les liens entre la théorie des jeux et la logique comme les jeux sémantiques et les jeux d'Ehrenfeucht-Fraïssé, pour ne même pas parler de la théorie des jeux différentiels) ; ce n'est pas interdit de ne parler que d'un tout petit bout de la théorie, mais je trouve que ç'en est un d'appeler ça théorie des jeux (enfin, game theory). Enfin, ce qui me pose surtout problème, c'est que je ne sais pas quel nom donner au petit sous-ensemble de la théorie des jeux que considèrent les auteurs du cours dont j'ai donné le lien (j'ai envie d'appeler ça la théorie nashienne des jeux, parce le concept fondateur est celui d'équilibre de Nash).

Pour le cours de courbes algébriques, la question est surtout comment arriver à des choses intéressantes sans noyer les étudiants dans trop de prérequis d'algèbre, et je ne suis pas du tout certain d'y arriver. Jusqu'à l'an dernier, je donnais un cours de géométrie algébrique qui était plutôt un échec de ce point de vue-là : même si j'admettais quasiment tout, il fallait une quantité énorme de formalisme pour arriver à ne serait-ce qu'énoncer les résultats intéressants. Le fait de se concentrer sur la dimension 1 devrait simplifier les choses, mais je me rends compte qu'il y a quand même énormément de choses à introduire sur les corps et extensions de corps pour pouvoir parler commodément de corps de fonctions. • Je n'ai toujours pas décidé, d'ailleurs, si le terme K est un corps de fonction de courbe sur k devrait vouloir dire K est un corps de type fini sur k, de degré de transcendance 1, et dans lequel k est algébriquement fermé ou bien (plus fort) K est un corps de type fini sur k, de degré de transcendance 1, et linéairement disjoint de la clôture algébrique de k : notamment, est-ce que k(x,y : u·xp+v·yp=0) est un corps de fonction de courbe sur k := Fp(u,v), sachant qu'il vérifie la première mais pas la seconde condition ? et laquelle de ces conditions est pédagogiquement la moins indigeste ?

Le fait de chercher à écrire un cours sur un sujet est souvent l'occasion de se rendre compte de lacunes inexplicables dans la litérature : comme des résultats bien connus mais néanmoins introuvables, ou comme des résultats trouvables mais pas de la façon qu'on voudrait, par exemple (sur ces deux liens, voir à la fois la question que je pose et la réponse que j'ai fini par faire à moi-même).

Il y a une autre chose dont on ne se rend correctement compte qu'en essayant d'enseigner un sujet, c'est à quel point une notion mathématique dépend d'une autre pour sa construction. Je fais référence au fait suivant : si je fais un cours sur les foobars bleutés, je consulte la litérature sur les foobars bleutés et je constate que le théorème de frobnification locale des foobars bleutés fait appel au théorème de Pumpernickel qui assure qu'un foobar est localement isomorphe à un bazqux et au lemme de Bratwurst qui affirme que tout bazqux est finiment frobnicable ; la question se pose alors, dans un cours sur les foobars, faut-il mettre un chapitre sur la théorie des bazqux, faut-il admettre ou démontrer le lemme de Bratwurst, et si on le démontre, peut-être faut-il essayer de le démontrer dans le cas particulier des foobars, foire des foobars bleutés, où peut-être il se simplifiera ?

Parfois une démontration mathématique se simplifie quand on l'« instancie » dans un cas particulier (certains arguments peuvent être évités, d'autres deviennent plus simples, plus courts ou plus transparents) ; ou simplement, ça évite d'avoir à introduire des concepts généraux qui ne sont pas très parlants. Mais parfois c'est le contraire : la démonstration appliquée dans un cas particulier devient plus complexe ou plus obscure. Et le plus souvent, la seule façon de savoir, c'est d'essayer : prendre la démonstration du théorème de théorème de Pumpernickel en la combinant à celle du lemme de Bratwurst et voir s'il en résulte quelque chose de plus ou moins indigeste. Et le fait de ne pas savoir à l'avance peut faire perdre énormément de temps : on commence par écrire toute la théorie des foobars en cherchant à éviter celle des bazqux, puis on se rend compte que c'est vraiment trop pénible, et il faut alors tout remanier pour dégager cette théorie dans une partie à part.

Bref, pour l'instant j'écris mes notes de cours au fur et à mesure, et j'espère que je ne vais pas tomber sur des impasses en me rendant compte que je n'ai vraiment pas présenté les choses comme je l'aurais dû. Mes notes en cours d'écriture (et pour l'instant très inachevées) sont ici pour la théories des jeux (PDF ici, pas forcément à jour) et ici pour les courbes algébriques (PDF ici, même remarque).

(mercredi)

Je revois The Last Unicorn

Ce soir j'ai revu le dessin animé The Last Unicorn que j'ai vu quand j'étais petit (je crois que c'était avec ma classe — j'étais probablement en CM1 ou CM2, en tout cas à l'école primaire, probablement pas très longtemps après sa sortie). Entre temps, il y a une dizaine d'années, j'ai lu le livre dont il est tiré — je l'avais raconté sur ce blog à l'époque. Aussi bien le livre que le film sont assez étranges : l'histoire est souvent très enfantine, mais elle n'a pas la morale simpliste des contes pour enfants, il n'y a pas vraiment de gentils et de méchants, les motivations des personnages sont difficiles à comprendre, on ne sait pas s'il faut comprendre le tout comme une sorte d'allégorie, de récit symbolique ou codé, une poésie surréaliste, ou encore autre chose, bref, on ne sait pas sur quel pied danser. Le film lui aussi semble changer sans arrêt d'avis sur le registre sur lequel il faut le comprendre, et il y a des passages vraiment bizarres, dérangeants ou inquiétants. La page que je viens de lier décrit ainsi le Taureau de Feu du dessin animé : Pure unadulterated nightmare fuel. This is the kind of thing that makes your stomach drop and gives an ill-prepared child a lifelong complex. You simply can't watch this movie and not be scared of The Red Bull. The Red Bull is fear. De fait, je crois que cette image m'avait beaucoup impressionné quand j'avais vu ce film, et peut-être bien que j'en ai fait quelques cauchemars. (En plus, rien que la traduction française Taureau de Feu, ça fait plus peur que l'anglais Red Bull, même sans compter que maintenant Red Bull est un soda.)

(mercredi)

De l'agacement provoqué par un téléviseur arnaque

Je racontais le mois dernier que la télécommande de mon téléviseur chinois merdique à deux balles (i.e., 130€) était tombée en panne, rendant celui-ci essentiellement inutilisable. À la place, nous avons rapidement acheté une télé un tout petit peu plus cher (200€) et d'une marque connue (Samsung), en espérant qu'au moins la télécommande serait plus facile à remplacer en cas de panne. Précisément, il s'agit d'une Samsung UE19H4000AW, numéro de modèle qui donne au moins un tout petit plus de réponses quand on le recherche sur Internet que la Akira LED-B81HU19F dont la télécommande est morte. À première vue, elle semblait d'un peu meilleure qualité que la Akira sur pas mal de petits détails : angle de vue de l'écran moins étroit, possibilité de changer de chaîne sans avoir à attendre plusieurs secondes que la vidéo s'affiche, affichage des infos TNT mieux fait, pas de problème d'encodage des caractères accentués, lecture des fichiers MKV, et quelques choses du même genre. J'ai supposé naïvement qu'elle était capable de faire tout ce que l'ancienne était capable de faire. Erreur : il y a une arnaque.

Je m'en suis rendu compte ce soir en voulant enregistrer un film. J'aurais dû essayer dès le début, parce que la fonction « enregistrement » est parfois incroyablement bien cachée dans le système d'interface de ce genre de gadgets (sur la précédente, nous avons mis un temps fou à comprendre comment lancer un enregistrement programmé à une heure donnée). Mais là, au bout de plusieurs dizaines de minutes passées à essayer systématiquement tous les boutons possibles dans tous les contextes possibles, nous avons fini par nous rendre à l'évidence :

Cette télé ne sait pas enregistrer.

Je me sens comme si on m'avait vendu une télé noir et blanc parce que je n'ai pas pensé à vérifier qu'il était bien écrit téléviseur couleur sur la boîte.

Car franchement, en 2016, vendre un téléviseur TNT numérique qui n'est pas capable d'enregistrer (alors qu'il a une prise USB depuis laquelle il est capable de lire toutes sortes de formats vidéo, et qu'il s'agit là simplement de recopier, sans réencodage quelconque, le flux numérique qu'il reçoit de la TNT sur le support USB), c'est du même niveau que vendre un téléviseur noir et blanc : ce n'est peut-être pas illégal, mais c'est quand même une arnaque honteuse. Si même ma télé chinoise à deux balles était capable de le faire, c'est vraiment que c'est une fonction de base.

Mon poussinet propose que nous prenions un décodeur TNT externe qui serait capable d'enregistrer ; mais je n'ai vraiment pas envie d'avoir une télécommande supplémentaire (surtout que me débarrasser d'une télécommande de trop était la principale raison pour laquelle j'avais remplacé ma télé cathodique par une numérique en premier lieu). Je suis prêt à passer les 200€ aux pertes et profits et racheter une nouvelle télé, mais maintenant que je suis averti qu'il faut explicitement chercher chaque fonction dont on peut avoir besoin sous peine de se faire arnaquer, je me dis que ça va être difficile de trouver un modèle sur lequel je puisse vérifier chaque point important.

Bref, quelqu'un a-t-il un modèle de télé à recommander ? Il faut qu'il soit achetable en France, d'une largeur entre environ 40cm et 49.5cm, capable de recevoir et décoder la TNT française, de lire les formats et codecs vidéo les plus courants sur support USB, d'enregistrer dessus, y compris lire en même temps qu'il enregistre (pour pouvoir faire une pause dans une émission qu'on regarde en direct)… mais il faut sans doute aussi plein d'autres choses que je ne pense pas à lister ici parce qu'elles me semblent tellement évidentes (être en couleur, être capable d'afficher les informations et métainformations fournies par la TNT, être capable pendant une lecture de faire une pause, une avance d'une seule frape, une avance rapide, un retour rapide, un saut à un temps spécifié arbitrairement, que sais-je encore…). Ceci dit, j'ai l'impression que le critère le plus difficile est celui de la taille, à cause de tous les beaufs qui font de la taille de leur téléviseur un concours de bite, ça rend très limitée la sélection des téléviseurs qui tiennent dans le petit espace que je peux leur accorder.

(mardi)

Une question d'Analyse (moyenner une fonction), et de pourquoi elle m'intéresse

Commençons tout de suite par la question qui m'intéresse (je précise que je n'en connais pas la réponse), que je vais faire suivre de commentaires mathématiques, puis métamathématico-psychologiques :

Soit f une fonction réelle 1-périodique, et L¹ sur une période (ou, si ça ne suffit pas : mesurable et bornée). Est-il vrai que pour presque tout x, la moyenne arithmétique de f(x), f(x+1/n), f(x+2/n), f(x+3/n), …, f(x−1/n), converge vers l'intégrale de f (sur une période) ?

Cette question peut se voir comme la suite d'une question que j'avais proposée en exercice : si j'appelle (n(f))(x) la moyenne dont il est question ci-dessus, je sais montrer un certain nombre de choses, par exemple que n(f) tend dans Lp vers (la fonction constante égale à) l'intégrale de f si f est Lp et p<∞, ou qu'il y a convergence uniforme si f est Riemann-intégrable. Je signale quelques autres faits apparentés (ainsi qu'une esquisse de démonstration de ce que je viens de dire) dans cette question sur math.stackexchange, où je pose la question recopiée ci-dessus et je demande aussi s'il y a convergence dans L (lorsque f est L). Au moment où j'écris, je n'ai pas eu de réponse (et la question n'a suscité que très peu d'intérêt, ouin ☹).

Mise à jour () : Comme on me le signale en commentaire, la réponse est non : même pour f mesurable et bornée (en fait, même pour la fonction indicatrice d'une partie de ℝ/ℤ), il n'y a pas forcément convergence presque partout, ni même « quelque part », de n(f) vers f. C'est l'objet de l'article de Walter Rudin, An Arithmetic Property of Riemann Sums, Proc. Amer. Math. Soc. 15 (1964), 321–324. La démonstration de Rudin est courte et a l'air assez jolie et arithmétique. • Par ailleurs, auparavant, Marcinkiewicz et Zygmund, dans Mean values of trigonometrical polynomials, Fund. Math. 28 (1937), chapitre II, théorème 3 p. 157, avaient déjà montré que pour la fonction précise −log(|x|)/√|x| sur [−½,½], prolongée par périodicité, qui est L¹ sur une période mais non bornée, on n'a convergence nulle part. • Par ailleurs, ces articles montrent que d'autres que moi ont pensé que la question était naturelle, et d'autre part, qu'elle n'était pas triviale. (Le terme qui me manquait pour chercher était somme de Riemann : je pensais qu'une somme de Riemann était le cas associé à une subdivision quelconque, pas spécialement régulière, et qu'on n'allait donc pas trouver grand-chose de plus en cherchant ce terme que la construction de l'intégrale de Riemann.)

Mais une méta-question que je trouve aussi intéressante, c'est : pourquoi est-ce que je trouve la question ci-dessus extrêmement intéressante, importante et naturelle ? (Peut-être que je ne serai plus de cet avis si j'obtiens la réponse, mais au minimum je la trouve intéressante au sens où j'ai vraiment envie d'avoir la réponse.) Ce n'est pas juste que moyenner une fonction comme ça est une opération qui me semble très naturelle (et assez élégante) et qu'on a envie de savoir si ça converge vers l'intégrale voire, si ça donnerait une « définition » de l'intégrale de Lebesgue. L'Analyse n'est pas un sujet dont je suis un grand fan, mais à partir du moment où on me présente une « situation » mathématique (ici, le fait de moyenner une fonction 1-périodique par ses n translatés par 1/n, et de considérer la limite quand n→+∞) sur laquelle j'arrive à dire des choses, j'ai naturellement envie de me poser toutes les questions « adjacentes » à la situation : si j'ai un résultat de convergence dans Lp pour p<∞, j'ai naturellement envie de poser la question de la convergence L et de la convergence presque partout. (D'ailleurs, le mystère c'est pourquoi j'ai mis plus d'un an à me rendre compte que ces questions étaient naturelles et que je ne savais pas les résoudre !) En plus de cela, il y a toujours un degré de frustration à penser : bon sang, mais une question aussi simple et naturelle que ça, je devrais savoir y répondre !, ou au moins, trouver la réponse dans un livre/article.

J'ai souligné le mot naturel dans le paragraphe précédent, parce que c'est un aspect psychologique fondamental dans la manière dont je conçois les mathématiques : il n'y a pas que le fait que les objets soient élégamment symétriques et beaux par leur grandeur qui me motive, il y aussi le caractère naturel des questions qu'on se pose. Je me considère comme un mathématicien pur non pas parce que je ferais des choses qui ne servent à rien, mais parce que ce qui me motive quand je me pose une question de maths n'est pas qu'elle serve à quelque chose (même à l'intérieur des mathématiques), mais qu'elle soit naturelle dans le contexte. Et c'est une qualité que je ne sais pas définir (même si cela a certainement un rapport avec la simplicité) et dont je me demande à quel point elle est personnelle, voire complètement illusoire. Un autre mathématicien sera-t-il convaincu que la question ci-dessus est intéressante ? Je ne sais pas. (Pas plus que pour les questions de l'entrée précédente. En revanche, une question telle que est-il vraie que pour toute fonction réelle f il existe une partie dense à laquelle la restriction de f est continue ? est probablement « naturelle » si j'en crois les réactions que j'ai eues.)

Toujours est-il que je n'ai pas le temps d'y réfléchir sérieusement (et je ne suis pas sûr d'y connaître assez en Analyse pour avoir une chance sérieuse de savoir résoudre le problème), donc j'essaie insidieusement de convaincre d'autres gens d'y faire attention et d'y réfléchir à ma place. Wir müssen wissen — wir werden wissen! 😉

(dimanche)

Quelques théorèmes de points fixes

Je suis un peu débordé en ce moment par la préparation de deux cours[#] qui commencent dans deux semaines et dont je n'ai pour l'instant que des notes très éparses et inachevées, d'autant plus que j'enseigne autre chose en ce moment. Mais pendant la préparation d'un de ces cours, je suis tombé sur une difficulté mathématique au sujet de laquelle j'aimerais l'avis de mes lecteurs mathématiciens (il doit bien y en avoir) ou amateurs de mathématiques : ce n'est pas que je ne sache pas démontrer quelque chose, mais que je m'étonne de la façon dont je le démontre, et je trouve qu'il y a quelque chose de surprenant dans toute l'histoire. Bref, je vais commenter les ressemblances et différences entre quelques énoncés apparemment très semblables et surtout différentes démonstrations des énoncés en question.

[#] L'un de ces cours concerne la théorie des jeux ; ou plutôt les théories des jeux, parce qu'il y a plusieurs domaines que leurs spécialistes appellent théorie des jeux, selon le type de jeux étudiés, et dont l'intersection est relativement faible : pensez à celle (que je ne sais pas nommer plus précisément) qui cherche des équilibres de Nash et celle (en gros, la théorie combinatoire des jeux) qui cherche à calculer des valeurs de Sprague-Grundy, par exemple, chacune a tendance à se définir comme « la » théorie des jeux, et d'ailleurs ça m'énerve, en tout cas je voudrais parler des deux et de quelques autres encore. Mes notes en cours d'écriture sont ici. L'autre cours concerne les courbes algébriques, pour lequel il va s'agir de remanier profondément un cours de géométrie algébrique (anciennes notes ici) que je donnais déjà.

Voici quatre énoncés mathématiques très simples, en théorie élémentaire des ensembles, que je pourrais regrouper sous le label général de théorèmes de points fixes, et que je vais appeler successivement (P), (P$), (F) et (F$) :

(P) Soit X un ensemble : on note 𝒫(X) son ensemble des parties. Soit Ψ:𝒫(X)→𝒫(X) une application vérifiant les deux propriétés suivantes : (i) Ψ est progressive, c'est-à-dire que Ψ(A)⊇A pour tout A∈𝒫(X), et (ii) Ψ est croissante, c'est-à-dire que si AB alors Ψ(A)⊇Ψ(B). Alors il existe un plus petit A∈𝒫(X) tel que Ψ(A)=A (c'est-à-dire un A tel que Ψ(A)=A et que si A′ vérifie aussi Ψ(A′)=A′ alors AA′).

(P$) [Exactement le même énoncé que (P) sans supposer (i).] Soit X un ensemble : on note 𝒫(X) son ensemble des parties. Soit Ψ:𝒫(X)→𝒫(X) une application vérifiant la propriété suivante : Ψ est croissante, c'est-à-dire que si AB alors Ψ(A)⊇Ψ(B). Alors il existe un plus petit A∈𝒫(X) tel que Ψ(A)=A. [Un peu mieux : il existe un plus petit A tel que Ψ(A)⊆A, et ce A vérifie Ψ(A)=A.]

Pour les deux énoncés suivants, j'ai besoin de rappeler la notion de fonction partielle : si X et Z sont deux ensembles, une fonction partielle XZ est une fonction définie sur une partie de X et à valeurs dans Z ; on peut aussi la voir comme une partie de X×Z (à savoir, le graphe de la fonction) qui soit fonctionnelle au sens où si elle contient à la fois (x,z₁) et (x,z₂) pour le même xX alors forcément z₁=z₂. La relation fg entre fonctions partielles signifie alors que la fonction f prolonge la fonction g (i.e., que f est définie partout où g l'est, et qu'alors leurs valeurs coïncident).

(F) [Exactement le même énoncé que (P) avec des fonctions partielles XZ au lieu de parties de X.] Soient X et Z deux ensembles : on note 𝒟 l'ensemble des fonctions partielles XZ. Soit Ψ:𝒟→𝒟 une application vérifiant les deux propriétés suivantes : (i) Ψ est progressive, c'est-à-dire que Ψ(f)⊇f pour tout f∈𝒟, et (ii) Ψ est croissante, c'est-à-dire que si fg alors Ψ(f)⊇Ψ(g). Alors il existe une plus petite f∈𝒟 telle que Ψ(f)=f (c'est-à-dire un f tel que Ψ(f)=f et que si f′ vérifie aussi Ψ(f′)=f′ alors ff′). [Précision : on me fait remarquer à juste titre que cet énoncé est en fait totalement creux (cf. la mise à jour ci-dessous).]

(F$) [Exactement le même énoncé que (F) sans supposer (i), donc exactement le même que (P$) avec des fonctions partielles au lieu de parties.] Soient X et Z deux ensembles : on note 𝒟 l'ensemble des fonctions partielles XZ. Soit Ψ:𝒟→𝒟 une application vérifiant la propriété suivante : Ψ est croissante, c'est-à-dire que si fg alors Ψ(f)⊇Ψ(g). Alors il existe une plus petite f∈𝒟 telle que Ψ(f)=f. [Un peu mieux : il existe un plus petit f tel que Ψ(f)⊆f, et ce f vérifie Ψ(f)=f.]

(Nomenclature : j'appelle (P) et (P$) les énoncés sur les Parties, (F) et (F$) ceux sur les Fonctions partielles, et (P$) et (F$) les énoncés qui vous en donnent plus pour votre argent.) J'espère que j'ai écrit ces énoncés de façon à ce qu'il n'y ait pas le moindre doute sur leur signification formelle. L'objet dont chacun de ces énoncés affirme l'existence peut être qualifié de plus petit point fixe de Ψ.

Commentaires : Le sens intuitif de ces résultats est quelque chose comme le suivant : on a une opération Ψ qui, pour prendre l'exemple de l'énoncé (F), prend une fonction f et l'étend en une fonction peut-être définie sur un peu plus de points, et par ailleurs, Ψ possède une propriété de cohérence, à savoir que si on étend f, on étend aussi le résultat de l'opération Ψ(f) ; alors il existe une « clôture du vide » pour l'opération Ψ, c'est-à-dire qu'en partant de rien, l'opération Ψ vous permet d'arriver à une certaine fonction f à partir de laquelle l'opération Ψ ne la fait plus grandir. Pour donner un exemple d'application de (P$), considérer l'ensemble X=ℕ des entiers naturels, et l'opération Ψ qui à un ensemble A de naturels associe l'ensemble formé des entiers 2, 3 et tous les produits de deux éléments de A : le plus petit point fixe sera alors l'ensemble de tous les entiers qu'on peut fabriquer en multipliant 2 et 3 autant qu'on veut ensemble (à savoir l'ensemble des 2i·3j avec au moins un de i et j non-nul, mais peu importe) ; plus généralement, (P) ou (P$) peut servir à montrer l'existence de toutes sortes de « clôtures » sous des opérations variées. Généralement parlant, le concept de plus petit point fixe (ou de point fixe en général) apparaît très souvent en mathématiques, et il existe tout un labyrinthe — mais je crois vraiment que les énoncés que j'ai cités ci-dessus sont parmi les plus naturels.

Il est complètement évident que (P$)⇒(P) (parce qu'on suppose quelque chose de plus fort dans (P) pour arriver à la même conclusion) et de même que (F$)⇒(F). Il est aussi facile de voir que (F)⇒(P) et (F$)⇒(P$) grâce à l'« astuce » (si on peut l'appeler comme ça…) consistant à prendre pour Z un singleton (:=ensemble ayant un seul élément), de sorte qu'une fonction partielle XZ est essentiellement la même chose qu'une partie de X (à savoir la partie sur laquelle la fonction est définie). Du coup, (F$) est assurément le résultat le plus fort des quatre. (Les remarques que j'ai introduites par un peu mieux sont encore plus fortes que (P$) et (F$), on pourrait les appeler (P€) et (F€), mais en fait elles ne m'intéressent pas tellement en tant que telles : c'est juste que je ne sais pas démontrer (P$) ou (F$) sans obtenir directement ces résultats plus forts, et par ailleurs ils aident vaguement à comprendre comment les choses se passent.)

Mais si je prends la peine d'énoncer quatre résultats différents, c'est que le résultat (P) est extrêmement facile à démontrer :

Démonstration de (P) : Il existe des A tels que Ψ(A)=A (puisque l'ensemble X tout entier en est un). Soit C l'intersection de tous ces A. Alors C est inclus dans chacun de ces A, donc par (ii), Ψ(C) est inclus dans chacun des Ψ(A)=A ; du coup, Ψ(C) est inclus dans l'intersection des A en question, qui est justement C, et comme (i) donne l'inclusion dans l'autre sens, on a Ψ(C)=C. La construction même de C fait qu'il est bien le plus petit.

Je pense que n'importe quel mathématicien non seulement sait démontrer le résultat (P) à la lecture, mais tombera de plus essentiellement sur la démonstration que je viens de dire. Dans n'importe quel livre de maths, la démonstration serait simplement condensée en quelque chose comme l'intersection des points fixes de Ψ est elle-même un point fixe de Ψ comme on le vérifie facilement, et c'est donc le plus petit pour l'inclusion.

Bon, autant vous en donner un peu plus pour votre argent et démontrer (P$). Je vais le faire de deux façons différentes :

Démonstration de (P$) en utilisant (P) : Je suppose que Ψ seulement croissante (i.e., vérifiant (ii)), et j'appelle Ψ₁(A) := AΨ(A). Alors Ψ₁ vérifie (i) et (ii), donc par (P), il existe un plus petit A tel que Ψ₁(A)=A, ce qui signifie exactement Ψ(A)⊆A. Comme du coup (ii) donne Ψ(Ψ(A))⊆Ψ(A), le fait que A soit le plus petit à vérifier Ψ(A′)⊆A′ garantit AΨ(A), et on a bien Ψ(A)=A (et comme tout A′ qui vérifie Ψ(A′)=A′ vérifie en particulier Ψ(A′)⊆A′, il est bien inclus dans A, qui est donc le plus petit à vérifier Ψ(A′)=A′).

Démonstration directe de (P$) : Il existe des A tels que Ψ(A)⊆A (puisque l'ensemble X tout entier en est un). Soit C l'intersection de tous ces A. Alors C est inclus dans chacun de ces A, donc par croissance, Ψ(C) est inclus dans chacun des Ψ(A)⊆A ; du coup, Ψ(C) est inclus dans l'intersection des A en question, qui est justement C, ce qui prouve Ψ(C)⊆C. Par croissance, on a aussi Ψ(Ψ(C))⊆Ψ(C). Du coup, Ψ(C) est l'un des A qu'on a intersectés pour former C, ce qui montre Ψ(C)⊇C, et donc Ψ(C)=C. La construction même de C fait qu'il est le plus petit A′ tel que Ψ(A′)⊆A′, et comme tout A′ qui vérifie Ψ(A′)=A′ vérifie en particulier Ψ(A′)⊆A′, il est bien inclus dans C, qui est donc le plus petit à vérifier Ψ(A′)=A′.

Ça reste très simple même si je trouve ça un chouïa moins transparent. Mais là où les choses sont bizarres, c'est quand on considère (F) et (F$). C'est ici que j'invite mes lecteurs mathématiciens à faire une pause pour se demander comment ils démontreraient ces énoncés, parce que je serais vraiment curieux de savoir à quoi ils penseront spontanément. Je n'arrive pas à décider s'il y a une vraie difficulté ou pas : vue la tête de l'énoncé et vue les démonstrations que j'ai données de (P) et (P$), on se dit que (F) et (F$) ne doivent pas être difficiles. Mais l'idée qu'on a envie d'essayer en premier est sans doute de prendre l'intersection de toutes les fonctions partielles f telles que Ψ(f)⊆f, et elle se heurte à l'obstacle qu'il n'est pas évident a priori qu'il existe un tel f (i.e., qui soit une fonction partielle) ; ou alors, on peut être tenté de prendre l'intersection de toutes les parties A de X×Z telles que Ψ(A)⊆A (en prolongeant un peu intelligemment Ψ de 𝒟 à 𝒫(X×Z)), mais alors il n'est pas du tout évident que cette intersection soit une fonction. Non, vraiment, réfléchissez-y avant de lire la suite !

Voici maintenant une démonstration de (F$), que je trouve presque hallucinante, même s'il faut admettre qu'elle a une certaine beauté :

Démonstration de (F$) :

Montrons d'abord que si il existe une fonction partielle f∈𝒟 telle que Ψ(f)=f, ou même simplement Ψ(f)⊆f, alors il en existe une plus petite. Pour cela, il suffit de considérer l'intersection h de toutes les f telles que Ψ(f)⊆f (considérées comme des parties de X×Z) : dès lors qu'il existe au moins un f∈𝒟 tel que Ψ(f)⊆f, cette intersection h est bien définie et est bien un élément de 𝒟. Si Ψ(f)⊆f alors hf (puisque h est l'intersection des f), donc Ψ(h)⊆Ψ(f) (par croissance de Ψ), donc Ψ(h)⊆f (par transitivité), et comme ceci est vrai pour tous les f dont l'intersection est h, on a finalement Ψ(h)⊆h ; mais la croissance de Ψ donne alors aussi Ψ(Ψ(h))⊆Ψ(h), et du coup Ψ(h) est l'une des f qu'on a intersectées pour former h, et on a ainsi hΨ(h) ; bref, Ψ(h)=h, et h est à la fois le plus petit élément f∈𝒟 vérifiant Ψ(f)⊆f (de par sa construction) et le plus petit vérifiant Ψ(f)=f (puisqu'il vérifie cette propriété plus forte).

Reste à montrer qu'il existe bien une fonction partielle f telle que Ψ(f)=f, ou même simplement Ψ(f)⊆f. Pour cela, on introduit l'ensemble ℰ des f∈𝒟 qui vérifient Ψ(f)⊇f (inclusion dans le sens opposé du précédent !). Notons que ℰ n'est pas vide puisque ∅∈ℰ (où ∅ est la fonction vide, définie nulle part).

Soit maintenant 𝔐 l'ensemble des applications (totales !) T:ℰ→ℰ qui vérifient (i) T(f)⊇f pour tout f∈ℰ et (ii) si fg alors T(f)⊇T(g). Ainsi id∈𝔐 (trivialement) et Ψ∈𝔐 (par définition de ℰ et par croissance de Ψ) ; et si T,T′∈𝔐 on a T′∘T ∈ 𝔐 (en notant T′∘T la composée). L'observation suivante sera cruciale : si g∈ℰ et T,T′∈𝔐, alors on a à la fois (T′∘T)(g) ⊇ T(g) (d'après (i) pour T′) et (T′∘T)(g) ⊇ T′(g) (d'après (i) pour T et (ii) pour T′).

Affirmation : si g∈ℰ alors la réunion des T(g) pour tous les T∈𝔐 est, en fait, une fonction partielle. En effet, l'observation faite ci-dessus montre que si T,T′ ∈ 𝔐 alors les fonctions partielles T(g) et T′(g) sont toutes deux restrictions d'une même fonction partielle (T′∘T)(g), donc il ne peut pas y avoir de conflit entre leurs valeurs (au sens où si toutes les deux sont définies en un x∈ X, elles y coïncident) — c'est exactement ce qui permet de dire que la réunion est encore une fonction partielle. Notons U(g) := ⋃T∈𝔐(T(g)) cette réunion. On a au moins U(g)∈𝒟. Mais en fait, comme U(g) prolonge tous les T(g), la croissance de Ψ assure que Ψ(U(g)) prolonge tous les Ψ(T(g)), qui prolongent eux-mêmes les T(g) (puisque T(g) ∈ ℰ), bref Ψ(U(g)) ⊇ U(g) et ainsi U(g)∈ℰ.

Mais alors U∈𝔐 (on vient de voir que U est une fonction ℰ→ℰ, et les propriétés (i) et (ii) sont claires). En particulier, ΨU∈𝔐, donc (ΨU)(g) est l'une des T(g) dont U(g) est la réunion, et on a donc (ΨU)(g) ⊆ U(g), l'inclusion réciproque ayant déjà été vue (et de toute façon on n'en a pas besoin). On a donc bien trouvé une fonction partielle f := U(∅) telle que Ψ(f)⊆f (même Ψ(f)=f).

C'est quand même bizarrement compliqué, comme façon de faire ! (D'ailleurs, je veux quand même bien qu'on me confirme que c'est correct et compréhensible, comme démonstration.)

Bon, ceci étant, le David Madore étant un grand fan des ordinaux, on peut aussi procéder comme ceci :

Seconde démonstration de (F$) (utilisant les ordinaux) :

On pose f0 = ∅, et par induction sur l'ordinal α on définit fα+1 = Ψ(fα) et si δ est un ordinal limite alors fδ = ⋃γ<δ fγ. On montre simultanément par induction sur α que fα est bien définie, est une fonction partielle, et, grâce à la croissance de Ψ, prolonge fβ pour chaque β<α (c'est ce dernier point qui permet de conclure que ⋃γ<δ fγ est une fonction partielle lorsque δ est un ordinal limite : la réunion d'une famille totalement ordonnée pour l'inclusion de fonctions partielles est encore une fonction partielle). Les inclusions fβfα pour β<α ne peuvent pas être toutes strictes sans quoi on aurait une surjection d'un ensemble sur la classe des ordinaux. Il existe donc τ tel que fτ+1 = fτ, c'est-à-dire Ψ(fτ) = fτ. D'autre part, si Ψ(h) = h, alors par induction sur α on montre fαh pour chaque α (l'étape successeur étant que si fαh alors fα+1 = Ψ(fα) ⊆ Ψ(h) = h), donc en particulier fτh, et fτ est bien le plus petit f tel que Ψ(f) = f.

Oui, c'est beaucoup plus simple. Ça pourrait servir de pub pour les ordinaux, je devrais m'en réjouir.

Mais là, je me dis : ce n'est pas moral : l'énoncé élémentaire (F$), qui ne fait pas intervenir d'ordinaux, ne devrait pas en avoir besoin pour sa démonstration, et de fait, (P$) n'en avait pas besoin. Comment se fait-il que la démonstration de (P$) sans ordinaux se complique immensément quand on passe à (F$), alors qu'avec les ordinaux les quatre énoncés se démontrent exactement pareil (construire l'itération transfinie de Ψ, et constater que c'est l'objet recherché). J'ai passé beaucoup de temps à me gratter la tête sur comment « enlever » les ordinaux dans la démonstration ci-dessus, sans succès.

Il y a sans doute aussi moyen de s'en sortir en invoquant astucieusement le lemme de Zorn. Mais c'est encore pire, comme atteinte aux bonnes mœurs mathématiques : le résultat ne dépend en aucune manière de l'Axiome du Choix (et l'objet construit est complètement canonique), il est scandaleux de se servir du Choix pour abréger la démonstration. Au contraire, le genre de théorèmes de points fixes que j'ai cités peut servir à démontrer le lemme de Zorn à partir de l'Axiome du Choix.

J'ai aussi passé pas mal de temps à chercher à passer de (F) à (F$) un peu de la manière dont je suis passé de (P) à (P$) ci-dessus, là aussi sans succès (si on tente de définir Ψ₁(f) := fΨ(f), rien ne garantit que c'est une fonction ; si on cherche à se limiter aux f pour lesquels ç'en est une, il me semble que ça ne marche vraiment pas).

Mise à jour () : Fab, dans les commentaires, me fait remarquer à juste titre que l'énoncé (F), quoique juste, est, en fait, creux. En effet, soit Z est un singleton, auquel cas (F) est équivalent à (P) (toujours grâce à l'« astuce » consistant à remarquer qu'une fonction partielle XZ est alors essentiellement la même chose qu'une partie de X, à savoir la partie sur laquelle la fonction est définie). Soit Z est vide, auquel cas tout est trivial. Soit Z a strictement plus d'un élément, auquel cas le plus petit point fixe de Ψ est automatiquement la fonction vide. En effet, si Ψ(∅) est une fonction g non vide, disons g(x)=z avec xX et zZ, on considère h telle que h(x)=z′ où z′≠z (possible car Z n'est pas un singleton) : on a alors d'une part Ψ(h)⊇Ψ(∅)=g par croissance, et d'autre part Ψ(h)⊇h par progressivité, or g et h sont incompatibles en x, contradiction (c'est donc que Ψ(∅)=∅, et il est le plus petit point fixe de Ψ). Il n'était donc pas étonnant que je n'arrivasse pas à déduire (F$) de (F). Maintenant, je ne sais pas si cette remarque rend toute l'histoire plus claire ou encore plus mystérieuse…

Donc, quelque chose me gêne vraiment dans l'histoire, pas tellement au niveau mathématique mais au niveau métamathématique. Parfois l'histoire ne s'arrête pas à démontrer un théorème, mais à comprendre les différentes façons de le démontrer, et comment elles se relient les unes aux autres.

Mais il faut que j'admette que j'ai caché quelque chose dans l'histoire, parce que j'en sais plus que je ne l'ai dit : c'est le contenu de cet article d'Andrej Bauer et Peter LeFanu Lumsdaine (On the Bourbaki-Witt Principle in Toposes), duquel d'ailleurs (cf. leur théorème 3.2, qui n'est pas de ces auteurs mais que j'ai appris par eux) je tire essentiellement la première démonstration (« hallucinante ») de (F$) donnée ci-dessus. Pour décoder un peu ce qu'ils racontent, ils s'intéressent à des principes affirmant l'existence de points fixes d'opérateurs Ψ:𝒟→𝒟 (où 𝒟 est un ensemble partiellement ordonné) en supposant soit (i) que Ψ est progressif, i.e., xΨ(x) pour tout x, soit (ii) que Ψ est croissant, i.e., que xy implique Ψ(x)≤Ψ(y), et en supposant que 𝒟 admet des bornes supérieures soit (a) quelconques, soit (b) de parties dirigées (:=dans lesquelles un nombre fini quelconque d'éléments admettent toujours un majorant), soit (c) de chaînes (:=parties totalement ordonnées). Cela donne six principes de points fixes en combinant les hypothèses (i) et (ii) avec les hypothèses (a), (b) et (c) : parmi eux, (i.a) est trivial, (ii.a) et (ii.b) sont démontrables de façon « constructive » (valables dans un « topos élémentaire »), c'est-à-dire sans utiliser le tiers exclu ni l'Axiome de Remplacement[#2], tandis que ni (i.b) et (i.c) (qui sont équivalents, et qu'ils appellent théorème de Bourbaki-Witt) ni (ii.c) (qu'ils appellent théorème de Knaster-Tarski) ne sont démontrables « constructivement », et ce défaut de constructivité passe par une question d'existence d'assez d'ordinaux (et la démonstration non-« constructive » se fait par induction transfinie exactement comme ci-dessus). • Le rapport avec ce que je disais au-dessus, c'est que l'ensemble des parties d'un ensemble X vérifie l'hypothèse (a) d'existence de bornes supérieures quelconques, tandis que l'ensemble des fonctions partielles XZ vérifie seulement (b) (et du coup (c) aussi, qui est plus faible). Ceci fournit une certaine lumière sur le problème : d'abord, ceci « explique » pourquoi (P) est plus simple que (P$), parce que la démonstration de l'existence d'un point fixe dans le cas (i.a) est triviale, on prend juste le plus grand élément de 𝒟, alors que dans le cadre (ii.a) il faut réfléchir un petit peu plus ; d'autre part, les ordinaux permettent d'utiliser la démonstration de (ii.c), tandis que si on veut éviter le Remplacement qu'ils utilisent intrinsèquement, il faut passer par (ii.b), or l'hypothèse (b) est plus délicate à mettre en œuvre que (c) (on n'a pas juste à prendre des unions de familles totalement ordonnées de fonctions, mais des familles dirigées de fonctions, et c'est ce que fait la démonstration qui explique que T(g) et T′(g) sont toutes deux restrictions d'une même fonction partielle (T′∘T)(g), donc il ne peut pas y avoir de conflit entre leurs valeurs). • Mais ceci ne clarifie pas complètement les choses, parce que le cadre dans lequel je me place est quand même différent : d'abord, je n'ai aucune objection à utiliser le tiers exclu, d'autre part, pour ce qui est de (F) je suis prêt à prendre (i) et (ii) comme hypothèses, pas juste l'une des deux, ensuite je me place dans un cadre où il y a des bornes inférieures représentées par les intersections, et de fait, je demande le plus petit point fixe, et enfin, il est parfaitement imaginable qu'une démonstration beaucoup plus simple existe dans le cadre concret d'un ensemble de fonctions partielles que dans le cadre abstrait d'un ensemble partiellement ordonné fût-il complet en tel ou tel sens. Donc je ne peux pas dire que j'aie la clé du mystère métamathématique.

[#2] En fait, je crois que ce n'est pas tant un question de tiers exclu, et moralement la démonstration vers les ordinaux ne l'utilise pas plus que les autres, que de Remplacement, qui fait marcher les ordinaux, donc constructif n'est peut-être pas le bon terme (c'est le terme standard, mais il suggère la mauvaise idée — moralement, les ordinaux même immenses sont parfaitement constructifs, c'est juste que le cadre métamathématique qu'on utilise pour faire des maths constructives limite aussi les ordinaux, et du coup on en est venu à utiliser un même terme pour une combinaison de choses différentes). Mais j'avoue que mes idées sur le rôle de Remplacement de l'affaire sont très incertaines : notamment, est-ce que l'énoncé (ii.c) si Ψ:𝒟→𝒟 est une application croissante où 𝒟 est un ensemble partiellement ordonné dans lequel toutes les chaînes admettent une borne supérieure, alors Ψ a un point fixe est un théorème de la théorie des ensembles de Zermelo ?

(mercredi)

Jouons un peu avec les subordonnées relatives

L'entrée précédente contenait le bout de phrase

…dans le cadre d'un cours dont j'enseigne à un groupe…

que j'affirme être correcte (j'enseigne à un groupe [d'élèves] de ce cours) mais qui a fait réagir le genre de grincheux dont j'imagine qu'ils doivent lire des blogs sans aucun intérêt pour le fond, par simple plaisir de pinailler sur la grammaire. Penchons-nous donc un instant sur les subordonnées relatives en français. [En vérité, l'avant-dernière phrase est surtout là pour fournir quelques exemples intéressants in situ de subordonnées compliquées : la phrase que j'affirme être correcte et les grincheux dont j'imagine qu'ils doivent lire des blogs blablabla.]

La subordonnée relative, dans les langues que je connais assez bien pour m'exprimer à leur sujet, a pour fonction de prendre deux phrases faisant intervenir le même concept, plus exactement un groupe nominal (ou un pronom), et d'imbriquer une dans l'autre (l'imbriquée devient donc la proposition subordonnée tandis que l'imbriquante devient la proposition principale) en explicitant le fait que c'est bien le même concept qui intervient dans les deux phrases. Exemple extrêmement simple :

{J'aime la maison} # {Je vois la maison} → {J'aime la maison {que je vois}}

(L'opération n'est pas commutative : dans l'autre sens on obtiendrait Je vois la maison {que j'aime}, ce qui a un sens subtilement différent, mais je vais y revenir.)

Le mot que indiqué en rouge est le pronom relatif ; il a un double rôle : (A) introduire la subordonnée (marquer son début, c'est-à-dire, débuter l'imbrication) et (B) préciser la fonction occupée par le groupe commun (l'antécédent de la relative) dans cette subordonnée. On va voir ci-dessous que ces rôles sont un peu en conflit et qu'il serait beaucoup plus clair d'avoir deux mots séparés pour les remplir. Le point à souligner dans (B) est que normalement en français la fonction d'un groupe nominal est indiquée par l'ordre des mots, mais comme on a réordonnée les mots pour mettre le pronom relatif en premier (à cause de son rôle (A)), cette fonction n'est plus apparente, et on la manifeste, à la place, par la forme du pronom. Pour reprendre un exemple très simple, comparer :

{Le garçon fait de la muscu} # {Le garçon drague Kévin} → {Le garçon {qui drague Kévin} fait de la muscu}

{Le garçon fait de la muscu} # {Kévin drague le garçon} → {Le garçon {que drague Kévin} fait de la muscu}

— la fonction (sujet ou objet) du groupe nominal commun dans la seconde phrase est indiquée par son emplacement quand la phrase est autonome, mais par la forme du pronom relatif (reste de déclinaison latine) quand elle est transformée en subordonnée.

Ajout () : J'aurais sans doute dû signaler que dans la seconde version, le garçon {que drague Kévin} fait de la muscu, on peut aussi utiliser l'ordre des mots le garçon {que Kévin drague} fait de la muscu, alors que dans la première il n'y a pas de choix : on peut donc préciser la fonction dans la subordonnée par le choix du pronom ou par l'ordre des mots. Il faudrait chercher un exemple où on ne peut pas jouer avec l'ordre des mots.

✱ Le français a plusieurs systèmes de pronoms relatifs (formant un tout assez incohérent) : à coté de qui, que et de quelques autres, on a tout un jeu de variations de lequel, laquelle, lesquel(le)s, l'emploi de ces deux systèmes étant subtilement et incompréhensiblement différent. Prenons par exemple :

{Ce système est assez incohérent} # {Je mesure la complexité de ce système}

→ (i) {Ce système {dont je mesure la complexité} est assez incohérent}

→ (ii) {Ce système {duquel je mesure la complexité} est assez incohérent}

mais

{Ce système est assez incohérent} # {Je suis confronté à la complexité de ce système}

→ (iii) {Ce système {dont je suis confronté à la complexité} est assez incohérent}

→ (iv) {Ce système {à la complexité duquel je suis confronté} est assez incohérent}

Dans la phrase (iv), le pronom relatif duquel prend une place différente (celle qui correspond à sa fonction dans la subordonnée) sans doute selon la logique que le rôle (B) d'indiquer clairement comment le groupe commun s'articule dans la subordonnée devient prépondérant sur le rôle (A) d'introduire la subordonnée, qui, ici, est en quelque sorte dévolu à la préposition à ; en revanche, dans (i)–(iii), le pronom relatif se place bien en premier pour tenir son rôle (A) (encore que je pourrais défendre la phrase ce système {la complexité duquel je mesure} est assez incohérent). Les grincheux qui ont critiqué la phrase de l'entrée précédente citée en tout premier dans cette entrée-ci pensent peut-être que (iii) est incorrecte vu qu'elle est construite selon exactement le même modèle (ce système {dont je suis confronté à la complexité} est assez incohérent et dans le cadre d'un cours {dont j'enseigne à un groupe}). Je sais pourtant que ce type de tournure est employé non seulement par moi mais par quantité d'autres locuteurs natifs du français et que je l'ai relevé chez les meilleurs auteurs — comme on le comprend à la lecture de la présente entrée, j'aime bien analyser mentalement la syntaxe des phrases que j'entends —, donc je suppose que ça fait partie des délires des linguistes prescriptivistes qui ont décidé que ça ne sa faisait pas selon leurs règles dont on voit bien, et c'est une des choses que je veux démontrer ici, qu'elles sont incodifiables. [Tiens, encore une phrase qui se finit par une subordonnée intéressante.]

✱ Tout ce système de pronoms relatifs et de syntaxes de subordination est, il faut bien le dire, invraisemblablement merdique, et une des difficultés qui va survenir est qu'il n'y a tout simplement pas assez de pronoms relatifs pour indiquer toutes les fonctions que pourrait occuper le groupe commun dans la phrase (qu'on transforme en) subordonnée. La bonne façon de faire, si on devait inventer une langue logique et claire, serait de procéder comme on fait en mathématiques, à savoir introduire une variable de liaison (genre x) répétée deux fois dans les deux fonctions et d'utiliser un marqueur unique (disons tel que) pour le rôle (A) : autrement dit, cela donnerait quelque chose comme

{Le garçon fait de la muscu} # {Le garçon drague Kévin} → {Le garçon x {tel que x drague Kévin} fait de la muscu}

{Le garçon fait de la muscu} # {Kévin drague le garçon} → {Le garçon x {tel que Kévin drague x} fait de la muscu}

C'est-à-dire que la notion de subordonnée relative est essentiellement (à des subtilités sémantiques sur lesquelles je vais revenir) le tel que des matheux avec une syntaxe alambiquée.

J'ignore s'il y a des langues naturelles qui ont un tel concept de « variable locale », c'est-à-dire de pronoms (pronoms locaux ?) dont un bout de phrase pourrait affecter la valeur dont un autre bout de phrase pourrait la reprendre. [Remarquer au passage un autre type de difficulté subtile dans la dernière relative de la phrase précédente.] L'avantage de ce système est qu'il permet des imbrications arbitrairement complexes :

{Ce système est assez incohérent} # {Je suis confronté à la complexité de ce système} → {Ce système x {tel que je suis confronté à la complexité de x} est assez incohérent}

{J'aime les subordonnées} # {J'écris une entrée dans mon blog pour me plaindre de la difficulté à combiner des phrases d'une complexité arbitrairement grande en subordonnées}

→ {J'aime les subordonnées {j'écris une entrée dans mon blog pour me plaindre de la difficulté à combiner des phrases d'une complexité arbitrairement grande en lesquelles}} (†)

→ {J'aime les subordonnées x {telles que j'écris une entrée dans mon blog pour me plaindre de la difficulté à combiner des phrases d'une complexité arbitrairement grande en x}}

— y compris reprendre des groupes qui sont eux-mêmes cachés dans une une subordonnée de la phrase qu'on cherche à subordonner :

{Le livre est sur la table} # {Je vois {que tu as fini le livre}}

→ {Le livre {que je vois {que tu as fini}} est sur la table} (passe encore)

→ {Le livre x {tel que je vois {que tu as fini x}} est sur la table}

Mais :

{Les gens sont maintenant vieux} # {{Quand les gens étaient petits} la seconde guerre mondiale s'est terminée}

→ {Les gens {{quand lesquels étaient petits} la seconde guerre mondiale s'est terminée} sont maintenant vieux} (†) (Oui, je sais bien que sur cet exemple comme sur quantité d'autres on peut trouver une façon de reformuler la phrase : vu que {quand les gens étaient petits} la seconde guerre mondiale s'est terminée équivaut essentiellement à les gens étaient petits {quand la seconde guerre mondiale s'est terminée}, la phrase impossible ci-dessus peut se redire en les gens {qui étaient petits {quand la seconde guerre mondiale s'est terminée}} sont maintenant vieux — phrase tout à fait naturelle en français, mais ce n'est plus la même syntaxe.)

→ {Les gens x {tels que {quand x étaient petits} la seconde guerre mondiale s'est terminée} sont maintenant vieux}

Cela marche(rait) même quand la subordonnée-dans-la-subordonnée est elle-même relative :

{Je suis amoureux de Kévin} # {Le garçon {qui drague Kévin} fait de la muscu} → {Je suis amoureux de Kévin {que le garçon {qui drague} fait de la muscu}} (†?) (Oui, de nouveau, on peut trouver une façon de retourner les choses : en remplaçant le garçon {qui drague Kévin} fait de la muscu par le garçon {qui fait de la muscu} drague Kévin, ce qui est presque pareil, on transforme la phrase impossible en je suis amoureux de Kévin {que le garçon {qui fait de la muscu} drague} — mais on a subtilement retourné syntaxe de la phrase.)

{Je suis amoureux de Kévin} # {Le garçon {qui drague Kévin} fait de la muscu} → {Je suis amoureux de Kévin k {tel que le garçon {qui drague k} fait de la muscu}}

— voire, en utilisant le même mécanisme à tous les niveaux :

{Je suis amoureux de Kévin} # {Le garçon x {tel que x drague Kévin} fait de la muscu} → {Je suis amoureux de Kévin k {tel que le garçon x {tel que x drague k} fait de la muscu}}

Les matheux ont l'habitude de voir et de comprendre des phrases avec des introductions de variables ainsi imbriquées (les réels t {tels que les réels x {tels que x>t} vérifient x≥0} vérifient t≥0, construite selon le même modèle que la phrase ci-dessus, et par ailleurs juste). Comme je le disais, je ne sais pas si une langue naturelle a un système de ce genre (avec vraiment plusieurs jeux de variables), mais je suis tout à fait persuadé qu'il y a des langues avec une notion de subordonnée relative et qui, au moins, séparent en deux mots les rôles (A) et (B) du pronom relatif français.

✱ Mais même en français, en fait, dans le cas fréquent où la phrase à subordonner fait intervenir un verbe du genre penser que ou affirmer que introduisant le groupe commun, on peut souvent utiliser une « astuce » qui consiste à (A) introduire la subordonnée par dont dans un sens de au sujet duquel [je peux faire l'affirmation suivante] et d'utiliser ensuite un pronom normal (il, le) pour la fonction (B) (à la place de la variable x de mes exemples précédents). Ceci permet de former des subordonnées compliquées qui ne seraient autrement pas vraiment possibles avec la syntaxe du français. Démonstration :

{Cette mesure ne sera pas adoptée} # {Je pense {que cette mesure est liberticide}}

• en essayant naïvement :

→ {Cette mesure {je pense {que laquelle est liberticide}} ne sera pas adoptée} (†)

• en remaniant la syntaxe grâce à la magie des propositions infinitives (changer je pense {que cette mesure est liberticide} en je pense {cette mesure être liberticide}) :

→ {Cette mesure {que je pense {être liberticide}} ne sera pas adoptée}

• en utilisant l'« astuce » que je viens d'expliquer :

→ {Cette mesure {dont(A) je pense {qu'elle(B) est liberticide}} ne sera pas adoptée}

• en utilisant le mécanisme général exposé plus haut :

→ {Cette mesure x {telle que(A) je pense {que x(B) est liberticide}} ne sera pas adoptée}

Ici j'ai choisi un exemple où on peut s'en sortir avec la magie des infinitives, mais si on envisage une phrase comme cette mesure {dont je suis persuadé {que les Français l'appellent de leurs vœux}} ne sera pas adoptée, on voit qu'on peut arriver à des choses assez complexes et néanmoins tout à fait compréhensibles grâce à l'« astuce du dont ». Je ne sais pas si ce type de tournure (dont je raffole de l'emploi, et il y en a plusieurs exemples dans cette entrée) a un nom classique, mais elle est extrêmement pratique.

Clarification () : Je ne prétends pas que cette « astuce » repose sur une anomalie de syntaxe : je réécris simplement la phrase à subordonner, par exemple je pense {que cette mesure est liberticide} peut être transformé en je pense de cette mesure {qu'elle est liberticide} (c'est une façon de donner à cette mesure une fonction « bidon » mais non imbriquée), et du coup on peut faire la transformation en cette mesure {dont je pense {qu'elle est liberticide}} ne sera pas adoptée. Néanmoins, ce type de réécriture est très général (dès qu'on a affaire à un verbe comme penser, croire, affirmer, etc., où on peut penser, croire ou affirmer quelque chose [au sujet] de quelque chose). Idéalement, il faudrait en français un « complément bidon » qui n'aurait aucun sens (une préposition qui servirait juste à introduire un groupe nominal à ignorer), ce qui permettrait de réaliser l'astuce dans tous les cas : la construction ici est ce qui s'en approche le plus.

✱ Il faut que j'évoque encore une difficulté bizarre de la syntaxe française (ou plutôt, du fait de fusionner les rôles (A) et (B) du pronom relatif), c'est quand le même groupe occupe deux fonctions distinctes dans la phrase à subordonner. Par exemple :

{J'aime les concepts} # {Le nom des concepts éclaire les concepts} → {J'aime les concepts x {tels que le nom de x éclaire x}}

{J'aime les concepts} # {Le nom des concepts éclaire les concepts} [≡ {Le nom des concepts les éclaire}] → {J'aime les concepts {dont le nom les éclaire}}

{J'aime les concepts} # {Le nom des concepts éclaire les concepts} [≡ {Leur nom éclaire les concepts}] → {J'aime les concepts {que leur nom éclaire}}

En principe, il n'y a aucune difficulté particulière : les deux phrases j'aime les concepts {dont le nom les éclaire} et j'aime les concepts {que leur nom éclaire} sont tout à fait conformes à la syntaxe générale, et essentiellement équivalentes. (Remarquons que selon l'« astuce du dont » évoquée plus haut, on pourrait aussi défendre : j'aime les concepts {dont leur nom les éclaire}.) En pratique, on est généralement gêné quand on rencontre l'une de ces formulations, parce qu'on a dans le cerveau quelque chose qui hurle non, on n'a pas le droit de reprendre l'antécédent de la relative par autre chose que le pronom relatif !, et du coup, on a la sensation que quelque chose « ne va pas » et on cherche à éliminer les deux occurrences, malheureusement ni la phrase j'aime les concepts {dont le nom éclaire} [éclaire quoi ?] ni j'aime les concepts {que le nom éclaire} [le nom de quoi ?] n'a le sens qu'on veut ! Et du coup, quand les deux fonctions sont tout à fait parallèles, alors cette fois on a tendance à « faire d'une pierre deux coups » (ou d'un pronom relatif deux emplois) et ne reprendre qu'une fois :

{J'aime les concepts} # {Le nom des concepts éclaire le sens des concepts} → {J'aime les concepts x {tels que le nom de x éclaire le sens de x}}

• Logiquement on devrait écrire :

{J'aime les concepts} # {Le nom des concepts éclaire le sens des concepts} [≡ {Le nom des concepts éclaire leur sens}] → {J'aime les concepts {dont le nom éclaire leur sens}}

{J'aime les concepts} # {Le nom des concepts éclaire le sens des concepts} [≡ {Leur nom éclaire le sens des concepts}] → {J'aime les concepts {dont leur nom éclaire le sens}}

• Mais en pratique, on écrit plutôt, « d'une pierre deux coups » :

{J'aime les concepts} # {Le nom des concepts éclaire le sens des concepts} → {J'aime les concepts {dont le nom éclaire le sens}}

Pourquoi tant de haine ?

✱ Je peux aussi rapprocher de la difficulté précédente le problème particulier posé par la situation où la phrase à subordonner est en plusieurs morceaux qui vont logiquement ensemble mais où le groupe commun qui va devenir antécédent n'apparaît que dans un de ces morceaux. Je donne un exemple :

{Voici le texte} # ({Je vais étudier la syntaxe du texte,} et {j'ai l'intention de la comprendre parfaitement à la fin}) → {Voici le texte {dont je vais étudier la syntaxe,} et {dont j'ai l'intention de la comprendre parfaitement à la fin}}

— ici la difficulté est que le texte n'a aucune fonction dans la deuxième proposition de la phrase à subordonner (autrement que comme déterminant de la syntaxe qui est repris par un pronom). Du coup, on ne sait vraiment pas quel pronom relatif choisir (j'ai choisi dont un peu selon la logique de l'« astuce » générale évoquée plus haut : il faut imaginer un pronom relatif qui n'introduit aucune fonction particulière). Bien sûr, on peut faire une subordonnée unique (voici le texte {dont je vais étudier la syntaxe, et j'ai l'intention de la comprendre parfaitement à la fin}), mais selon la longueur des termes cela peut être plus ou moins maladroit. Le lecteur attentif aura remarqué que j'ai déjà utilisé dans cette entrée une tournure comme celle de la phrase ci-dessus.

✱ J'ai pour l'instant été assez vague sur le sens des subordonnées, mais il faut préciser qu'il y a deux sens principaux la frontière entre lesquels n'est pas toujours parfaitement nette : dans un premier sens, qu'on appelle restrictif ou déterminatif, il faut comprendre que les foobars {tels que blabla} limitent, à l'intérieur des foobars, ceux qui vérifient blabla, tandis que dans le second sens, qu'on appelle non-restrictif ou explicatif, il faut comprendre qu'on apporte deux informations sur l'ensemble de tous les foobars. La différence de sens, qui est en gros celle entre ∀x(P(x)⇒Q(x)) et ∀x(P(x)∧Q(x)), sauf que les choses ne sont jamais aussi claires dans les langues naturelles, tend à être indiquée, au moins en français et en anglais, par une virgule :

{Les lecteurs de ce blog me comprendront bien} # {Les lecteurs de ce blog maîtrisent la logique}

→ {Les lecteurs de ce blog {qui maîtrisent la logique} me comprendront bien} (i.e., parmi les lecteurs de blog, le sous-ensemble de ceux qui maîtrisent la logique me comprendra bien)

→ {Les lecteurs de ce blog, {qui maîtrisent la logique}, me comprendront bien} (i.e., les lecteurs de blog maîtrisent la logique et me comprendront bien)

La différence est moins claire au singulier (si de toute façon il existe un unique foobar, étant donné que le langage naturel a horreur de parler de l'ensemble vide, cela n'a pas trop de sens de se demander si on restreint son ensemble ou si on apporte une information de plus à son sujet). Dans toute la discussion précédente j'ai volontairement ignoré la différence entre ces deux sens puisque je me préoccupais uniquement de la syntaxe du mécanisme de subordination, pas de son sens.

La virgule censée marquer la différence peut disparaître à cause d'une incise : si j'écris les lecteurs de ce blog, je veux parler du mien, qui maîtrisent la logique, ce domaine si important, me comprendront bien, on ne sait plus dans quel cas de figure on est. À l'oral on la marque par une différence d'intonation, qui peut être plus ou moins évidente ou subtile selon le contexte, le locuteur, etc. En allemand (mais pas en néerlandais !, du moins il me semble), à l'écrit, toute subordonnée est introduite par une virgule, et du coup la différence entre le sens restrictif et non-restrictif des relatives n'est pas marquée : cela peut être gênant pour la compréhension, et c'est d'ailleurs étonnant pour une langue habituellement si précise (je suppose qu'un grammairien prescriptiviste imbécile a un jour décidé que la virgule avant les subordonnées était une bonne chose et qu'il allait la décréter obligatoire, sans réfléchir aux conséquences que cela entraînait) ; mais on peut parfois s'en sortir en changeant le démonstratif (par exemple derjenige suggère fortement le sens restrictif) et/ou le pronom relatif (welcher au lieu de der).

✱ Il faut que je dise encore un mot des subordonnées qui ne sont pas des relatives, que le français appelle subordonnées conjonctives, même si ce n'est sans doute pas une bonne idée de regrouper dans le même sac celles qui occupent une fonction essentielle dans la principale/subordonnante (comme je vois {que tu as embrouillé tes lecteurs}, à ne pas confondre avec la relative dans je vois les lecteurs {que tu as embrouillés}) et celles qui marquent une circonstance non-essentielle (comme tu devrais lire plus lentement {quand les choses sont compliquées}). Le sujet est un peu trop vaste pour que j'en parle en général, mais je veux évoquer un type particulier de subordonnées dont je crois qu'on ne les classe pas avec les relatives [que je crois qu'on ne classe pas avec les relatives ?], à savoir celles du discours indirect : il s'agit de phrases comme je veux savoir {qui tu as embrouillé} ou je veux savoir {quel lecteur tu as embrouillé}, qui sont différentes à la fois des relatives ((1) je comprends les lecteurs {que tu as embrouillés} : la subordonnée qualifie le groupe nominal les lecteurs) et des conjonctives « ordinaires » ((2) je comprends {que tu as embrouillé tes lecteurs} : la totalité du fait désigné par la subordonnée remplit la fonction d'objet dans la principale), puisqu'ici c'est l'identité de quelque chose, ou la réponse à une question indirecte, qui joue une fonction dans la principale ((3) je comprends {qui tu as embrouillé} : l'objet de comprendre n'est ni la personne qualifiée par la subordonnée comme dans l'exemple (1), ni le fait tout entier comme dans l'exemple (2), c'est l'identité de la personne, i.e., la réponse à la question qui as-tu embrouillé ?).

La raison pour laquelle je fais ce distinguo est qu'il y a des situations où on peut avoir ambiguïté. En effet, une subordonnée relative peut occuper toute seule une fonction dans la phrase principale, parce que celui (la personne) dans celui qui peut être omis : dans {qui veut voyager loin} ménage sa monture, il n'y a pas d'antécédent explicite à la subordonnée, il faut comprendre celui / la personne {qui veut voyager loin} ménage sa monture. De façon illogique, d'ailleurs celui que peut aussi se dire qui, c'est-à-dire que la forme qui du pronom est relatif est utilisée pour marquer l'omission de celui plutôt que pour indiquer la fonction dans la subordonnée. Et là les choses deviennent dangereusement confusantes : dans la phrase j'ai rencontré {qui tu aimes} on a affaire à une subordonnée relative et le sens est j'ai rencontré celui {que tu aimes} (l'objet de rencontrer est la personne désignée par la relative), alors que dans la phrase je sais {qui tu aimes}, on a une interrogative indirecte et l'objet de savoir est l'identité de la personne en question. Du coup, la phrase je vois qui tu aimes peut se comprendre de deux façons différentes en français : soit avec une relative je vois {qui tu aimes} c'est-à-dire je vois celui {que tu aimes}, soit avec une interrogative indirecte je vois {qui tu aimes}, i.e., je vois (=je comprends) l'identité de la personne que tu aimes. (Les deux sont d'ailleurs bien différentes de je vois {que tu aimes}.)

Si mon latin n'est pas trop pourri, je vois {qui tu aimes} (avec une relative) doit se dire video [eum] {quem amas} alors que je vois {qui tu aimes} (avec une interrogative indirecte) doit se dire video {quem ames}, la différence venant du fait que les interrogatives indirectes, en latin, prennent un verbe au subjonctif. (C'est en réfléchissant à ce que cela signifiait que je suis tombé sur cet exemple.)

Mais le plus bizarre, c'est le ce que du français : il peut s'analyser comme le pronom démonstratif neutre ce suivi du pronom relatif que, mais aussi comme un pronom interrogatif ce que (enfin, une « locution pronominale » interrogative, si on veut être pédant), auquel cas le ce est impossible à analyser autrement que comme un bout du tout, sans doute apparu par confusion avec la situation du pronom relatif. Ceci fait que la phrase j'ignore ce qu'il me dit peut s'analyser, exactement comme je vois qui tu aimes, de deux façons différentes : soit avec une relative, j'ignore ce {qu'il me dit} (c'est-à-dire qu'il me dit quelque chose, que je l'entends peut-être et que je le comprends peut-être mais que je décide d'ignorer cette chose qu'il me dit ; pour souligner : j'ignore ce qu'il me dit, je n'en tiens aucun compte), ou bien avec une interrogative, j'ignore {ce qu'il me dit} (c'est-à-dire que je suis ignorant de l'identité de ce qu'il me dit, par exemple parce que je ne l'entends pas : j'ignore la réponse à la question que me dit-il ? ; pour souligner : j'ignore ce qu'il me dit, je ne sais même pas quelle langue il parle). De même : je vois ce {que tu aimes} (avec une relative), i.e. je vois la chose que tu aimes, est différent de je vois {ce que tu aimes}, i.e., je vois (=je comprends) l'identité de la chose que tu aimes ; si mon latin n'est pas trop pourri, video [id] {quod amas} contre video {quid ames} (sur ce cas précis, le pronom aussi est différent). (De nouveau, les deux sont bien différentes de je vois {que tu aimes}.) La même ambiguïté doit exister pour ce qui. Mais il faut remarquer que parfois la différence sémantique est fine comme une lame de rasoir : entre les deux analyses possibles de j'ai entendu ce qu'il disait (relative ou interrogative indirecte, j'ai entendu la parole qu'il disait ou j'ai entendu l'identité de ce qu'il disait, audivi {quod dicebat} ou audivi {quid diceret} — je crois que le latin va nettement préférer l'interrogative), le sens est presque exactement le même, et c'est sans doute ce qui fait qu'il y a eu confusion.

✱ Ajout () : suite à une question/remarque intéressante en commentaire, il faut que je dise encore un mot sur le cas du français. Il me semble que ce même mot peut introduire (1) une subordonnée relative, comme dans voici l'endroit { nous nous sommes rencontrés}, même si dans ce cas la nature exacte de la phrase subordonnée n'est pas entièrement claire (nous nous sommes rencontrés à cet endroit ? ou en cet endroit ?), peut-être (2) une subordonnée conjonctive circonstancielle (i.e., non-essentielle), comme dans je reviens { nous nous sommes rencontrés}, analyse que je calque sur le modèle de j'étais heureux {quand nous nous sommes rencontrés}, mais on pourrait aussi préférer l'analyser comme une relative portant sur un adverbe implicite, i.e., je reviens [] { nous nous sommes rencontrés} comme je revois [celui] {qui nous a rencontrés}, ou enfin (3) une interrogative indirecte, comme je sais { nous nous sommes rencontrés}. • Les cas (1) et (3) sont assez peu problématiques, même si on peut certainement fabriquer des phrases ambiguës comme je l'ai fait au point précédent avec qui et ce que. En revanche, la question de savoir si je reviens où nous nous sommes rencontrés doit s'analyser comme une subordonnée relative avec un implicite ou comme une subordonnée circonstancielle de lieu ressemble à une question byzantine : apparemment les grammaires françaises (du moins celles que je trouve en ligne) ont choisi l'analyse comme une relative (et vont jusqu'à nier l'existence des subordonnées circonstancielles de lieu), mais aucune en prend le soin d'expliquer pourquoi cette analyse leur semble préférable (ou si c'est un choix purement arbitraire), on a l'impression que c'est comme ça semble être un argument suffisant dans le monde bizarre de ces grammaires. • En tout état de cause (et indépendamment de l'analyse qu'on en fait), j'ai toujours été choqué par le caractère hideusement asymétrique de la manière dont le français exprime les subordonnées indiquant le lieu et le temps, par exemple si je compare : d'une part, je serai présent où tu auras besoin de moi (peu importe qu'on l'analyse d'une manière ou d'une autre) avec je serai présent quand tu auras besoin de moi (l'analyse est forcément je serai présent {quand tu auras besoin de moi}), et d'autre part, je serai présent à l'endroit { tu auras besoin de moi} avec je serai présent au moment { tu auras besoin de moi}. Pourquoi dans un cas exprime-t-on le lieu avec et le temps avec quand alors que dans le second on exprime les deux avec  ? C'est peut-être un argument (celui que les grammaires omettent d'expliciter !) pour défendre l'analyse de je serai présent où tu auras besoin de moi comme une relative, mais en tout cas c'est une vraie bizarrerie du français. (En anglais, on dit fort logiquement : the place where you need me and the time when you need me, complètement parallèle de I am where you need me, when you need me, et il n'y a donc, en anglais, aucune raison de douter que l'analyse de where soit différente de celle de when.)

Il reste encore un certain nombre de subtilités que je n'ai pas évoquées, mais je crois que je vais m'en tenir là. Je vous laisse imaginer, cependant, à quel point j'ai pu emmerder mes instituteurs et profs de français (et d'autres langues, d'ailleurs) au collège et lycée, à explorer systématiquement les exemples tordus, les constructions bizarres, les cas non couverts par les règles qui venaient d'être énoncées, etc.

(samedi)

Petites notes sur la calculabilité, et quelques remarques à ce sujet

Je donnais jeudi matin une très courte[#] introduction à la calculabilité, dans le cadre d'un cours intitulé Théorie des Langages (donc un sujet plutôt connexe que contenant) dont j'enseigne à un groupe ; des circonstances anecdotiques (des feutres manquants[#2] au début de la séance, les élèves qui filent pour aller à un partiel à la fin) ont fait que je n'ai pas pu la finir correctement. J'ai donc envoyé des notes écrites[#3] aux élèves, auxquelles je n'ai pas résisté à la tentation d'ajouter quelques compléments en petits caractères. Comme ces notes (qui sont très basiques et passablement informelles même par rapport à ce que j'ai pu raconter sur le sujet sur ce blog) peuvent peut-être intéresser d'autres gens, je les mets en ligne ici. L'approche choisie consiste à ne pas chercher à définir formellement ce qu'est un algorithme (que ce soit par une machine de Turing ou autrement), vu que de toute façon on ne demandera à personne de programmer une machine de Turing, et pédagogiquement il semble que si on formalise un modèle de calcul, cela paralyse les étudiants au point qu'ils ne comprennent plus la notion d'algorithme alors qu'en entrant ils savaient.

[#] Et je trouve véritablement triste que dans une grande école dont l'informatique est une des spécialités, le seul contact que tous les élèves auront avec des notions aussi fondamentales que le problème de l'arrêt ou la notion de problèmes décidable et semi-décidable, c'est une séance d'une heure et demie dans le cadre d'un cours plutôt consacré à autre chose (et sur laquelle il est donc difficile de les interroger à l'examen).

[#2] Obtenir des feutres qui marchent au début de chaque cours peut être une véritable quête du graal.

[#3] Ils ont aussi un poly de cours (il n'a pas l'air d'être disponible publiquement), mais j'ai suivi une présentation différente dans mon exposé, suivant le principe qu'on comprend parfois mieux quand les choses sont expliquées deux fois de façon différente, et du coup j'ai repris mes notations dans ces notes.

Mais même en racontant des choses très basiques, on peut apprendre des choses ou s'éclaircir les idées. Notamment sur deux points, tous deux plus ou moins liés à l'énumération φ0,φ1,φ2,… des fonctions calculables partielles ℕ⇢ℕ. Il faut comprendre qu'on numéroté les programmes, par exemple par taille puis par ordre lexicographique, et que φe(n1,…,nk) est le résultat de l'exécution du e-ième programme auquel on fournit les arguments n1,…,nk, la valeur étant indéfinie si le programme ne (s'exécute pas correctement ou) ne termine pas. Un point important est qu'il existe un programme universel, c'est-à-dire que la fonction (e,n) ↦ φe(n) est elle-même calculable (informatiquement, cela signifie qu'on peut écrire un « interpréteur », qui prend un programme e et un paramètre n et exécute le programme sur cette entrée ; philosophiquement, cela signifie que le fait d'exécuter un algorithme est lui-même algorithmique). Les deux points qui m'avaient un peu échappés sont les suivants :

✱ Le premier point concerne le théorème s-m-n de Kleene. Si h(m,n)=φe(m,n) est une fonction calculable des deux variables m,n, alors pour chaque valeur de m elle est calculable dans la variable n : ça c'est plus ou moins une évidence ; mais ce qui l'est moins, c'est qu'on peut algorithmiquement fabriquer un indice s(e,m) pour cette fonction, au sens où φs(e,m)(n) = φe(m,n) avec s une fonction calculable — c'est ça que dit le théorème s-m-n. Informatiquement, cela signifie qu'il y a une transformation algorithmique (le s en question) qui prend un programme e prenant deux arguments m et n (ou en fait, deux jeux d'arguments), et une valeur à donner au premier, et qui renvoie un nouveau programme s(e,m) où ces arguments ont été fixés à cette valeur. Dans toute formalisme de calcul précis (que ce soit les machines de Turing, ou un langage de programmation réel), c'est plus ou moins évident — dans un langage de programmation fonctionnel, par exemple, cela signifie curryfier la fonction et appliquer à une constante — et la fonction s sera mieux que calculable (elle sera primitive récursive, et certainement beaucoup mieux que ça, parce que ce n'est pas un problème algorithmiquement difficile de substituer une valeur dans un programme !). Mais comme je n'introduisais pas de modèle de calcul précis, je me suis demandé si ça pouvait se démontrer in abstracto, à partir de la simple existence de l'énumération des fonctions calculables partielles et l'existence d'un programme universel.

La réponse est non, il existe des numérotations des fonctions calculables partielles qui vérifient le théorème d'universalité mais pas le théorème s-m-n. Un contre-exemple est fourni en définissant à partir d'une numérotation standard φe une nouvelle numérotation ψv+1,e(0)=v (et ψv,e(0) non définie), et sinon, ψv,e(n)=φe(n) (dans tout ça, ‹x,y› désigne un codage quelconque des couples d'entiers naturels par des entiers naturels) : autrement dit, dans la numérotation ψ, on précise séparément la valeur en 0 de la fonction (y compris « non définie ») et ses autres valeurs via une numérotation standard. Sur cet exemple, toute fonction calculable partielle apparaît bien dans les ψ, mais on ne peut pas calculer, à partir de d'un indice e d'une fonction calculable partielle h parmi les ψ, un tel indice pour la fonction constante de valeur h(1), car il faudrait pour cela déterminer si h(1) est défini (i.e., termine), donc résoudre le problème de l'arrêt. Donc on ne peut pas faire de substitution dans les ψ de façon algorithmique.

Pour raconter ce contre-exemple dans des termes informatiques, imaginons un langage de programmation permettant de coder des fonctions ℕ⇢ℕ (ou ℕk⇢ℕ, enfin peu importe) et qui est un langage tout à fait banal à une particularité près : la valeur en 0 de la fonction (qu'il s'agisse d'un entier ou du fait de partir en boucle infinie) doit être précisée par une instruction spéciale au début du programme, la seule instruction qui sera lue pour calculer cette valeur en 0, les autres valeurs étant calculées par un programme « normal » (par ailleurs, cette bizarrerie ne s'applique qu'à la fonction main, si j'ose dire, du programme). Interpréter ce langage, ou le compiler vers un autre, ne pose pas de problème particulier, et ce langage permet de représenter toutes les fonctions calculables partielles, ou d'ailleurs d'écrire un interpréteur pour un langage standard (une machine de Turing, disons) ou quelque chose comme ça. Mais il ne vérifie pas le théorème s-m-n, et ceci cause des bizarreries : on ne peut pas, par exemple, compiler un programme vers ce langage sauf à calculer à la compilation la valeur de la fonction en 0, ce qui risque de provoquer une boucle infinie ; et on ne peut pas algorithmiquement remplacer un programme dans ce langage par le programme qui calcule la (fonction constante égale à la) valeur en 1 de cette fonction. Ceci suggère que le terme Turing-complet est défini de façon un peu trop vague : à mon avis, ce qui importe est que l'énumération des fonctions partielles calculées par le langage considéré soit non seulement l'ensemble de toutes les fonctions calculables partielles, mais aussi que la numérotation soit acceptable au sens où on peut de façon calculable convertir une machine de Turing en le langage en question, et on peut montrer que cela revient exactement à vérifier le théorème s-m-n (avec une fonction s calculable).

(Référence pour tout ça : Soare, Recursively Enumerable Sets and Degrees, 1987, chapitre I, exercices 5.9 à 5.11. C'est de là que je tire le contre-exemple au théorème s-m-n.)

✱ Le second point concerne la fonction « castor affairé », qui à n associe le plus long temps d'exécution possible d'une machine de Turing à ≤n états et qui termine effectivement (en partant d'un ruban vide). Il est facile de voir que fonction, appelons-la h, dépasse infiniment souvent n'importe quelle fonction calculable [totale] f, au sens où, quelle que soit f calculable, il existe une infinité de n tels que h(n)≥f(n). (En effet si ce n'est pas le cas pour une certaine fonction f, quitte à modifier un nombre fini de valeurs de celle-ci, on a h(n)≤f(n) pour tout n, et on peut alors résoudre le problème de l'arrêt pour une machine de Turing — partant d'un ruban vide — en attendant f(n) étapes où n est son nombre d'états : si la machine ne s'est pas arrêtée au bout de ce temps-là, elle ne s'arrêtera jamais.) Mais le résultat classique dû à Tibor Radó est plus fort : la fonction h du « castor affairé » finit par dominer n'importe quelle fonction calculable f, au sens où, quelle que soit f calculable, l'inégalité h(n)≥f(n) est toujours vraie à partir d'un certain point, et je n'avais pas vraiment fait attention au fait que ce n'est pas trivial de passer de l'un à l'autre.

La démonstration d'origine de ce résultat (trouvable ici) est d'une part assez peu lisible (j'arrive à la suivre pas à pas, mais l'idée générale m'échappait) et d'autre part très spécifique au cas de la fonction « castor affairé » sur les machines de Turing en comptant leurs états. Par exemple, si on définit la fonction h en appelant h(n) la plus grande des valeurs φe(0) (ou φe(e), peu importe) qui soient définies pour 0≤en (l'argument montrant qu'elle dépasse infiniment souvent toute fonction calculable marche essentiellement pareil), alors est-il encore vrai que h finit par dominer n'importe quelle fonction calculable ? La réponse est oui, comme il résulte d'un échange sur math.stackexchange (je n'ai pas osé aller sur MathOverflow pour cette question), où on a pu m'expliquer beaucoup plus clairement l'argument de Radó, ce qui m'a permis de le généraliser facilement.

(J'en ai profité pour apprendre ce qu'est un degré de Turing hyperimmune, à savoir qu'il calcule une fonction qui dépasse infiniment souvent n'importe quelle fonction calculable, ce qui n'implique pas automatiquement qu'il calcule une fonction qui finit par dominer n'importe quelle fonction calculable.)

✱ Sinon, de fil en aiguille, je suis tombé par accident sur la relation suivante : pour A et B deux ensembles d'entiers naturels, notons AB lorsqu'il existe deux fonctions calculables partielles ℕ⇢ℕ qui se restreignent en des bijections réciproques entre ces deux ensembles. C'est une notion qui me semble extrêmement naturelle, mais qui n'est pas ce qu'on appelle de façon standard un isomorphisme calculable entre les deux ensembles. Mais ce qui me frappe, c'est que je n'ai réussi à en trouver aucune mention dans la littérature.

(mardi)

Après le rhinovirus, le norovirus

Remarque préliminaire : Même si je ne compte de toute façon pas entrer dans les détails, je rappelle à tout hasard que non seulement la lecture de mon blog n'est obligatoire pour personne, mais en plus la lecture d'une entrée particulière n'est pas nécessaire même si on veut lire la suite : il n'y a pas de contrôle de connaissances à la sortie. Je dis ça, parce qu'il y a régulièrement des vieux grincheux qui trouvent que tel ou tel sujet les incommode et qui s'en plaignent après coup dans les commentaires. D'ailleurs, de toute façon, l'information ne peut pas avoir de valeur négative, n'est-ce pas ? Ah non, zut.

Donc, juste après que j'ai posté une entrée pour me plaindre que les rhumes sont pénibles, un autre charmant virus est venu me rendre visite. Comme j'ai déjà posté il y a quelques années des remarques sur son mode de transmission, je ne vais pas les répéter. J'ai aussi déjà dit à cette occasion que je suis émétophobe, et d'ailleurs je crois que ça empire avec le temps, pas au point que ça affecte ma vie quotidienne, mais quand j'ai une gastro, l'anxiété à l'idée que je vais peut-être vomir est un désagrément comparable au mal au cœur lui-même. D'autant plus que quand il s'agit bien d'un virus (et a posteriori je n'ai aucun doute, même si j'ai aussi eu des aventures bactériennes — d'ailleurs passablement mystérieuses — par le passé), vomir n'aide absolument pas. Du coup, je n'hésite pas à prendre un antiémétique, en espérant que l'infection soit effectivement virale. En l'occurrence, la métopimazine. Qui est disponible en vente libre en France sous le nom de Vogalib® (en fait, il semble qu'il n'y ait quasiment qu'en France qu'on utilise la métopimazine, et je me demande bien pourquoi ; à ce sujet, il y a en eu une rupture de stock il y a quelques années qui a duré un bon nombre de mois, je me suis inquiété de tomber malade pendant ce temps, mais heureusement ce n'est pas arrivé). Après, peut-être que le fait qu'il soit en vente libre signifie qu'il est sans effet autre que placébo, je ne sais pas.

Mais il y a une chose qui est fascinante avec ce type d'infection, c'est sa régularité : je tiens un journal quotidien assez précis, et pour ce genre de maladie je note à quelle heure je commence à sentir quelque chose, à quelle heure je me sens mieux, etc. Et, même si ça ne m'arrive pas très souvent, heureusement, la progression semble toujours la même : ça commence par l'impression d'avoir trop mangé, mais elle ne passe pas, l'idée de manger ou la moindre odeur de nourriture deviennent de plus en plus répugnants, et le mal au cœur se développe progressivement, malgré des phases de répit occasionnelles, pendant assez précisément 14 heures (à compter des premiers symptômes) ; à ce moment-là, ça s'améliore assez soudainement (dans mon dernier cas, c'était vers 4h du matin dans la nuit de dimanche à lundi), même s'il faut encore huit à dix heures pour que j'aie envie de manger légèrement, et encore dix à douze heures supplémentaires, pendant lesquelles je reste très fatigué, avant d'être vraiment rétabli. Mais si ce planning est assez précis, ce que je n'ai jamais réussi à savoir dans aucun de mes cas de gastro, c'est comment je l'ai attrapée : apparemment, le virus incube pendant 12 à 48 heures avant l'apparition des premiers symptômes, et évidemment, avec un intervalle aussi imprécis en comparaison à la chronologie bien réglée que j'ai décrite, ce n'est pas facile de retrouver le poit de départ.

(dimanche)

De l'agacement provoqué par un téléviseur dont la télécommande ne marche plus

Il y a un peu moins de deux ans, j'ai remplacé l'antique téléviseur à écran cathodique que j'avais depuis une éternité (et qui m'avait d'ailleurs été offert par des gens à qui j'ai prêté mon appartement). Il marchait encore sans problème, c'est juste que ce n'était pas très pratigue d'utiliser un décodeur TNT externe. Apparemment, d'ailleurs, les télés CRT intéressaient encore des gens en 2014, parce que quand mon poussinet a mis la télé devant l'immeuble, le temps qu'il rentre chercher un papier sur lequel écrire le numéro d'enlèvement auprès du service des objets encombrants de la mairie de Paris, ce qui a pris environ une minute parce que nous habitons au rez-de-chaussée, la télé avait déjà disparu.

À la place, j'ai acheté un appareil LCD qui fait aussi décodeur TNT, magnétoscope numérique, moniteur, et sans doute d'autres formes de café, et qui coûtait 130€…

…chiffre à peu près représentatif de ce qu'il valait, c'est-à-dire, une proverbiale cheap plastic imitation, certainement chinoise. Ce n'est pas juste que je pense le plus grand mal des écrans LCD en général, mais à peu près tout était visiblement programmé en vitesse par des singes sous-payés. Par exemple, l'affichage des noms des émissions et autres informations de la TNT révélait un problème d'encodage des caractères (un peu dans ce genre-là, sauf que nous n'avons jamais réussi à deviner quels pouvaient être les deux jeux de caractères impliqués dans la confusion). Autre exemple, si on enregistre une émission sur clé USB et que le fichier stocké dépasse les 2Go, la télé plante et reboote (et reste allumée, et le fichier enregistré est, bien sûr, tronqué) : alors oui, je sais que le format FAT ne permet pas de stocker des fichiers de plus de 2Go (et que son successeur est totalement verrouillé par Microsoft donc essentiellement inutilisable), mais un appareil correctement programmé aurait pu, par exemple, couper tout seul le fichier en plusieurs morceaux en s'approchant de la limite fatidique. Encore un exemple, le réglage du son est linéaire et non logarithmique, donc quand on écoute la télé on a le choix entre 8 (pas assez fort) et 9 (trop fort) unités arbitraires alors que quand on écoute quasiment n'importe quelle vidéo, il faut mettre le réglage vers 90 ou au maximum et souvent ça ne suffit même pas. (Je me demande d'ailleurs pourquoi le niveau de mixage du son est si différent entre la TNT et la plupart des vidéos qu'on peut récupérer en ligne, mais ça au moins ce n'est pas la faute de la télé.) La télé met aussi un temps très long à changer de chaîne (c'est peut-être la faute de la TNT, je ne sais pas vraiment) et à s'allumer (ça c'est certainement plus la faute de la télé). Bref, je ne vais pas faire la liste de tout ce qui ne va pas dessus, vous avez déjà eu droit aux griefs sur mon réveil, vous pouvez imaginer le même genre de choses.

Si vous voulez le même modèle, ça s'appelle une Akira modèle LED-B81HU19F, terme dont la recherche donne un nombre ridiculement faible de résultats dans Google et bizarrement surtout en français (pourtant, l'interface n'est pas uniquement disponible en français).

Mais bon, mon poussinet et moi n'utilisons la télé que pour la regarder un petit peu pendant le dîner, ou très occasionnellement pour enregistrer une émission, ou pour changer un peu de l'ordinateur pour regarder une vidéo téléchargée sur Internet (du moins, si la télé sait en décoder le format, ce qui n'est pas le cas des MKV). Donc ce n'est pas très grave qu'elle soit merdique, et je l'ai achetée en connaissance de cause.

Seulement, il y a deux semaines, la télécommande est morte. Ce ne sont pas les piles, ce n'est pas non plus le capteur infrarouge sur le téléviseur, c'est bien la télécommande elle-même qui est morte. Je ne sais pas comment c'est possible que quelque chose d'aussi idiot tombe en panne, mais apparemment ça l'est. (Et elle n'a pas non plus subi de choc ou quoi que ce soit.)

Bon, le téléviseur n'est pas totalement inutilisable sans télécommande, il y a quelques boutons dessus qui permettent de l'allumer, de changer de chaîne (uniquement par ±1), de régler le volume, et même de faire apparaître un menu, mais plus moyen d'enregistrer, de changer la langue ou de faire apparaître les sous-titres. C'est un peu trop limité.

Pourquoi ne pas acheter une télécommande universelle ? Le truc est que la marque, et à plus forte raison le modèle, de notre téléviseur sont tellement obscurs qu'ils semblent en-dehors du champ d'application du mot universel (d'après la liste des marques indiquée au dos), et je n'ai pas envie de payer >10% du prix du téléviseur pour confirmer que la télécommande universelle ne fonctionne pas avec. Nous n'avons pas non plus de smartphone avec émetteur infrarouge qui permettrait de servir de télécommande universelle. (Et ma calculatrice HP48 de quand j'étais en prépa ne s'allume plus.) Il y a des gadgets infrarouge sur USB, mais sans les codes émis par la télécommande d'origine, ce ne serait pas évident d'en faire quoi que ce soit. <Insérer ici un rant selon lequel la commercialisation de n'importe quel appareil disposant d'une télécommande devrait obliger le fabriquant à publier l'intégralité des codes émis par cette télécommande sous un format facilement réutilisable par des émetteurs infrarouge.>

Nous avons aussi essayé, à tout hasard, de brancher un clavier sur le port USB du téléviseur, histoire de voir s'il réagissait à quelque chose (comme les combinaisons Alt+SysRq), mais apparemment pas.

Bref, tout ça a quelque chose de plus frustrant que si la télévision était entièrement tombée en panne. Ce n'est pas grave, je rachèterai une autre merde chinoise à une centaine d'euros qui tombera en panne dans deux ans, et nous mettrons celle que nous avons dehors où elle disparaîtra dans la minute — mais c'est quand même idiot.

(samedi)

Un médicament qui a peut-être de l'effet, ou peut-être pas

Je suis très souvent enrhumé (en tout cas, trop souvent à mon goût, peut-être trois fois dans une année typique). Même si les symptômes n'en sont pas très graves, la fatigue qu'ils provoquent, combinée au fait qu'ils empêchent aussi de bien dormir, rendent l'expérience quand même bien pénible, surtout quand elle tombe pendant une période où j'enseigne (d'où nécessité de se lever à une heure fixée, et d'exercer sa voix ce qui fatigue et assèche la gorge). Et les médicaments pour soigner ces symptômes sont d'une efficacité franchement très limitée. Alors quand ma maman m'a fait la pub de ce qu'elle m'a décrit comme un médicament miracle contre le rhume, je me suis dit que je n'y croyais pas du tout (j'ai un peu tendance à penser que presque aucun médicament en vente libre n'a le moindre effet, parce que s'ils avaient de l'effet ils auraient des effets nocifs et que du coup le principe de précaution ferait qu'ils ne seraient pas en vente libre), mais que, après tout, un placebo en plus dans mon arsenal, ça ne fera sans doute pas de mal. (Après, je n'ai jamais eu de réponse très claire à la question de savoir si un placebo peut fonctionner même si le patient est persuadé qu'il ne fera rien.)

Le médicament en question est un spray nasal qui porte en France le nom commercial de SurbroncViral : le principe actif est le ι-carraghénane qui a une activité antivirale. Peut-être. L'emballage publicitaire du médicament met surtout en valeur le fait qu'il réduit la durée du rhume. Il y a en effet quelques études publiées qui concluent à un effet bénéfique (par exemple Eccles, Meier &al, Efficacy and safety of an antiviral Iota-Carrageenan nasal spray […], Respiratory Research 11 (2010), ou plus récemment Ludwig, Enzenhofer &al. Efficacy of a Carrageenan nasal spray in patients with common cold […], Respiratory Research 14 (2013) ; il y en a encore un paquet d'autres) ; sauf que ces études sont financées par la boîte qui commercialise le produit, et la plupart des auteurs sont employés par elle… Après, je crois qu'en fouillant j'avais fini par trouver une étude où le conflit d'intérêt était, disons, moins évident, et dont le résultat était moins clair mais néanmoins positif, alors que je n'en ai pas trouvé qui annonce un résultat négatif, donc peut-être quand même que ma méta-analyse à 0.02¤ était positive. (Mais les revues médicales publient-elles facilement des articles qui concluent à une absence de résultat ? C'est un peu un problème intrinsèque de la publication scientifique qu'il biaise les résultats visibles en direction de ce qui sera considéré comme « intéressant ».) Et puis, finalement, c'est peut-être moi qui suis biaisé à trop me méfier.

Après tout, ce n'est pas une question si grave : même si le médicament coûte un prix un peu exorbitant, pourquoi ne pas juste me faire une idée par moi-même ?

J'ai eu un énorme rhume la semaine passée. J'ai utilisé le SurbroncViral™ comme indiqué par la notice. Ce que j'ai observé est que (A) mon rhume m'a encore plus fatigué que d'habitude (je ne prétends pas du tout que le médicament y soit pour quelque chose, bien sûr !, c'est plutôt un signe que c'était un « gros » rhume), (B) il a duré à peu près le temps que mes rhumes durent habituellement, (C) j'ai eu beaucoup moins le nez bouché que d'habitude (normalement je passe trois nuits entières à respirer par la bouche, là juste quelques heures, et encore, mon nez n'était pas complètement bouché), mon rhume a surtout pris la forme d'une sensation de froid, de fatigue, de maux de tête et de sinus douloureux, (D) j'ai aussi un peu moins toussé dans l'ensemble, et (E) j'ai l'impression que mon système imunitaire a maintenant éliminé le virus mais que mon nez continue à couler plus que normal et en tout cas mes sinus sont toujours enflammés. Est-ce que tout ceci est significatif ? Non, sans doute pas — à part peut-être le (C), toutes ces variations tombent à l'intérieur des fluctuations statistiques des mes rhumes typiques. (Dont je me demande, d'ailleurs, si elles sont plutôt dues à la différence entre souches de virus ou dans la réaction immunitaire de mon corps d'une fois sur l'autre.)

Bref, je ne sais pas quoi conclure. Peut-être que le médicament a fait de l'effet en me laissant le nez plus dégagé. Peut-être pas. Pour faire une étude scientifique, il faut un échantillon statistiquement représentatif, il faut faire les choses en double aveugle. Là, je n'ai pas d'échantillon représentatif, et je ne veux certainement pas faire les choses en double aveugle (je m'en fous de comparer à un effet placebo, l'effet placebo[#] m'intéresse autant que l'effet « réel »). Je déteste prendre des décisions avec des informations trop incomplètes — mais bon, c'est presque la définition de la vie, ça. Bref, je vais continuer à utiliser ce produit comme je continue à prendre beaucoup de vitamine C pendant mes rhumes : même si je ne crois pas vraiment que ça fasse du bien, je crois encore beaucoup moins que ça fasse du mal.

[#] Enfin, on ne devrait pas dire l'effet placebo, parce qu'il y en a plein : un effet purement psychologique (je prends un médicament, je me dis que je vais mieux), un effet somatique de cet effet psychologique (je me dis que je vais mieux, je me mets objectivement à aller mieux), et sans doute encore plein d'autres.

Only the 20 most recent entries were included above. Continue to older entries.

Seules les 20 plus récentes entrées ont été incluses ici. Continuer à lire les entrées plus anciennes.


Entries by month / Entrées par mois:

2016 Jan 2016 Feb 2016 Mar 2016 Apr 2016
2015 Jan 2015 Feb 2015 Mar 2015 Apr 2015 May 2015 Jun 2015 Jul 2015 Aug 2015 Sep 2015 Oct 2015 Nov 2015 Dec 2015
2014 Jan 2014 Feb 2014 Mar 2014 Apr 2014 May 2014 Jun 2014 Jul 2014 Aug 2014 Sep 2014 Oct 2014 Nov 2014 Dec 2014
2013 Jan 2013 Feb 2013 Mar 2013 Apr 2013 May 2013 Jun 2013 Jul 2013 Aug 2013 Sep 2013 Oct 2013 Nov 2013 Dec 2013
2012 Jan 2012 Feb 2012 Mar 2012 Apr 2012 May 2012 Jun 2012 Jul 2012 Aug 2012 Sep 2012 Oct 2012 Nov 2012 Dec 2012
2011 Jan 2011 Feb 2011 Mar 2011 Apr 2011 May 2011 Jun 2011 Jul 2011 Aug 2011 Sep 2011 Oct 2011 Nov 2011 Dec 2011
2010 Jan 2010 Feb 2010 Mar 2010 Apr 2010 May 2010 Jun 2010 Jul 2010 Aug 2010 Sep 2010 Oct 2010 Nov 2010 Dec 2010
2009 Jan 2009 Feb 2009 Mar 2009 Apr 2009 May 2009 Jun 2009 Jul 2009 Aug 2009 Sep 2009 Oct 2009 Nov 2009 Dec 2009
2008 Jan 2008 Feb 2008 Mar 2008 Apr 2008 May 2008 Jun 2008 Jul 2008 Aug 2008 Sep 2008 Oct 2008 Nov 2008 Dec 2008
2007 Jan 2007 Feb 2007 Mar 2007 Apr 2007 May 2007 Jun 2007 Jul 2007 Aug 2007 Sep 2007 Oct 2007 Nov 2007 Dec 2007
2006 Jan 2006 Feb 2006 Mar 2006 Apr 2006 May 2006 Jun 2006 Jul 2006 Aug 2006 Sep 2006 Oct 2006 Nov 2006 Dec 2006
2005 Jan 2005 Feb 2005 Mar 2005 Apr 2005 May 2005 Jun 2005 Jul 2005 Aug 2005 Sep 2005 Oct 2005 Nov 2005 Dec 2005
2004 Jan 2004 Feb 2004 Mar 2004 Apr 2004 May 2004 Jun 2004 Jul 2004 Aug 2004 Sep 2004 Oct 2004 Nov 2004 Dec 2004
2003 May 2003 Jun 2003 Jul 2003 Aug 2003 Sep 2003 Oct 2003 Nov 2003 Dec 2003