David Madore's WebLog: 2023-11

Digression préliminaire : Je suis pas mal sous l'eau en ce moment : le problème principal étant que je rédige le cours d'informatique que je donne en ce moment à Télécom moins vite que le cours n'avance : pour l'instant j'ai encore un peu d'avance, mais je ne suis pas convaincu par l'argument de Monsieur Zénon qui m'assure qu'Achille ne peut pas rattraper la Tortue ; surtout qu'en plus de ça, la Tortue se laisse distraire en chemin, c'est-à-dire que j'ai eu le malheur de commencer à réfléchir à des questions comme ça qui n'ont rien, ou très peu, à voir avec ce que je suis censé enseigner, mais qui font partie de réflexions sur lesquelles je reviens périodiquement. En plus, j'ai déjà un billet de blog en cours d'écriture et que j'ai arrêté pour ne pas perdre trop de temps avec. Néanmoins, comme j'ai beaucoup aimé le livre dont je veux parler ici, je vais quand même prendre le temps d'écrire quelque chose, en essayant d'être un peu bref (et vue la longueur de ce paragraphe, ce n'est pas bien parti).

Je connaissais déjà l'autrice/dessinatrice Tiphaine Rivière à travers sa bédé Carnets de Thèse, laquelle raconte le parcours partiellement autobiographique d'une doctorante en lettres qui part avec l'enthousiasme de quelqu'un qui se dit qu'elle va découvrir le monde de la recherche et qui connaît rapidement la désillusion entre les années de thèse qui s'accumulent sans qu'on n'en voie le bout, l'absence de financement qui l'oblige à enseigner en parallèle jusqu'à l'épuisement, le directeur de thèse qui a plein de doctorants et ne s'occupe pas du tout d'elle, la famille qui ne comprend rien à ce qu'elle fait, le copain avec qui elle finit par rompre, etc. On pourra se dire qu'elle force le trait, mais j'ai connu assez de doctorants en lettres et sciences humaines pour savoir que tous ces clichés sont parfois — trop souvent — vrais. J'avais beaucoup aimé ce livre aigre-doux, et je le recommande ne serait-ce que comme avertissement préalable à toutes les personnes qui envisagent de se lancer dans un doctorat (surtout dans une discipline littéraire, mais même en sciences : au minimum il faut retenir l'avertissement de bien se renseigner auprès d'anciens thésards sur l'ambiance du labo, la manière dont l'encadrant de thèse traite ses doctorants et leur consacre son attention, etc.).

Bref, quand j'ai vu que Tiphaine Rivière avait sorti une autre bédé où je pouvais penser que son talent d'observation des situations humaines et sociales serait bien employé, j'ai sauté dessus.

Il s'agit de La Distinction, sous-titré Librement inspiré du livre de Pierre Bourdieu, et c'est à la fois une histoire (ou plutôt un tas de petites histoires ou saynètes, cf. mes réflexions à ce sujet ici concernant une autre bédé), et de la vulgarisation sociologique.

