David Madore's WebLog: 2023-12

Vous êtes sur le blog de David Madore, qui, comme le reste de ce site web, parle de tout et de n'importe quoi (surtout de n'importe quoi, en fait), des maths à la moto et ma vie quotidienne, en passant par les langues, la politique, la philo de comptoir, la géographie, et beaucoup de râleries sur le fait que les ordinateurs ne marchent pas, ainsi que d'occasionnels rappels du fait que je préfère les garçons, et des petites fictions volontairement fragmentaires que je publie sous le nom collectif de fragments littéraires gratuits. • Ce blog eut été bilingue à ses débuts (certaines entrées étaient en anglais, d'autres en français, et quelques unes traduites dans les deux langues) ; il est maintenant presque exclusivement en français, mais je ne m'interdis pas d'écrire en anglais à l'occasion. • Pour naviguer, sachez que les entrées sont listées par ordre chronologique inverse (i.e., la plus récente est en haut). Cette page-ci rassemble les entrées publiées en décembre 2023 : il y a aussi un tableau par mois à la fin de cette page, et un index de toutes les entrées. Certaines de mes entrées sont rangées dans une ou plusieurs « catégories » (indiqués à la fin de l'entrée elle-même), mais ce système de rangement n'est pas très cohérent. Le permalien de chaque entrée est dans la date, et il est aussi rappelé avant et après le texte de l'entrée elle-même.

You are on David Madore's blog which, like the rest of this web site, is about everything and anything (mostly anything, really), from math to motorcycling and my daily life, but also languages, politics, amateur(ish) philosophy, geography, lots of ranting about the fact that computers don't work, occasional reminders of the fact that I prefer men, and some voluntarily fragmentary fictions that I publish under the collective name of gratuitous literary fragments. • This blog used to be bilingual at its beginning (some entries were in English, others in French, and a few translated in both languages); it is now almost exclusively in French, but I'm not ruling out writing English blog entries in the future. • To navigate, note that the entries are listed in reverse chronological order (i.e., the most recent is on top). This page lists the entries published in December 2023: there is also a table of months at the end of this page, and an index of all entries. Some entries are classified into one or more “categories” (indicated at the end of the entry itself), but this organization isn't very coherent. The permalink of each entry is in its date, and it is also reproduced before and after the text of the entry itself.

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

Entries published in December 2023 / Entrées publiées en décembre 2023:

↓Entry #2776 [older| permalink|newer] / ↓Entrée #2776 [précédente| permalien|suivante] ↓

(dimanche)

Une autre énigme de calculabilité

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é.)

L'énigme

