David Madore's WebLog: 2023-12

Méta : J'ai proposé une petite énigme la semaine dernière, qui m'était venue en réfléchissant à des questions autour de la logique et de la calculabilité (j'ai ajouté successivement un indice et la réponse, donc si vous aviez lu l'énigme et l'aviez trouvée intéressante mais sans aller jusqu'à la réponse, vous pouvez y jeter un nouveau coup d'œil). Avec toutes mes excuses aux >99.9% de mes lecteurs qui ne sont pas amusés par ce genre de choses, je vais finir l'année en en proposant une autre, un peu dans le même esprit mais néanmoins bien différente, qui m'est aussi venue en réfléchissant à des questions adjacentes. Je ne sais vraiment pas si elle est difficile (plus que la première ? moins ?), parce que pendant que j'y réfléchissais, je n'arrêtais pas de me tromper sur l'énoncé, de m'embrouiller sur ce que je voulais demander, et finalement de ne plus savoir du tout où j'en étais ; j'ai régulièrement cru me persuader que « non, ce n'est pas possible du tout, ce truc », et finalement la réponse m'a semblé étonnamment bête, du genre « mais comment je n'ai pas vu ça ? », peut-être parce qu'il faut penser out of the box comme on dit, ou peut-être que je m'obstinais un peu trop à réfléchir dans les mêmes lignes que l'énigme précédente. Bon, cette fois je ne vais pas trop essayer de faire semblant de m'adresser au grand public, donc même si je vais écrire un scénario tarabiscoté pour rendre l'énigme formellement indépendante, je suppose en fait qu'on connaît les bases de calculabilité et qu'on sait ce qu'est un ensemble décidable, un algorithme, ce genre de choses. (La version formulée mathématiquement, que je donne à la fin, est beaucoup plus simple que l'énigme précédente, et certainement plus simple que mon scénario tarabiscoté.)

[Lire la suite…]

Ce qui motive ce billet (qui traîne depuis un moment dans mes cartons) est que j'entends de plus en plus de gens dire que YouTube s'est mis à bloquer leur bloqueur de pub. Le mien (Adblock Plus, à ne pas confondre avec AdBlock, ils n'ont pas plus de rapport qu'un lointain ancêtre commun, oui, c'est très confusant) continue à marcher, ou peut-être que YouTube a décidé de ne pas me servir de pub ou peut-être que je ne fais pas (encore ?) partie de la population sur laquelle il teste le bloqueur de bloqueur de pub, mais j'imagine que je vais tomber sur le problème tôt ou tard, et devoir soit me passer de YouTube soit perdre du temps pour trouver comment bloquer le bloqueur de bloqueur de pub, temps qui aurait été bien plus agréablement perdu à regarder YouTube. En tout cas je n'imagine pas du tout de regarder leurs pubs, et leur abonnement Premium coûte un prix complètement déraisonnable (eu égard à une estimation raisonnable à la fois du coût marginal que je leur fais subir et de ce que je pourrais leur rapporter en pubs) donc je ne l'envisage pas non plus.

Mais laissant de côté le cas particulier de YouTube, il faut dire clairement que le financement d'Internet est un problème fondamental auquel personne n'a de réponse satisfaisante. Je n'ai pas de lumière particulière à apporter, mais je peux au moins décortiquer le problème par le menu comme c'est la spécialité de ce blog.

[Lire la suite…]

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

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

[Lire la suite…]

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

[Lire la suite…]

On dit souvent jamais deux sans trois, mais il me semble que c'est une pure coïncidence que, moi qui ne lis pas beaucoup de bédés (et, à vrai dire, pas beaucoup tout court), me retrouve à évoquer trois albums coup sur coup dans ce blog : après celle-ci dans le style « jeu de personnages » et celle-ci de sociologie, disons un mot des Indes fourbes (pas si récent que ça, et dont j'ai entendu parler au hasard d'une mention sur Twitter).

Mais, à vrai dire, je ne veux pas en dire grand-chose, parce que je ne veux pas divulgâcher : j'ai moi-même ouvert l'album en ne sachant essentiellement rien de ce qu'il y avait dedans, et je pense que c'est le meilleur état d'esprit pour l'apprécier.

Disons juste que le scénario est écrit par Alain Ayroles (notamment connu pour la très drôle série De Cape et de Crocs) et que les dessins sont de Juanjo Guarnido (notamment connu pour le style très léché de Blacksad) : cette combinaison d'auteurs peut déjà donner envie de lire cet album.

Disons aussi, pour les gens qui comme moi pensent que cette information a une importance, qu'il s'agit d'un album unique (pas un élément d'un cycle), et d'une histoire qui se tient à elle seule, et qui a une vraie fin. Ceci peut prêter à confusion, vu que la couverture porte le sous-titre :

Une seconde partie de l'Histoire de la vie de l'aventurier nommé don Pablos de Ségovie, vagabond extraordinaire et miroir des filous ; inspirée de la première, telle qu'en son temps la narra don Francisco Gómez de Quevedo y Villegas, chevalier de l'ordre de Saint Jacques et seigneur de Juan Abad

Ce sous-titre (ou faut-il parler d'une épigraphe ?) signifie que la bédé est une suite imaginée du roman El Buscón (Historia de la vida del Buscón, llamado don Pablos; ejemplo de vagamundos y espejo de tacaños) de Francisco Gómez de Quevedo, roman picaresque, satirique et humoristique, espagnol paru en 1626 : à la fin de ce(t unique) roman de Quevedo, l'aventurier éponyme embarque pour l'Amérique pour tenter sa chance là-bas, promettant une suite que Quevedo n'a jamais écrite : c'est donc cette suite qu'Ayroles et Guarnido imaginent. La première page de la bédé est d'ailleurs composée d'une manière qui imite le frontispice du roman de Quevedo.

Mais il n'est pas nécessaire d'avoir lu ce dernier (et d'ailleurs je m'avoue dans ce cas) : les quelques éléments de situation sont rappelés dans la bédé, et l'histoire est de toute façon complètement différente. Cependant, il peut être bon de savoir que le thème principal du roman de Quevedo est celui des efforts et fourberies que fait son héros (un gueux, fils d'une prostituée et d'un homme qui finit pendu) pour essayer de s'élever au-dessus de sa condition : dans le roman, ces efforts sont toujours des échecs, et la morale est que, gueux il est et gueux il restera. Dans la bédé… ah ben, je ne vais pas en dire plus.

Bref, c'est l'histoire de ce Pablos, qui part pour les Indes occidentales, et qui raconte sa recherche de l'El Dorado — qu'il a peut-être fini par trouver, ou peut-être pas, là non plus je ne vais pas vous en dire plus.

C'est à la fois une histoire d'aventures picaresques (au sens original du terme), qu'on peut également rapprocher du film de casse, parce qu'il est bien question d'un casse (et même d'un très gros casse), et aussi une satire sociale, un tableau (artistique, et pas historique) de l'Espagne et de ses colonies au Siècle d'or, spécifiquement sous le règne de Philippe IV… mais c'est surtout très drôle. Pas drôle à la manière d'une bouffonnerie qui ne se prend jamais au sérieux, mais plutôt d'une histoire qui fait semblant de se prendre au sérieux, mais dont on se demande régulièrement où est le lard et où est le cochon. (Je suis un peu tenté de comparer le style à Ruy Blas de Hugo, qui se passe à peu près à la même époque, et qui réussit à être un drame immensément drôle, dont il a d'ailleurs été tiré une adaptation cinématographique un peu dans le même esprit que la bédé que j'évoque ici. On peut aussi comparer, dans une moindre mesure, à Cyrano de Bergerac : même si le panache de Cyrano est diamétralement opposé à la fourberie de Pablos, il y a un style d'humour commun.)

Et j'aime aussi beaucoup le dessin : non seulement il est très soigné mais aussi, signe d'une bonne bédé, il ne fait pas qu'accompagner l'histoire mais la pousse en avant : il y a des pages entières des aventures que raconte Pablos qui sont entièrement en images, sans un seul mot : c'est tout à fait à dessein (ha, ha), et le style en est très fort. Les personnages sont absolument truculents dans leur représentation graphique : le héros lui-même, mais aussi l'alguazil auquel il raconte son histoire, le corregidor qui vient récupérer l'argent des mines, le vice-roi de Nouvelle-Espagne, le comte-duc d'Olivares et le roi Philippe IV lui-même.

Le livre est par ailleurs truffé de références et de clins d'œil : y compris à lui-même, certainement au roman dont il prétend être une suite, et à toutes sortes d'autres choses (il est difficile, par exemple, de ne pas reconnaître une allusion visuelle au plus célèbre tableau de Velázquez — allusion qui n'est, d'ailleurs, pas gratuite — ainsi qu'à d'autres du même).

Bref, j'ai adoré ce livre, et je le recommande à ceux qui aiment les histoires d'aventures picaresques, drôles et pleines de rebondissements et de fourberies, et qui ne se prennent pas trop au sérieux.

Les Indes fourbes d'Alain Ayroles et Juanjo Guarnido, 160 pages, éditions Delcourt.

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

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

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

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

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

❦

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

❦

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

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

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

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

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

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

[Lire la suite…]