Je dois préciser d'emblée que je n'ai pas lu l'ouvrage source, La Distinction : Critique sociale du jugement (même si maintenant j'ai envie de le faire) : j'ai bien sûr[#] été exposé à un certain nombre des idées de Bourdieu (à commencer par la notion de capital culturel) à travers d'autres gens qui ont repris ses idées, à travers des discussions politiques, à travers des résumés ou compte-rendus divers et variés, donc ce n'est pas comme si je découvrais. Mais je suis également loin d'en avoir une connaissance approfondie, ou même une idée bien précise. Donc je ne peux pas juger si Tiphaine Rivière reproduit fidèlement les idées de Bourdieu (à part les passages qu'elle cite textuellement), ou si elle ajoute des idées de fond d'elle-même, combien elle transpose pour s'ajuster aux quelques décennies qui se sont écoulées depuis 1979. Mais ça ne me semble pas terriblement important.

[#] Le bien sûr ici est lui-même marqueur du capital culturel de la classe sociale à laquelle j'appartiens ; cf. aussi ce que j'écrivais ici sur la culture générale (et où d'ailleurs je mentionne Bourdieu au passage).

Ce qui est intéressant, et que je trouve très réussi, c'est qu'elle mélange assez habilement une exposition des thèses de Bourdieu et une illustration de celles-ci à travers des anecdotes qu'elle représente, ce qui rend les thèses à la fois plus compréhensibles (si j'en juge par les passages cités qui ne sont pas toujours franchement limpides), plus parlantes et plus convaincantes.

Et la bédé a un petit côté méta (j'ai déjà dit que j'aimais le méta ? ah oui) : car le point de départ en est un (nouveau) professeur de sciences économiques et sociales dans un lycée plutôt défavorisé, qui décide d'essayer d'enseigner à ses élèves les idées de Bourdieu. Évidemment, ça ne marche pas facilement (comme je l'ai dit plus haut à propos de Carnets de Thèse, Tiphaine Rivière est bien consciente que l'enseignement n'est pas toujours facile). Donc on a une sorte de double lecture : la bédé montre en même temps le prof qui essaye de démontrer et faire comprendre à ses élèves que, par exemple, le capital économique (l'argent !) n'est pas la seule distinction entre classes sociales[#2], et des situations qui illustrent ces idées, et les deux se rejoignent souvent. C'est assez délicieusement fait (par exemple j'ai beaucoup aimé les passages où une des élèves de la classe lit des passages du livre à ses parents en leur disant ah tiens, c'est marrant, vous faites exactement comme Bourdieu explique à propos des petits bourgeois, et les énerve parce que personne n'aime se trouver renvoyé aux clichés de sa classe sociale).

[#2] Par exemple quelque chose comme ceci (c'est moi qui paraphrase) : Est-ce que vous êtes déjà allés à l'opéra ? ― Non ! ― Et pourquoi pas ? ― Parce que c'est trop cher ! ― D'accord. Mais si vous aviez tout d'un coup plein d'argent, est-ce que vous vous mettriez à aller à l'opéra ? ― Ben non.

Les personnages sont assez nombreux, et assez variés, illustrant par exemple assez bien le fait que le patrimoine culturel n'est pas forcément parfaitement corrélé au patrimoine économique, qu'il y a cinquante nuances de bourgeois, etc. Mais ça ne tourne pas non plus à l'inventaire sans intérêt, et ces personnages sont au moins indirectement raccordés à l'histoire.

Il n'y a pas vraiment un arc narratif clair ni de conclusion savamment construite, mais je ne trouve pas que ce soit un défaut (il y a quand même une histoire, et une situation qui évolue, mais ce n'est pas le plus important). Le dessin (je veux dire, le dessin graphique) est moins détaillé que dans Carnets de Thèse (c'est en noir et blanc, et il n'y a pas ce que Boulet appelle les petits traits), mais j'ai eu l'impression que la peinture sociologique était tout à fait précise. En tout cas, à moi qui ne suis pas sociologue (mais quand même, j'espère, un peu observateur de la société et des comportements des gens) les portraits des personnages et des situations sonnent juste, et souvent juste dans le sens c'est un cliché, mais malheureusement ce cliché est vrai. Pas que je ne croyais pas à (disons) la réalité des distinctions sociales dans le domaine des goûts, mais je n'y pense pas trop, ou peut-être que j'essaie de ne pas y penser, et la représentation en bédé oblige à y penser, de manière à la fois éclairante et dérangeante.

Parce que c'est peut-être ce qui nous met le plus mal à l'aise avec la sociologie, c'est combien cette idée de déterminisme social, en nous renvoyant aux clichés auxquels nous nous conformons malgré nous, vient gifler notre désir (dans une certaine mesure illusoire) de liberté et d'individualité en nous rappelant combien nos goûts sont socialement construits et largement le fruit de notre classe sociale. Y compris, et ça fait encore plus mal, la rébellion contre le déterminisme social qui est elle-même le propre d'une certaine catégorie sociologique. Tout ça est profondément déprimant (je trouve), un peu comme la prédestination dans une tragédie grecque ; et la bédé dont je parle a donc, comme Carnets de Thèse, un côté décidément aigre-doux, triste en même temps qu'il est souvent drôle. (On se doute bien, par exemple, que la relation qu'essaient d'avoir deux ados de classes sociales très différentes, risque de ne pas durer longtemps, et d'ailleurs le père de la jeune bourgeoise qui fréquente un garçon des cités hausse les épaules en disant en substance ça ne durera pas, ça lui passera.)

Mais c'est précisément parce que cette gifle fait du bien qu'il faut lire ce livre !

La Distinction (Librement inspiré du livre de Pierre Bourdieu) de Tiphaine Rivière, 287 pages, éditions La Découverte Delcourt.

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

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

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

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

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

[Lire la suite…]

Au sujet des notes de cours signalées dans le billet précédent, on me fait remarquer en commentaire, d'ailleurs pas très agréablement, que j'ai écrit intention (dans le contexte d'un contraste avec extension) là où je voulais sans doute écrire intension. Alors, est-ce une erreur, ou quelle écriture est-elle préférable ? À vrai dire je m'y perds assez.

Bon, déjà en général je déteste ces mots en -/sjɔ̃/ dont on je sait jamais si on doit les écrire -tion ou -sion (sans parler des différences gratuites entre l'anglais et le français, comme le fait que contorsion, distorsion et extorsion et parfois distension mais pas torsion s'écrivent, en anglais, avec -tion là où le français met -sion : comment voulez-vous retenir quelque chose de pareil[#0] ?). Donc déjà le fait qu'on ait extension avec -sion mais intention avec -tion, tandis que distension hésite, est vraiment pénible. Mais peut-être justement qu'il y a deux mots distincts, intention et intension ? C'est là que ça devient hautement confus.

[#0] Digression (2023-11-05) : Comme on me le signale en commentaire, j'oubliais aussi l'hésitation entre -ction et -xion : annexion mais exaction, complexion mais élection. Bon, encore, ceux-là on peut les retenir au fait qu'il y a des mots annexe et complexe. Mais parfois le français et l'anglais font des choix différents, ou bien l'anglais hésite : connexion, inflexion, réflexion, génuflexion et peut-être parfois même flexion lui-même s'écrivent, en anglais, avec -ction, au moins en anglais américain parce que l'anglais britannique hésite plus, alors que le français met -xion. (Le fait que connexion s'écrive -xion en français et -ction en anglais peut se retenir au fait que connexe en français se dit connected en anglais, mais reflex existe bien en anglais sans que ça empêche d'écrire reflection. Soupir.)

Indubitablement, certains dictionnaires contiennent bien un mot intension (qui n'est pas le même que intention). Ou peut-être même qu'il y a plusieurs mots intension différents ? La 5e édition (1798) du Dictionnaire de l'Académie française donne : INTENSION. sub. fém. Terme de Physique. Force, véhémence, ardeur. L'intension de la fièvre. — ce qui ne m'aide pas et ce qui n'est clairement pas le sens que je veux, et de toute façon ce mot semble avoir mystérieusement disparu des éditions ultérieures. Au moment où j'écris, le TLF en ligne semble en rade, donc je ne peux pas vérifier s'il a le mot intension et avec quel sens[#]. Mais dans Wiktionary en français, on trouve intension \ɛ̃.tɑ̃.sjɔ̃\ féminin 1. (Logique) Désignation d’un ensemble d’éléments par un prédicat qu’ils vérifient. En anglais, le American Heritage Dictionary of the English Language me dit : in·ten·sion (ĭn-tĕnʹshən) n. 1. The state or quality of being intense; intensity. 2. The act of becoming intense or more intense; intensification. 3. Logic. The sum of the attributes contained in a term. [Latin intēnsiō, intēnsiōn-, from intēnsus, stretched. See intense.] — in·tenʹsion·al adj. Et dans Wiktionary en anglais, je lis : intension (plural intensions) […] 2. (logic, semantics) Any property or quality connoted by a word, phrase or other symbol, contrasted with actual instances in the real world to which the term applies.

[#] Voici : INTENSION, subst. fém. A. - Vx. Force, ardeur. L'intension de la fièvre (Ac. 1798). B. - LOG., LING., vieilli. Synon. de compréhension (d'un concept, d'un terme). Anton. extension. Plus l'intension d'un terme (le nombre de traits) est grande, plus l'extension (la classe des objets dénotés) est restreinte. Il faut plus de traits pour définir hêtre que pour définir arbre, mais il y a dans l'univers observé plus d'arbres que de hêtres (MOUNIN 1974).

Voilà qui ne m'aide pas des masses, et honnêtement je ne comprends pas vraiment ces définitions.

L'étymologie n'est pas d'un grand secours non plus. En latin, intēnsiō et intēntiō existent tous les deux, mais ils ont l'air vaguement interchangeables. Le Gaffiot donne : intensĭo, ōnis, f. (intendo), action de tendre, tension — et il donne un plus grand nombre de sens pour intentĭo, mais le premier est le même. (À ce sujet, le Gaffiot a aussi les deux mots extensĭo et extentĭo, mais là l'un renvoie simplement à l'autre ; ça suggère en tout cas qu'il n'y a pas vraiment de raison étymologique forte au fait d'écrire extension avec -sion et intention avec -tion.)

Bon alors qu'est-ce que c'est que cette histoire du mot intension et quel est son sens en logique ?

Je ne suis pas sûr de comprendre le sens général.

Le sens dans lequel je l'utilisais (avec l'orthographe en -tion, mais peut-être que je vais changer) dans mes notes est le suivant : si on a un programme/algorithme qui calcule une fonction, alors ce programme/algorithme est l'intention (ou peut-être justement plutôt l'intension, donc… bon, écrivons intenſion comme une sorte de compromis) tandis que la fonction calculée est l'extension. C'est important de faire la distinction parce qu'une même fonction peut être calculée par toutes sortes d'algorithmes différents. (Et le théorème de Rice nous dit essentiellement qu'on ne peut rien dire de non-trivial — calculablement et à coup sûr — sur l'extension rien qu'en regardant l'intenſion.)

En théorie des ensembles, l'extension d'un ensemble, c'est justement l'ensemble de ses éléments. Et l'axiome d'extensionalité nous dit que deux ensembles ayant les mêmes éléments sont égaux (dans l'autre sens ça fait partie de la définition même de l'égalité). L'intenſion, si je me base sur la définition donnée par Wiktionary, ce serait une propriété définissant l'ensemble implicitement : par exemple {0,1,2} serait un ensemble défini en extension alors que {n∈ℕ : n≤2} serait le même ensemble définit en intenſion.

Déjà, je ne suis pas franchement convaincu que les deux sens décrits aux deux paragraphes précédents soient exactement le même, ni quel serait le sens général. Mais l'idée approximative est que l'extension est une description explicite (d'une fonction par ses valeurs, d'un ensemble par ses éléments) de l'objet désigné, alors que l'intenſion est une description par une caractérisation du sens, ou quelque chose comme ça.

Du coup, je peux très bien rapprocher ça du mot intention au sens de volonté de faire quelque chose : en décrivant un algorithme pour une fonction, je veux fabriquer cette fonction, donc l'algorithme est l'intention qui produit la fonction. Ceci justifierait d'écrire le mot en -tion et de l'identifier avec le mot usuel intention (but, volonté).

[Ajout 2023-11-03 :] Ce qui est bizarre, c'est qu'il y a une distinction que je comprends bien, c'est celle entre extensif et intensif : extensif fait référence à quelque chose qui tend à s'étendre, i.e., tendu vers l'extérieur, alors qu'intensif fait référence à quelque chose qui tend à s'intensifier (← oui, OK, c'est une lapalissade), i.e., tendu vers l'intérieur. Je comprends par exemple bien la différence entre agriculture extensive (qui utilise de l'espace) et agriculture intensive (qui maximise ses rendements à surface donnée) ou, en physique, entre une grandeur extensive (qui double quand on double la quantité de choses considérées, p.ex. la masse ou le volume) et une grandeur intensive (qui reste la même quand on double la quantité de choses considérées, p.ex. la température ou la pression). Mais cette distinction extensif/intensif (pour laquelle je n'ai aucun doute sur l'orthographe en -s-) semble avoir assez peu de rapport avec la distinction extension/intenſion dont je parle ici (en tout cas je ne vois pas pourquoi l'un correspondrait à tendre vers l'extérieur et l'autre vers l'intérieur).

Une explication plus détaillée, mais dont honnêtement je ne comprends las bien les subtilités, sur la distinction entre extensionnel et intenſionnel en logique ou en philosophie est sur cette page de la Stanford Encyclopedia of Philosophy et celle-ci sur Wikipedia (voir aussi cet autre passage sur Wikipédia s'agissant précisément des théories des types intuitionnistes ; je sais que Martin-Löf en a inventé plusieurs qu'on désigne justement en en qualifiant certaines d'extensionnelles et d'autres d'itenſionnelles). Mais je trouve que tout ça est plus confus qu'éclairant (disons que j'ai l'impression confuse qu'on mélange plusieurs distinctions qui ne sont pas la même, notamment le fait de décrire un objet par son identité ou par une caractérisation, et le fait de s'intéresser à des égalités contingentes ou nécessaires, ce qui sont deux questions qui me semblent sans rapport).

Un exemple qu'on donne souvent, mais là aussi je ne suis pas sûr de pouvoir le relier clairement aux usages évoqués ci-dessus, est quelque chose comme le syllogisme fallacieux suivant (attention, divulgâchis concernant le film Star Wars) :

Luke Skywalker veut devenir comme son père.

Darth Vader est le père de Luke Skywalker.

Donc : Luke Skywalker veut devenir comme Darth Vader.

Si on veut expliquer l'erreur en parlant d'extension et d'intenſion, l'idée est que bien que Darth Vader soit le père de Luke Skywalker en extension (ce sont la même personne), l'intenſion, au moins dans la tête de Luke, est différente, puisqu'il n'a pas cette information (ou même quand il l'a, il y pense différemment). Donc on ne peut pas substituer une égalité extensionnelle dans un énoncé qui dépend des intenſions.

(Mais à vrai dire, moi, j'aurais plutôt tendance à analyser ça en termes de logique modale et mondes possibles : le fait que dans un monde donné on ait x=y, n'est pas la même chose que de dire que x et y sont nécessairement égaux, c'est-à-dire égaux dans tous les mondes possibles, et notamment dans le monde que Luke a dans sa tête. Ce n'est pas clair pour moi si cette analyse en termes de logique modale et mondes possibles soit compatible avec l'analyse en terme d'extension/intenſion que je viens de donner.)

Là aussi, je n'ai pas trop de mal à identifier le mot que je persiste à écrire intenſion pour signifier mon doute sur l'orthographe, avec le mot intention tout à fait habituel et qu'on écrit -tion de façon standard : on parle justement des intentions de Luke. Pourquoi une orthographe différente ?

Du coup je ne sais toujours pas si intension est une variante orthographique du mot intention qui s'est spécialisée dans ce sens bizarre en philo / logique / linguistique, ou si c'est un mot distinct (même si, in fine, ils viennent quand même de la même origine latine).

C'est peut-être comme mise en abyme, qui est juste une variante graphique de abîme, mais c'est quand même le même mot. (En l'occurrence, il semble que ce soit André Gide qui ait popularisé cette expression dans son sens figuré, avec cette orthographe particulière : ça vient de l'héraldique mais il n'y a pas spécialement de raison de préférer l'orthographe en ‘y’. Ceci étant, maintenant qu'elle s'est imposée, on peut trouver que ce n'est pas plus mal d'avoir cette spécialisation.)

Maintenant, comme il y a indubitablement des gens qui utilisent scrupuleusement l'orthographe intension pour les différents sens que je n'ai pas réussi à rendre très clairs ci-dessus, peut-être que c'est une bonne idée de se rallier à cette convention comme on peut choisir d'écrire mise en abyme avec ‘y’ même s'il n'y a pas de raison étymologique à le faire.

Ceci étant, on peut se demander comment est apparue cette écriture intension avec ce sens (je veux dire, celui de la philo / logique, pas celui donné par l'édition de 1798 du Dictionnaire de l'Académie), indépendamment du fait que ce soit ou non un mot distinct de intention. L'article de la Stanford Encyclopedia of Philosophy cité ci-dessus semble dire que c'est Carnap le coupable. (The Port-Royal Logic used terminology that translates as “comprehension” and “denotation” for this. John Stuart Mill used “connotation” and “denotation.” Frege famously used “Sinn” and “Bedeutung,” often left untranslated, but when translated, these usually become “sense” and “reference.” Carnap settled on “intension” and “extension.” However expressed, and with variation from author to author, the essential dichotomy is that between what a term means, and what it denotes.) Mais la Wikipédia en allemand évoque aussi Leibniz, qui aurait alors certainement l'antériorité sur Carnap.

Évidemment, si l'inventeur du terme (qu'il s'agisse de Carnap ou Leibniz) écrivait en allemand, langue dans laquelle intention se dit Absicht (même si Intention se trouve aussi), le fait d'avoir choisi l'écriture Intension comme pendant à Extension n'est pas aussi significatif qu'en français ou en anglais.

Quoi qu'il en soit, je reste assez dubitatif sur la question de si on doit considérer que intension est un mot distinct de intention, comme sur celle de savoir si on doit se tenir à cette orthographe (cette fantaisie de Carnap comme abyme en est une de Gide ?), et, en fait, sur la signification (ou peut-être la significasion ?) générale de cette histoire d'intenſionalité.

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

Ces transparents sont en ligne ici

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

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

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

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

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

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

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

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

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

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

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