Le cruel Docteur No (connu pour ses méfaits précédemment racontés ici, , , et encore — et j'en ai peut-être oublié au passage) est à la recherche d'inspiration pour une nouvelle torture pour mathématiciens. Ayant construit un Ordinateur Infini[#], il s'apprête à choisir une question, pour chaque entier n, dont la réponse est soit oui, soit non, de manière à ce qu'il soit impossible de calculer algorithmiquement la réponse en fonction de n : ces pauvres mathématiciens, qui ne disposent que de vulgaires ordinateurs (i.e., machines de Turing) seront donc incapables de répondre à la question, et le Docteur No jubile de l'impossibilité devant laquelle il va les placer.

Mais voilà que son code de l'honneur de grand méchant se rappelle à lui : ses énigmes doivent avoir une solution ! Il doit toujours y avoir un moyen de s'en sortir. Demander de calculer une fonction non-calculable n'est pas du jeu.

Le mathématicien capturé aura donc le droit de faire calculer par l'Ordinateur Infini une indication pour chaque question, sous forme d'un entier naturel h(n), qui lui sera donnée avec la question. Bon, mais comme ça ce serait vraiment trop facile. Donc en fait le Docteur No va mettre deux limitations sur cette indication : d'abord, il n'y aura une indication choisie par le mathématicien que quand la réponse à la question est oui ; quand la réponse est non, le mathématicien se verra donnée une fausse indication, choisie par le Docteur No (et évidemment, aucune façon de savoir si on a affaire à une vraie ou fausse indication). Ensuite, l'indication sera donnée non pas comme l'entier h(n) mais comme un programme q (ne prenant pas d'entrée, et choisi par Docteur No en même temps que n) qui calcule h(n) : en cas de fausse indication (i.e., si la réponse attendue est non), le programme pourrait ne jamais terminer du tout, ou pourrait terminer et renvoyer n'importe quoi (ou même ne pas être un programme du tout, mais ça ce n'est pas intéressant parce que c'est trop facile à tester) ; en revanche, en cas de vraie indication (i.e., si la réponse attendue est oui), le programme fourni terminera en temps fini et renverra h(n) (mais sans aucune autre garantie que ça). Avec ces données n (la question) et q (le programme calculant — peut-être — l'indication), le mathématicien doit (algorithmiquement !) calculer la réponse attendue, sachant que l'énigme doit faire que ce ne soit pas possible sans q.

Comment le Docteur No va-t-il choisir son énigme pour que le problème soit faisable, et comment le mathématicien capturé va-t-il choisir les indications ?

[#] Ce peut calculer l'Ordinateur Infini n'est pas très pertinent ici. Disons par exemple qu'il peut calculer n'importe quoi dont on peut démontrer l'existence. Mais si on veut par exemple imaginer que c'est une machine hyperarithmétique, on peut.

Comme mon scénario est assez tarabiscoté (franchement, si vous trouvez une meilleure façon de raconter l'histoire, dites-le moi !), voici une version mathématiquement précise de ce que je demande de prouver :

Montrer qu'il existe une fonction d:ℕ→{0,1} non calculable (ce sont les réponses attendues, avec ‘0’ pour non et ‘1’ pour oui) et une fonction h:ℕ→ℕ (nécessairement non calculable ; ce sont les indications ; la valeur de h(n) n'aura d'importance que si d(n)=1 donc on peut se limiter définir h sur d−1({1})) telles qu'il existe un algorithme p qui, donné un n∈ℕ et un q comme on va le dire, termine toujours en temps fini et calcule d(n). La garantie sur q est que si d(n)=1 alors q est un programme sans entrée[#2] qui termine en temps fini et renvoie h(n) (en revanche, si d(n)=0 alors il n'y a aucune sorte de garantie sur q, c'est une donnée finie arbitraire).

[#2] Pour qu'il n'y ait pas de confusion possible : q ne prend pas n en entrée : il (q) est donné en même temps que n, et la garantie est que si d(n)=1 alors pour ce n-là, le programme q (qui ne prend pas d'entrée du tout) termine et renvoie h(n).

Je ne sais pas si j'ai vraiment d'indication à donner, cette fois-ci : je vois mal comment en donner une sans donner directement la solution : je sais juste qu'on peut partir dans la mauvaise direction et avoir l'impression que cette énigme est complètement insoluble, ou bien se dire qu'en fait c'est juste idiot. Sans que ce soit une indication (et je ne me prononce pas sur le fait que ça aide au problème général), on peut éventuellement commencer par réfléchir à la version plus simple où q est directement la valeur de h(n) dans le cas où d(n)=1, au lieu d'être un programme qui la calcule.

Une fois de plus, j'écrirai la réponse dans quelques jours en éditant ce billet. En attendant, à défaut de trouver la solution, vous pouvez aussi proposer une façon plus claire que moi de présenter l'énigme ! (Vous pouvez aussi vous plaindre si les termes de l'énigme ne sont pas clairs.)

La réponse

[Section ajoutée .]

Voici la solution que je propose (j'ai peur qu'elle soit complètement incompréhensible si on n'a pas un minimum d'habitude de la calculabilité, mais j'ai quand même fait des efforts minimaux pour rappeler quelques conventions du domaine).

↑Entry #2776 [older| permalink|newer] / ↑Entrée #2776 [précédente| permalien|suivante] ↑

↓Entry #2775 [older| permalink|newer] / ↓Entrée #2775 [précédente| permalien|suivante] ↓

(mardi)

Il faut qu'on parle des pubs en ligne et du financement du Web

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.

☞ Le modèle de financement du Web est pourri

Je faisais remarquer il y a quelques mois dans cette entrée sur la préservation de l'information que pour rendre une information disponible sur le Web, il faut payer, et payer en permanence (si bien que quand un individu décède ou une compagnie fait faillite, les informations disparaissent) : c'est une conséquence structurale de la manière dont le Web fonctionne (voir cette autre entrée pour de la vulgarisation à ce sujet), à savoir que des serveurs doivent tourner en permanence pour être prêts à répondre aux requêtes des navigateurs. Par exemple, s'agissant de ce blog, il est hébergé sur un serveur que je loue avec de l'argent qui sort de ma poche : j'ai des raisons diverses de vouloir faire ça (allant de la vanité de disséminer mes idées à la commodité de pouvoir moi-même relire à tout endroit sur mon téléphone un truc qui me sert largement de bloc-notes) ; mais même si je voulais demander à mes lecteurs de participer au financement de son hébergement, ce ne serait pas du tout évident.

C'est complètement différent du modèle d'un livre où non seulement l'objet ne disparaît pas quand son auteur décède (je parle ici des vrais livres sur papier, pas les e-books qui disparaissent quand la compagnie qui vous l'a loué en faisant semblant de vous le vendre décide de vous retirer son bon vouloir), mais aussi, même si quelqu'un doit payer des frais d'édition initiaux, le lecteur contribue assez naturellement à les rembourser, même pour un livre pour lequel aucune propriété intellectuelle ne s'applique (i.e., le prix concerne le processus d'édition et pas la rémunération de l'auteur).

Il me semble que c'est un problème fondamental, dont les conséquences expliquent beaucoup des problèmes du Web à travers les moyens tous pourris qu'on a de contourner de problème. Hélas, je n'ai pas de meilleur système à proposer (les choses comme IPFS ont peut-être du potentiel, mais il faut reconnaître que ça ne marche pas pour l'équivalent d'un site Web, et en plus ce type de modèle est maintenant teinté par la culture toxique des cryptomonnaies).

☞ Les quatre modes de financement principaux

Les modes de financement du Web qu'on a trouvés pour contourner ce problème fondamental du il faut payer pour héberger et pas pour lire semblent se limiter aux suivants :

  • Baisser les bras, i.e., accepter la réalité du fait qu'il faut payer pour héberger. Cela peut s'expliquer si, par exemple, l'hébergeur est une institution qui a dans ses missions de communiquer (on comprend par exemple ainsi le fait que la Bibliothèque Nationale de France paye pour mettre en ligne énormément de livres qu'elle a scannés) ou si cette communication sert à sa mission ou lui est autrement profitable (le plus évident étant une entreprise commerciale qui a besoin d'exister en ligne pour que ses clients la trouvent). De tels sites Web sont donc gratuits et sans pub ni abonnement (ou éventuellement ils sont intégralement de la pub pour leur auteur ; je suppose qu'on peut aussi ranger dans cette catégorie tous les sites marchands où le site est gratuit parce que les produits qu'on y achète sont payants).

  • Faire appel à la bonne volonté des visiteurs, i.e, leur demander de contribuer au financement du site sans pour autant en faire une condition sine quā non de son utilisation, soit en payant directement, soit en achetant des goodies (genre tee-shirts ou autocollants) dont on comprend bien qu'ils n'ont pas d'autre intérêt que de matérialiser une contribution financière. Wikipédia utilise ce modèle, ce qui prouve qu'il peut fonctionner à grande échelle ; mais il reste qu'il est très compliqué en pratique de payer une petite somme d'argent à plein de sites qu'on trouve un petit peu utiles (on ne sait pas faire fonctionner de système pratique de micropaiements), et c'est aussi assez horripilant d'être constamment bombardé de messages du type ce site est payé par vos contributions : s'il vous plaît, pensez à visiter la page de dons.

  • Fonctionner sur un système d'abonnements, i.e., le site n'est accessible qu'aux gens qui payent.

  • Ou enfin, bien sûr, mettre des pubs.

Toutes sortes de compromis sont possibles entre ces systèmes : par exemple, il est fréquent que le site soit payant mais que quelques parties soient quand même gratuites histoire d'allécher le client potentiel (les journaux en ligne payant mettent souvent une poignée d'articles en accès libre ainsi que le début de tous leurs articles, ou quelque chose come ça) ; ou inversement, le site est gratuit, mais pour inciter à donner on réserve quelques fonctionnalités supplémentaires aux donateurs/abonnés ; ou encore, le site est gratuit mais chargé de pubs et on peut payer pour avoir une version sans pubs.

☞ Ce qui ne va pas avec eux

Soyons bien clairs : tous ces systèmes sont pourris. Si je dois absolument choisir mon poison, le système le site est gratuit mais quelques fonctionnalités supplémentaires sont payantes ou le site est gratuit, mais les abonnés ont accès aux informations en avance me semble le moins mauvais, mais aucun des quatre grands systèmes que j'ai décrits ne fait plus que répartir la merde d'un problème fondamental. Il n'est pas normal qu'un site utile soit payé par ses auteurs, mais il n'est pas non plus normal qu'on ait à supplier les lecteurs (et donc les emmerder) ou les culpabiliser pour obtenir une petite obole ; les sites fonctionnant sur abonnement sont coupés du Web et cassent son modèle de partage de l'information ; et les pubs sont une calamité parce qu'elles transforment le lecteur en ennemi qu'il s'agit de duper, ce qui ne peut qu'aboutir à une guerre. Bref, ces quatre modèles sont complètement pourris : différemment pourris, mais complètement pourris quand même.

Pour détailler un petit peu, le premier problème avec les sites fonctionnant sur abonnement, c'est qu'ils empêchent de partager les informations par un lien. Si je m'abonne à un journal en ligne, je vais avoir accès aux articles de ce journal, mais ce qui m'intéresse n'est pas juste de pouvoir les lire mais aussi de les montrer à mes amis, de pouvoir les citer sur mon blog, ce genre de choses : le partage de l'information est le principe même du Web, et si je ne peux pas faire toutes ces choses, je préfère ne pas avoir accès à l'information du tout. Et symétriquement, de temps en temps je vois passer des liens sur les réseaux sociaux pointant vers des articles auxquels je n'ai pas accès : qu'est-ce que vous voulez que je fasse de choses comme ça ? Je ne vais pas m'abonner pour lire un unique article (encore une fois : les micropaiements ne marchent pas et c'est un drame), donc ce genre de liens ne font que m'irriter à la fois contre la personne qui me nargue avec un lien auquel je n'ai pas le droit d'accéder comme si elle me montrait une photo de l'intérieur de son club exclusif, et contre l'auteur du contenu.

Un système un peu plus malin est celui où chaque abonné, en plus du droit d'accéder à l'ensemble des contenus couverts par son abonnement, a le droit d'en partager un certain nombre, c'est-à-dire de créer des liens qui seront accessibles aussi par les non-abonnés. Mais ces systèmes ont forcément des limites, parce que les auteurs du site ont peur qu'un petit nombre de lecteurs se regroupent pour partager tous les articles et créent ainsi une version gratuite du site : probablement, chaque lien de partage ne marchera qu'un nombre donné de fois ou autre limitation à la con.

Plus fondamentalement, le problème avec les sites sur abonnement, c'est qu'ils ne font pas vraiment partie du Web, c'est-à-dire du Web ouvert, public, recherchable et (certes imparfaitement mais néanmoins un peu) archivé. Les problèmes déjà pénibles d'accès et de préservation de l'information sur le Web sont donc encore empirés sur ce non-Web. Si je m'abonne à un site payant, je vais devoir mettre en place un mécanisme pour sauvegarder tout ce que je consulte dessus, parce que je risque de perdre l'accès si mon abonnement expire et parce que l'Internet Archive ne l'archivera pas pour moi : ça va me prendre plus de temps et d'efforts que l'abonnement n'en vaut, donc je préfère laisser tomber.

Reste la solution des pubs.

↑Entry #2775 [older| permalink|newer] / ↑Entrée #2775 [précédente| permalien|suivante] ↑

↓Entry #2774 [older| permalink|newer] / ↓Entrée #2774 [précédente| permalien|suivante] ↓

(dimanche)

Une énigme avec un dragon et de la calculabilité

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.

L'énigme

Vous êtes un aventurier dans un donjon. Devant vous se trouvent trois portes, identiques à part leur étiquette : A, B et C. Derrière une de ces portes se trouve un dragon, qui vous dévorera si vous ouvrez la porte, mais vous ne savez pas laquelle. Votre but est d'ouvrir une des portes « sûres », c'est-à-dire sans dragon (et qui conduisent à la sortie et, soyons généreux, à un trésor pour vous récompenser d'avoir résolu l'énigme). Peu importe quelle porte sûre vous ouvrez, la seule chose qui importe est de ne pas ouvrir la porte au dragon.

Pour vous aider à trouver une porte sûre, il y a un indice apposé sur chaque porte. Mais comme ceci est un donjon très moderne, pas ces trucs poussiéreux des magiciens d'il y a quelques siècles, chaque indice prend la forme d'un programme informatique. Ça tombe bien, vous avez un ordinateur capable de faire tourner ces programmes (ou pour en examiner le contenu si vous le voulez).

L'idée générale est que le programme apposé sur chaque porte devrait, quand vous l'exécutez, vous indiquer une des deux autres portes qui soit sûre. Mais ce n'est pas si simple ! Car le programme demande quelque chose en entrée, et ne fonctionnera correctement que si on lui a fourni le bon quelque chose. Et ce quelque chose est aussi un programme (qui, lui, ne prend rien en entrée).

Les règles précises sont les suivantes :

  • Le programme apposé sur la porte au dragon, quoi qu'on lui passe en entrée, va terminer quoi qu'il arrive et produire comme résultat l'étiquette d'une des deux autres portes. (Comme il n'y a qu'un dragon, les deux autres portes sont sûres, donc ce sera de toute façon une porte sûre. Son choix peut dépendre de ce que vous avez donné en entrée, mais il doit produire un résultat dans tous les cas, même si le programme qu'on lui a fourni en entrée n'a pas de sens ou ne termine pas ou quoi que ce soit du genre.)

  • Le programme apposé sur une porte « sûre » va terminer et produire comme résultat l'étiquette de l'autre porte sûre (il n'y en a qu'une autre), mais à condition qu'on lui ait fourni comme entrée un autre programme qui lui-même (exécuté sans entrée) produit comme résultat l'étiquette de l'autre porte sûre. Si cette condition n'est pas remplie, le comportement du programme n'est pas précisé (il pourrait ne pas terminer, produire une mauvaise porte, ou afficher 42 ou n'importe quoi d'autre ; mais il ne va pas vous tuer, quand même : c'est un programme, pas un dragon, et votre ordinateur peut le faire tourner sans risque).

Je redis ça pour être bien sûr d'avoir été clair. Appelons X la porte au dragon, et Y,Z les deux autres portes. Appelons pX,pY,pZ les programmes apposés aux portes X,Y,Z respectivement, et q un programme qu'on décide de passer en entrée à un de pX,pY,pZ. Les garanties sont : d'abord, concernant la porte au dragon, pX(q) termine quoi que soit q et produit comme résultat soit Y soit Z ; ensuite, concernant les deux autres portes : si q termine et produit Z comme résultat alors pY(q) termine et produit lui aussi Z comme résultat, et de même, si q termine et produit Y comme résultat alors pZ(q) termine et produit Y comme résultat.

Vous avez bien sûr le droit de lancer les programmes plusieurs fois (séquentiellement ou en parallèle) avec des entrées différentes. Vous avez le droit de créer vos propres programmes (par exemple écrire un programme qui produit toujours la sortie B, et fournir ça au programme de la porte C est légitime ; ou même faire un programme qui exécute le programme de la porte C sur le programme qui produit toujours B en sortie, et fournir ça au programme de la porte A : tout ça est légitime). Vous avez aussi tout le temps nécessaire, mais il faut quand même arriver à un résultat de façon certaine au bout d'un temps fini (donc on a le droit d'attendre longtemps la sortie d'un programme, mais s'il ne termine jamais c'est un échec).

En fait, votre réponse sera elle-même algorithmique. C'est-à-dire que techniquement, ce que je demande c'est d'écrire un programme qui prend en entrée les programmes pX,pY,pZ apposés aux trois portes et qui, quelle que soit la porte au dragon et quels que soient pX,pY,pZ vérifiant les contraintes, termine et produit en sortie l'étiquette d'une porte qui n'a pas de dragon.

Voilà, c'est un peu long, mais j'espère que c'est parfaitement clair. S'il y a quelque chose qui ne l'est pas, dites-le moi en commentaire et j'essaierai de préciser les règles.

Résumé : Il y a une seule porte avec un dragon et on ne sait pas laquelle, les deux autres sont sûres et le but est de trouver une porte sûre. Chaque porte a un programme apposé comme indice. Ce programme termine et produit comme résultat l'étiquette d'une des deux autres portes qui soit sûre ; mais, s'agissant du programme apposé sur une porte sûre, ceci n'est garanti que sous condition qu'on lui passe comme entrée un programme (sans entrée) qui lui-même termine et produise comme résultat l'étiquette de l'autre autre porte qui soit sûre.

Comment vous tirez-vous (de façon certaine) de cette fâcheuse situation ?

Pourquoi elle semble insoluble

J'ai fini l'énoncé de l'énigme et on peut s'arrêter de lire là si on veut y réfléchir ; mais je vais quand même faire un commentaire qui, sans vraiment constituer un indice, attire l'attention sur ce qui est difficile dans cette énigme.

↑Entry #2774 [older| permalink|newer] / ↑Entrée #2774 [précédente| permalien|suivante] ↑

↓Entry #2773 [older| permalink|newer] / ↓Entrée #2773 [précédente| permalien|suivante] ↓

(vendredi)

Une introduction à la correspondance de Curry-Howard

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.

Table des matières

Introduction

[Sean Connery dans le rôle de Guillaume de Baskerville dans le film “Le Nom de la Rose”] Preuves mathématiques
(contemplatives ?)

[Sean Connery dans le rôle de Zed dans le film “Zardoz”] Programmes informatiques
(dynamiques ?)

Bref, mon but est d'exposer (avec des prérequis aussi limités que possible) la correspondance de Curry-Howard entre preuves et programmes.

De quoi s'agit-il ? On résume parfois la correspondance de Curry-Howard en disant que, comme un bon acteur capable de prendre des rôles très différents, les preuves mathématiques et les programmes informatiques sont, en fait, fondamentalement la même chose (et d'ailleurs je suis très content de l'illustration ci-contre).

À vrai dire, ce raccourci, qui a le mérite d'être mémorable, est un peu… raccourci. Ce ne sont pas n'importe quelles preuves et surtout, ce ne sont pas n'importe quels programmes. Côté preuves, il s'agit a priori de preuves en logique intuitionniste (c'est-à-dire sans le tiers exclu ; je vais définir les choses précisément ci-dessous), et même si on peut étendre Curry-Howard à la logique classique grâce à la fonction call/cc, la correspondance obtenue n'est peut-être pas aussi satisfaisante. Côté programmes, il s'agit de programmes écrits dans des langages fortement typés dans lesquels la terminaison de tout programme est garanti : donc ce ne sont pas du tout les langages de programmation habituels, lesquels permettent des boucles infinies et/ou des appels récursifs illimités[#] ; il n'y a rien non plus qui corresponde à des effets de bord (modification de valeurs, entrées-sorties, rien de tel). Parmi les limites de Curry-Howard, il y a aussi des différences subtiles dans la signification de la quantification existentielle (‘∃’) en logique par rapport aux types sommes (‘Σ’) qui vont faire l'objet de mon « addendum 1 » plus bas.

Toujours est-il que, malgré ces limitations, Curry-Howard établit une correspondance entre, côté logique propositions et preuves de ces propositions, et, côté informatique, types dans un langage informatique fortement typé et termes (i.e., programmes) de ces types. À un certain niveau c'est même une trivialité (observer qu'on exactement les mêmes règles de formation des deux côtés : c'est juste deux façons de voir le même acteur, cet acteur étant une sorte de λ-calcul qui peut servir soit à désigner des preuves soit à coder des programmes) ; mais quand même, cette correspondance permet d'interpréter une preuve comme quelque chose qui va s'exécuter, prendre des données en entrée et renvoyer des résultats à la sortie, et c'est assez frappant, et c'est l'essence de ce qui permet d'extraire d'une preuve constructive un programme réalisant le calcul qu'elle prétend construire (j'agite un peu les mains ici). À titre d'exemple, le programme qui correspond à la preuve « évidente » de AB ⇒ BA (si A et B sont vrais, alors B et A sont vrais) est le programme qui prend en entrée un couple et échange les deux coordonnées de ce couple (lesquelles peuvent être de types arbitraires).

[#] Comme je l'ai déjà signalé ici, autoriser ces appels récursifs revient très précisément, au niveau preuves, à autoriser les raisonnements du style suivant : Je veux démontrer que les poules ont des dents. Je tiens l'affirmation suivante : Si j'ai raison, alors les poules ont des dents. Clairement, si j'ai raison (c'est-à-dire, si cette affirmation est vraie), alors les poules ont des dents. Mais c'était justement mon affirmation : donc j'ai raison. Donc, par ce qui vient d'être démontré, les poules ont des dents. Il est peut-être intéressant de s'intéresser à des logiques paraconsistantes dans lesquelles une telle démonstration serait permise (et du coup, tout est démontrable, de même que dans un langage de programmation usuel on peut fabriquer un programme de n'importe quel type — même le type vide, c'est juste que le programme ne terminera pas), mais ce n'est pas ce qu'on appelle usuellement une « démonstration » mathématique.

De façon un petit peu plus détaillée, la correspondance de Curry-Howard met en regard (je vais essayer d'expliquer ces différents points dans la suite, donc ceci est un divulgâchis qui a pour but d'aider à se retrouver dans la masse de mes explications si on décide de la lire en diagonale) :

  • propositions avec types ;
  • preuves avec termes (= programmes) ;
  • implication logique (PQ) avec types fonctions (στ, qui correspond aux fonctions prenant une valeur de type σ et renvoyant une valeur de type τ) ;
  • modus ponens (application d'une implication : si PQ et P alors Q) avec application d'une fonction (une fonction στ s'applique à un type σ pour donner un type τ) ;
  • ouverture d'une hypothèse (pour démontrer une implication) avec λ-abstraction (= définition d'une fonction à partir d'un argument) ;
  • hypothèses actuellement ouvertes avec variables libres (en contexte) dans le programme ;
  • hypothèses déchargées avec variables liées dans le programme ;
  • conjonction (et logique : PQ) avec types produits (σ×τ, qui correspond aux données d'un couple d'une valeur de type σ et d'une valeur de type τ) ;
  • disjonction (ou logique : PQ) avec types produits (σ+τ, qui correspond aux données soit d'une valeur de type σ soit d'une valeur de type τ, avec un sélecteur qui indique dans quel cas on se trouve) ;
  • le vrai (noté ‘⊤’, affirmation tautologiquement vraie) avec le type unité (ayant une seule valeur, triviale) ;
  • le faux (noté ‘⊥’, affirmation tautologiquement fausse) avec le type vide (n'ayant aucune valeur) ;
  • quantification universelle ∀(v:U).P(v) (qui est une sorte de « conjonction en famille » ⋀v:U P(v) sur tous les v de type U) avec types produits en famille ∏v:U σ(v) (type des fonctions prenant un v de type U et renvoyant une valeur de type σ(v)) ;
  • quantification existentielle ∃(v:U).P(v) (qui est une sorte de « disjonction en famille » ⋁v:U P(v) sur les v de type U) avec types sommes en famille ∑v:U σ(v) (type des données d'un v₀ de type U et d'une valeur de type σ(v₀)).

La correspondance est surtout satisfaisante dans le sens des preuves vers les programmes, i.e., donnée une démonstration, arriver à construire un programme. C'est cette direction que je vais essayer d'exposer ci-après, en laissant globalement de côté la question de si on obtient tous les programmes de cette façon (ce qui demanderait d'expliquer précisément ce que sont « tous les programmes », et j'ai peur qu'on ne puisse avoir qu'une réponse un peu triviale en prenant la définition de programme qui fait rend Curry-Howard bijectif, c'est-à-dire de prendre pile-poil ceux qu'on peut fabriquer de la sorte : c'est en quelque sorte tout l'objet du typage que de limiter les programmes écrivibles à ceux que la correspondance de Curry-Howard atteint).

Bref, mon but dans la suite est d'exposer ça plus précisément, d'abord dans le cas purement propositionnel, c'est-à-dire sans quantificateurs (c'est nettement plus simple et si ça peut sembler ennuyeux je pense qu'il a déjà énormément à nous apprendre), et ensuite dire des choses plus vagues sur les quantificateurs (les quantificateurs posent toutes sortes de difficultés pénibles sur ce qu'on a le droit de quantifier exactement), en regardant d'un peu plus près la logique du premier ordre (qui est la forme de quantification la plus simple) ; je finis par parler de deux points indépendants (et que je ne comprends que de façon très imparfaite, donc je serai encore plus vague et à la limite de l'agitage de mains) : la question du sens du ‘∃’ d'une part, et l'imprédicativité de l'autre.

L'exposition que je vais faire ici suit pour le début la même idée que mon cours, pour laquelle on peut se référer à ce jeu de transparents pour la partie propositionnelle, mais je vais plutôt partir du côté preuves et ne pas entrer dans une description précise de ce qu'est le λ-calcul simplement typé. En revanche, la fin de ce billet va nettement au-delà de ce que je compte exposer dans mon cours (la partie de mon cours sur les quantificateurs est encore à l'état d'ébauche au moment où j'écris ce paragraphe, mais de toute façon je ne vais pas dire grand-chose).

Puisque ce sera le côté « preuves », je commence par des explications sur la logique intuitionniste (propositionnelle pour commencer) et sur ses règles de démonstration : on peut aussi se référer à ce billet passé pour le contexte général (y compris historique) sur les maths constructives, et cet autre billet (assez mal écrit) pour une description un peu différente des règles de la logique (en style « calcul des séquents »).

↑Entry #2773 [older| permalink|newer] / ↑Entrée #2773 [précédente| permalien|suivante] ↑

↓Entry #2772 [older| permalink|newer] / ↓Entrée #2772 [précédente| permalien|suivante] ↓

(dimanche)

Les Indes fourbes d'Ayroles et Guarnido

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.

↑Entry #2772 [older| permalink|newer] / ↑Entrée #2772 [précédente| permalien|suivante] ↑

↓Entry #2771 [older| permalink|newer] / ↓Entrée #2771 [précédente| permalien|suivante] ↓

(vendredi)

Où j'apprends aussi l'informatique en l'enseignant

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 , 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.

↑Entry #2771 [older| permalink|newer] / ↑Entrée #2771 [précédente| permalien|suivante] ↑

Continue to older entries. / Continuer à lire les entrées plus anciennes.


Entries by month / Entrées par mois:

2024 Jan 2024 Feb 2024 Mar 2024 Apr 2024 May 2024 Jun 2024
2023 Jan 2023 Feb 2023 Mar 2023 Apr 2023 May 2023 Jun 2023 Jul 2023 Aug 2023 Sep 2023 Oct 2023 Nov 2023 Dec 2023
2022 Jan 2022 Feb 2022 Mar 2022 Apr 2022 May 2022 Jun 2022 Jul 2022 Aug 2022 Sep 2022 Oct 2022 Nov 2022 Dec 2022
2021 Jan 2021 Feb 2021 Mar 2021 Apr 2021 May 2021 Jun 2021 Jul 2021 Aug 2021 Sep 2021 Oct 2021 Nov 2021 Dec 2021
2020 Jan 2020 Feb 2020 Mar 2020 Apr 2020 May 2020 Jun 2020 Jul 2020 Aug 2020 Sep 2020 Oct 2020 Nov 2020 Dec 2020
2019 Jan 2019 Feb 2019 Mar 2019 Apr 2019 May 2019 Jun 2019 Jul 2019 Aug 2019 Sep 2019 Oct 2019 Nov 2019 Dec 2019
2018 Jan 2018 Feb 2018 Mar 2018 Apr 2018 May 2018 Jun 2018 Jul 2018 Aug 2018 Sep 2018 Oct 2018 Nov 2018 Dec 2018
2017 Jan 2017 Feb 2017 Mar 2017 Apr 2017 May 2017 Jun 2017 Jul 2017 Aug 2017 Sep 2017 Oct 2017 Nov 2017 Dec 2017
2016 Jan 2016 Feb 2016 Mar 2016 Apr 2016 May 2016 Jun 2016 Jul 2016 Aug 2016 Sep 2016 Oct 2016 Nov 2016 Dec 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

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]