David Madore's WebLog: 2026-04

J'ai commencé à écrire ce billet en me disant que j'allais poster des versions condensées de divers trucs dont j'ai envisagé de faire des billets plus longs mais je n'ai pas eu le temps. Sauf qu'en fait j'ai écrit quelque chose d'un peu long pour chacun, et que j'en ai eu marre à chaque fois, donc j'aurais vraiment mieux fait de faire des billets séparés plutôt qu'un seul billet six-en-un. (Il y aurait aussi sans doute une auto-analyse psychologique intéressante à mener sur pourquoi j'arrive à me convaincre d'essayer poster des choses plus courtes — enfin, tout est relatif — à condition d'en mettre plusieurs dans un billet, mais je n'ai pas le temps pour ça maintenant non plus.)

• Pas de progrès du côté de l'archivage de ce site
• Activation du HTTPS ?
• Gmail traite mon mail comme du spam
• Je m'achète une voiture
• Construction projective d'un point à partir de n points
• Deux remarques sur l'approximation diophantienne

❦

Pas de progrès du côté de l'archivage de ce site

Je commence par ce qui n'est pas une nouvelle du tout, c'est même le contraire : j'avais raconté il y a un an que la Wayback Machine de l'Internet Archive n'arrive plus à archiver ce site (or s'il y a une chose à quoi je tiens beaucoup, c'est la préservation de l'information). Deux choses sont maintenant certaines : ① ce n'est pas volontaire (c'est un bug), et ② c'est lié au fait que ce site est (pour les raisons que j'ai expliquées ici) servi en HTTP et pas en HTTPS, même si le problème est sans doute causé par une conjonction de facteurs et j'ignore quels peuvent être les autres. Je soupçonne qu'il s'agit d'une sorte de firewall trop agressif qu'ils ont mis en place suite à des attaques diverses qu'ils ont subies, et qui est probablement mal calibré pour le HTTP parce que l'immense majorité des sites sont maintenant en HTTPS et que les HTTP sert donc essentiellement à renvoyer des redirections vers HTTPS. Je soupçonne quand même qu'il y a des conditions où HTTP marche encore sur l'Archive, parce que sinon ils se seraient rendu compte du problème plus tôt, mais je n'en sais pas plus. (Si des gens qui me lisent ont la possibilité de mener tes tests, je vous en supplie, faites-le, je suis preneur de tous renseignements.)

En attendant j'ai pris l'habitude de faire une copie de sauvegarde de mes billets de blog sur Archive.today (un site qui a plein de noms alternatifs : Archive.is, Archive.ph et d'autres). Le problème est qu'on ne sait pas qui est derrière ce truc, et que ses intentions ne sont pas claires : au minimum, on sait qu'il en profite pour faire résoudre des captchas aux gens qui s'en servent, et qu'il a lancé des attaques denial-of-service ; et j'ai aussi entendu passer l'information selon laquelle il aurait truqué des archives, bref, ce n'est pas une solution de repli raisonnable, sauf à court terme. J'aimerais vraiment pouvoir revenir à l'Internet Archive.

Le problème est qu'il est quasi impossible de contacter l'Internet Archive pour essayer d'attirer l'attention sur le problème qui me concerne. J'ai essayé de leur écrire plusieurs fois, ça tombe dans un trou noir. J'ai essayé d'envoyer un courrier papier (vous savez, le truc du siècle dernier, ou on met un timbre sur une enveloppe), c'est aussi tombé dans un trou noir. Puis un jour (2025-05-13) j'ai eu une réponse surgie de l'espace disant qu'ils avaient identifié un problème et allaient le régler (We have identified an issue and are working on a fix. I will update you when we have implemented it.), du coup j'ai eu de l'espoir… sauf qu'en fait rien ne s'est passé, et le problème n'a pas changé. Puis, il y a deux mois, nouvel espoir : j'ai eu une conversation sur Bluesky avec Jason Scott, qui est un des personnages importants de l'Internet Archive, qui m'a assuré qu'ils n'étaient pas au bord de la faillite comme je le pensais, qui m'a dit qu'ils pouvaient tout à fait s'occuper de ce genre de choses, et et qui m'a dit de signaler mon problème par mail en le mettant en copie… ce que j'ai fait, il m'a dit avoir transmis à qui de droit, et… deux mois plus tard, toujours pas le moindre signe de changement.

Bref, j'ai bien peur qu'il faille que j'admette que ce problème ne sera jamais réglé et que la seule option qui s'offre à moi est de rendre mon site accessible en HTTPS (enfin, encore faudrait-il être bien certain que ça réglera le problème, ce dont je ne suis pas sûr du tout). Je passe donc à l'item suivant de ce billet.

❦

Activation du HTTPS ?

Il va falloir que j'envisage (à reculons et à contrecœur, donc) de rendre mon site accessible en HTTPS. Puisque j'évoque le sujet, il faut d'ailleurs que je signale cette vidéo (que plusieurs contacts m'ont envoyée tant elle semble faite pour moi) de quelqu'un qui, pour en gros exactement les mêmes raisons que moi n'a pas envie de passer son site en HTTPS et qui le fait quand même en faisant exprès, pour protester, de rendre le HTTPS aussi peu sûr que possible : c'est rigolo, et surtout, en fait, on en apprend pas mal au passage sur le fonctionnement de HTTPS.

Je n'irai pas jusque là, même s'il est probable que je publie[#] la partie « privée » du certificat du site, juste pour me simplifier sa distribution d'une machine à l'autre. Ma question à moi est surtout comment je peux faire ce passage en minimisant les emmerdes que je vais devoir subir en conséquence de ces conneries. À commencer par le fait de devoir remettre en place tout le setup dès qu'un de mes serveurs claque entre mes doigts, ce qui arrive tous les quelques mois. (Exemple de problème : actuellement, je pare le problème des serveurs qui meurent tout le temps en ayant un serveur prêt à prendre le relais à tout instant, et j'ai simplement à changer le DNS pour faire pointer www.madore.org de l'un vers l'autre ; mais s'il y a un certificat à fournir, le serveur de secours ne peut pas obtenir lui-même par des canaux comme Lets Encrypt le certificat pour www.madore.org puisqu'il n'est, justement, pas accessible sous ce nom en temps normal ; donc il faut que je trouve un moyen de transférer le certificat vers le serveur de secours, et c'est d'ailleurs une des raisons pour lesquelles j'envisage de publier la partie privée du certificat pour simplifier la démarche.)

[#] Étant bien entendu que comme ce HTTPS ne sert rigoureusement à rien question sécurité vu que mon site ne contient rien de non-public, l'aspect « privé » de ce certificat est bidon, et il peut parfaitement être rendu public.

Une possibilité serait que j'utilise un certificat auto-signé, ce qui me permet d'avoir un unique certificat pour toutes mes machines et de m'affranchir de la limitation de durée de validité sur les certificats. Ce serait même plus raisonnable en termes de sécurité (si la sécurité était un enjeu, ce qu'elle n'est pas) parce que comme ça les gens qui veulent vraiment vérifier l'authenticité du site pourraient s'assurer que le certificat ne change jamais, alors que si on passe par Lets Encrypt il faut vérifier que la clé de signature ne change pas, et c'est beaucoup plus technique. Une chose est que l'usage d'un certificat auto-signé cause un message d'erreur pénible, mais bon, ça je m'en fous, c'est le problème des gens qui tiennent à utiliser HTTPS alors que ça ne sert à rien sur un site public. En revanche, ce n'est pas clair du tout ce que fait l'Internet Archive quand ils tombent sur un site en HTTPS dont le certificat est auto-signé, parce que l'Internet Archive est quand meme toute la raison de la manœuvre. Et je n'en ai aucune idée.

Mais la grosse grosse source de maux de tête, c'est ce que fait Google et ce qui se passe avec la canonisation des URL.

Le problème fondamental, c'est que les versions HTTP et HTTPS d'un site Web sont, du point de vue des standards, deux sites totalement séparés. Et Google n'aime pas que deux sites séparés dupliquent la même information : c'est pénalisant. Et pour ajouter l'injure à la blessure, par défaut il va considérer que HTTPS est le site principal (à renvoyer en priorité), alors que moi je veux exactement le contraire (je veux bien que le site soit accessible en HTTPS, mais je ne veux pas que Google renvoie des liens en HTTPS, qui seront probablement cassés la moitié du temps vu combien le système est compliqué et fragile). Je peux mettre un robots.txt interdisant à Google le parcours de la version en HTTPS, mais je ne suis pas certain que ça fonctionne, ni que ça suffise, ni que ça ne soit pas pénalisant. Et je ne sais pas non plus ce que fait Google quand il rencontre un certificat auto-signé si je choisis cette solution (s'il refuse d'accéder à la version HTTPS dans ces conditions, c'est parfait pour moi, mais encore faut-il être sûr qu'il n'en profite pas pour désindexer ou pénaliser la version HTTP).

Et puis il y a la question de comment persuader les gens qui partagent des liens vers mon site d'utiliser uniquement le lien en HTTP, même si le site est aussi accessible en HTTPS (par exemple, si je mets un robots.txt qui interdit la version HTTPS à Google, c'est indispensable sinon les liens HTTPS seront en quelque sorte perdus ; et à l'inverse, si je ne le fais pas, je vais me retrouver avec du crawling en double, par exemple toutes les IA avides de texte vont probablement tout récupérer deux fois). Je peux mettre un bandeau en tête de page avec du JavaScript, mais c'est chiant pour tout le monde.

À un moment je m'étais dit que je créerais un domaine spécial appelé quelque chose comme www-https-sucks-please-do-not-use-this-url.madore.org et que le HTTPS soit accessible uniquement via ce domaine, mais alors ça ne règle rien côté Internet Archive parce que personne ne va penser à interroger les archives pour ce domaine spécial. Ou alors il faut que je mette en place une redirection de HTTP vers HTTPS uniquement si la requête vient de l'Internet Archive[#2].

[#2] Si je ne trouve pas de solution raisonnable sur comment faire cohabiter HTTP et HTTPS, peut-être que je choisirai le pis-aller qui est de n'ouvrir le port HTTPS que pour les IP de l'Internet Archive, et, pour elles et pour elles seulement, de faire une redirection de HTTP vers HTTPS. Donc tout le monde continuera à n'avoir que du HTTP sauf l'Internet Archive (ou peut-être les gens super motivés qui m'en feraient une demande exprès). Je n'aime pas trop cette solution (c'est une forme de géolocalisation, et je déteste le principe), mais elle a le mérite d'éviter les tracas liés à la question de ce que fera Google.

Bref, on voit le genre de questions sans fin auxquelles je suis confronté, et dont personne ne parle jamais quand on essaie de vous faire la propagande pour le HTTPS. Je ne peux même pas vraiment faire de tests, parce que le simple fait d'ouvrir le port HTTPS sur mon serveur n'est pas du tout anodin. Tout ça me prend vraiment la tête, et j'ai franchement autre chose à faire de mon temps que de devoir m'occuper de telles conneries. (Et j'ai bien peur que ça finisse en demande de conseils à des IA.)

❦

Gmail traite mon mail comme du spam

Continuons avec le chapitre Google m'emmerde avec une autre source de tracas dont je me serais bien passé :

En gros tous les mails que j'envoie vers Gmail sont considérés comme du spam.

Le problème est que j'ai un serveur mail personnel. OK, mais ce n'est pas nouveau, et franchement, ils abusent : j'ai publié des enregistrements SPF, tous mes mails sont signés par DKIM, il y a une politique DMARC, mon serveur a des enregistrements DNS valides, avant et arrière, il n'a jamais envoyé un seul spam (forcément, il ne sert qu'à mon courrier personnel, et je ne forwarde rien), absolument tous les champs concernant mon domaine sur postmaster.google.com sont verts, et pourtant le résultat est là : en gros, tous les mails que j'envoie vers n'importe quelle adresse Gmail atterrissent directement dans la boîte à spam[#3].

[#3] Peut-être que si le destinataire classifie pas du spam suffisamment souvent, alors le mail finit par arriver à être considéré comme non-spam. Mais je crois que même ça ne dure pas longtemps. (Malheureusement, mes interlocuteurs ne me donnent pas trop de feedback sur ce qui se passe. J'ai moi-même une adresse Gmail avec laquelle j'ai fait quelques tests, mais ce que j'observe n'est pas forcément universel.)

Même quand quelqu'un m'écrit à une adresse sur madore.org et que je réponds depuis exactement cette adresse-là, ça tombe (parfois ? toujours ? pas totalement clair) dans la boîte à spam. Google est vraiment nul, là : un mail qui répond, avec un message-ID valable, à un mail expédié depuis Gmail à cette adresse, et surtout si le mail est signé par DKIM, ça n'a juste aucun sens de considérer que ça peut être du spam.

Bon, le problème n'a pas que des inconvénients : généralement, quand j'envoie des mails, c'est plutôt qu'on m'a demandé quelque chose. Donc parfois ah ben j'aurais bien voulu te répondre [voire : je t'ai répondu], mais ce n'est pas ma faute si Gmail ne veut pas de mes messages peut être une excuse pratique pour ne pas répondre. Mais parfois je veux quand même contacter des gens sur Gmail. Ma solution temporaire est d'écrire depuis mon adresse mail professionnelle en mettant mon adresse personnelle en copie et les deux en reply-to ; ou bien d'envoyer un message par un autre canal (SMS, Signal, message privé sur un réseau social) pour dire je t'ai répondu, regarde dans ta boîte à spam. C'est quand même lourdingue.

Qu'est-ce qui se passe ? Je n'en sais rien. Comme je le dis plus haut, sur postmaster.google.com on me dit que tout va bien, que mon domaine n'a rien à se reprocher. Les rapports DMARC que Google m'envoie ne disent rien non plus. Le mail n'est pas rejeté : il est marqué comme spam.

Je ne sais pas exactement depuis quand ça date, parce que je n'écris pas si souvent que ça à des gens chez Gmail, et je ne sais pas forcément si mon mail s'est perdu ou que la personne a juste décidé de ne pas répondre. J'ai toujours eu quelques problèmes à écrire à des adresses Gmail, mais c'est bien pire maintenant qu'il y a quelques années.

[Lire la suite…]

Bon, pour l'instant c'est une prépublication[#], donc je mets un point d'interrogation parce qu'on n'est jamais sûr qu'une prépublication devienne vraiment une publication avant que ce soit fait, mais quoi qu'il en soit, je pense qu'il faut que j'en parle un peu sur ce blog, ne serait-ce que parce que c'est dans la continuation de choses que j'ai évoquées dessus, notamment ici et là. Aussi parce que mon coauteur me connaît via ce blog — ce qui prouve au passage que tenir un blog peut avoir un réel intérêt scientifique. Et accessoirement, parce que ce texte est indirectement responsable du fait que je n'ai rien écrit ici depuis longtemps (pas tant pour des questions de répartition du temps que de fatigue de rester coincé à taper sur un clavier).

[#] Aussi disponible ici sur HAL, parce que je trouve important que tout ne soit pas uniquement sur l'arXiv (il faudrait d'ailleurs que je parle un jour de l'arXiv, du service inestimable qu'elle rend à la communauté scientifique, mais aussi des problèmes qu'elle pose et du pouvoir qu'elle donne à l'université de Cornell ; mais à défaut vous pouvez lire ce que j'en ai écrit rapidement ici sur Reddit).

Je n'aime pas parler de mes publications parce que ça amène à des discussions complexes et potentiellement déplaisantes sur pourquoi j'en produis si peu, et de façon plus large sur le caractère restrictif et problématique d'évaluer la recherche sous l'unique angle des publications[#2], et sur l'évolution de la recherche en général. Je ne veux pas entrer dedans ici. La dernière fois que j'ai fait ça (billet au lien précédent), un commentateur très agressif s'est estimé obligé de m'attaquer personnellement, et j'ai écrit encore un billet pour lui répondre : ça suffit assez.

[#2] Pour résumer, les publications sont censées être un outil de communication entre chercheurs ; en les transformant en un outil d'évaluation, on subit de plein fouet la loi de Campbell/Goodhart, et cela nuit à la communication qui était le but initial du système (sans même parler des problèmes causés par la rapacité des éditeurs, qui sont liés mais distincts).

Mais il y a quand même une chose dont je suis content, car on sait mon attachement à l'éclectisme, c'est la diversité des thématiques mathématiques sur lesquelles j'ai écrit quelque chose : en cryptographie, en géométrie algébrique, en codes correcteurs, en géométrie combinatoire, en théorie des automates (je ne peux pas le lier pour l'instant, mais il y a un truc accepté qui sera présenté à la conf Latin 2026) ; et il faut que j'ajoute des textes qui pour des raisons diverses ne deviendront pas des publications sans que ce soit à cause de problèmes scientifiques, en théorie des graphes et en épidémiologie. (Sinon, j'ai aussi un truc récemment écrit en analyse réelle pour montrer essentiellement que le dual de Gel'fand de L^∞(ℝ) est la limite projective des compactifiés de Stone-Čech des ouverts denses de la topologie de la densité sur ℝ, mais j'ai peur que ce soit déjà considéré comme « bien connu », donc c'est plutôt de l'exposition que de la recherche à proprement parler et je ne sais pas bien quoi en faire.) Néanmoins, la calculabilité ou la logique manquaient cruellement à cette liste de sujets alors que ce sont des domaines qui m'intéressent énormément (et que j'ai décidé d'enseigner depuis quelques années à Télécom Trifouilly-lès-Saclay et sur lequel j'ai pas mal échangé sur MathOverflow).

Or, comme je l'avais dit dans ce billet où j'avais tenté de semi-vulgariser le sujet mais sans doute assez mal (et ici je l'avais vulgarisé, mais de façon très superficielle), j'ai été assez fasciné par la description faite par Takayuki Kihara dans cet article d'une notion d'oracles qui me semble à la fois très élégante et très générale, et à ce stade trop peu étudiée.

Ce texte est donc en partie une opération de publicité pour ces oracles à la Kihara, que nous appelons[#3] les degrés d'Arthur-Nimué-Merlin. Nous avons bien un résultat à nous à proposer, mais ça me motive au moins autant de faire la pub pour les degrés d'Arthur-Nimué-Merlin et leur étude en essayant de convaincre d'autres gens qu'ils sont intéressants et jolis à étudier (et notamment, en les décrivant de façon que j'espère pas trop compliquée).

[#3] La terminologie est un épouvantable sac de nœuds. Dans son article de 2023, Kihara les appelle topologies de Lawvere-Tierney sur le topos effectif, parce qu'ils leur sont équivalents, ou plus exactement, ils en fournissent une description concrète. Mais c'est un terme qui fait très peur à tous les gens qui ne savent pas ce qu'est un topos (en réalité, il n'est ni besoin de savoir ce qu'est un topos en général pour comprendre le topos effectif, ni besoin de comprendre ce qu'est le topos effectif pour comprendre ce qu'est une topologie de Lawvere-Tierney sur le topos effectif, ni besoin de comprendre ce qu'est une topologie de Lawvere-Tierney sur le topos effectif pour étudier les degrés d'Arthur-Nimué-Merlin, quoique ces liens soient éventuellement importants pour motiver les définitions) ; en en plus, on ne sait pas comment énoncer le théorème principal de l'article de Kihara qui, dans la terminologie que j'utilise, dit justement que les topologies de Lawvere-Tierney sur le topos effectif sont équivalents [isomorphes comme ensemble ordonnés] aux degrés d'Arthur-Nimué-Merlin : ce n'est pas parce que deux choses sont isomorphes qu'il faut les nommer de la même manière. Par ailleurs, les fonctions par lesquelles les degrés en question sont présentés sont appelées fonctions bicouche (bilayer function) dans l'article de 2023 et prédicats de Weihrauch étendus dans sa « présuite », ce qui pose encore d'autres problèmes (notamment parce que ce n'est pas du tout une réduction de Weihrauch qu'on regarde). Comme les personnages que Kihara utilise pour décrire son jeu sont Arthur, Nimué et Merlin (et que je n'aime pas nommer les gens d'après des personnes réelles, donc je ne veux pas dire degrés de Kihara), nous avons décidé d'utiliser le terme de degrés d'Arthur-Nimué-Merlin pour eux, au risque de provoquer cette situation.

Essayons donc de (semi-)vulgariser ici un minimum de quoi il est question. Mais pour ceux qui aiment plutôt les présentations sous forme de transparents, voici une présentation que j'ai faite la semaine dernière sur ce travail, et en voici une (un peu plus vieille) par mon coauteur.

Méta : Comme souvent quand j'écris sur ce blog, je ne sais pas bien à quel niveau de technicité me placer (à la fois parce que je sais que mon lectorat est très varié, allant de gens qui ne connaissent rien en maths — même si ceux-ci ont probablement déjà arrêté de lire à ce point du billet — à d'autres qui sont spécialistes du sujet, et aussi parce que je change moi-même d'avis). Donc, comme souvent, il faudra me pardonner une certaine incohérence en la matière, une remarque très technique pouvant s'insérer subrepticement dans un passage prétendant être de la vulgarisation : normalement on peut sans problème se contenter de les ignorer.

❦

Pour commencer, il y a une notion très standard en calculabilité, c'est la réduction de Turing (et les degrés de Turing) qu'elle définit. (C'est ce que j'avais essayé d'expliquer dans ce billet.) Disons de façon simplifiée qu'on dit qu'une fonction mathématique est calculable lorsqu'il existe un algorithme capable de la calculer (en temps fini, et de façon certaine) ; et qu'une fonction f est calculable relativement à une autre g lorsqu'il existe un algorithme capable de calculer f à condition qu'on fournisse à cet algorithme le moyen magique (auquel on donne le nom d'oracle) d'obtenir la valeur de g en n'importe quel point, aussi souvent qu'il le souhaite. (Quand je dis fonction, il faut imaginer une fonction prenant en entrée une donnée finie et renvoyant une donnée finie ; comme en calculabilité on ne préoccupe pas du tout de questions d'efficacité, on peut toujours supposée que les données finies sont représentées, fût-ce de façon tarabiscotée, par des entiers, donc on imagine qu'on a affaire à des fonctions des entiers vers les entiers. Cf. cet autre billet pour les bases.) Si on pose à l'oracle la question n, il répond par g(n), on a le droit de faire ça autant qu'on veut, et tout ce qu'on peut calculer par un algorithme utilisant un tel oracle est dit calculable relativement à g.

C'est cette notion de calculabilité relative qui porte le nom de réduction de Turing (on peut en définir plein d'autres, par exemple en limitant le nombre d'accès à l'oracle, mais c'est celle-là qui m'intéresse ici) : on dit que f est Turing-réductible à g dans les conditions que j'ai expliquées (f est calculable relativement à g), et on dit que f est Turing-équivalente à g, ou qu'elles ont le même degré de Turing, lorsque f est Turing-réductible à g et g à f. En quelque sorte, le degrés de Turing d'une fonction est une mesure d'incalculabilité : si f est calculable, son degré de Turing est 0 (le plus petit possible, celui qui ne nécessite aucun oracle, ou, ce qui revient au même, un oracle qui répond toujours 0 donc rien d'utile) ; et de façon plus générale, dire que f est calculable relativement à g, i.e., Turing-réductible à g, signifie exactement que le degré de Turing de f est inférieur ou égal à celui de g (c'est ce qui définit l'ordre sur les degrés de Turing), et intuitivement, qu'elle est « au pire aussi incalculable que g ».

Énormément de choses sont connues sur les degrés de Turing[#4]. On peut toujours chercher à en savoir plus, bien sûr, mais on peut aussi chercher à élargir la notion. Et c'est ce que font les degrés d'Arthur-Nimué-Merlin introduits par Kihara (ce ne sont cependant pas la seule généralisation possible ! mais elle me semble particulièrement intéressante).

[#4] Et aussi sur les degrés de Turing calculablement énumérables, c'est-à-dire ceux des fonctions de la forme est-ce que telle valeur apparaîtra dans une certaine suite calculable ? : ce n'est pas parce qu'une suite est calculable qu'on peut décider de façon calculable si une certaine valeur apparaîtra dedans, c'est même l'essence du problème de l'arrêt, mais c'est un type particulier et important de problème, dit semi-décidable parce que si la réponse est oui on finit toujours par le savoir ; et les degrés de Turing qu'ils définissent ont été étudiés spécifiquement : il s'avère qu'ils se comportent assez différemment des degrés de Turing en général. (Par exemple, il existe des degrés de Turing >0 minimaux, mais ils ne peuvent pas être calculablement énumérables, parce que si a<b sont deux degrés c.é. il y en a toujours un troisième strictement compris entre les deux.)

La manière dont j'aime présenter les choses, c'est que cette généralisation se fait en trois étapes : si je renomme en degrés T0 les degrés de Turing ordinaires :

• Au niveau T1, on autorise des fonctions partielles, c'est-à-dire que certaines questions sont interdites (la valeur g(n) n'est pas définie) : si on les pose, l'oracle ne répond pas, et, pire, ça casse tout le processus calculatoire (disons que l'oracle vous tue si vous lui posez une question interdite). Symétriquement, bien sûr, quand on vous demande de calculer une telle fonction f, on ne vous demandera de calculer que des valeurs définies.

  C'est une extension qui peut sembler mineure, mais qui pousse déjà la notion en-dehors de ce qui a été très étudié. (Il y a quand même cet article, dont Kihara est coauteur, sur ce que j'appelle les degrés T1 et que lui a choisi d'appeler « degrés de sous-Turing » — et d'ailleurs, de façon amusante, il me crédite pour l'introduction de la notion parce que j'avais posé cette question sur MathOverflow il y a longtemps.)

• Au niveau T2, on autorise le non-déterminisme, ou plus exactement le non-déterminisme adversarial. C'est-à-dire que certaines questions à l'oracle peuvent avoir plusieurs réponses possibles (la fonction g est remplacée par une multifonction, ou, si on n'aime pas cette notion, par une fonction renvoyant un ensemble d'entiers naturels — les valeurs autorisées — plutôt qu'un seul) : l'oracle vous fournira une des réponses possibles, mais sans aucune garantie sur laquelle. Symétriquement, bien sûr, quand on vous demande de calculer une fonction f admettant plusieurs valeurs, votre but est de fournir n'importe laquelle.

  Comme le calcul doit fonctionner quelles que soit les valeurs renvoyées par l'oracle, il faut imaginer que l'oracle essaye de vous embêter : la réduction de f à g devient alors une forme de jeu, où Arthur (le programme) essaye de mener un calcul, et quand il interroge l'oracle, un autre joueur, Merlin (son adversaire) choisit les valeurs renvoyées parmi celles autorisées par la fonction g, en essayant de faire échouer le calcul. On dira que f est T2-réductible à g lorsque Arthur a une stratégie calculable, c'est-à-dire qu'un programme peut jouer sa partie, pour interroger l'oracle et finalement déclarer une valeur finale correcte quelles que soient les réponses faites par Merlin.

• Au niveau T3, Kihara introduit encore un personnage dans le jeu : Nimué, qui est l'alliée d'Arthur contre Merlin, et qui essaie d'aider le calcul alors que Merlin essaie de le faire échouer. C'est donc une autre forme de non-déterminisme, si on veut, mais du non-déterminisme coopératif : côté Nimué, l'oracle vous fournit la meilleure réponse possible, alors que côté Merlin il faut s'attendre à ce qu'il fournisse la pire possible.

  Il y a diverses façons de voir ça. On peut dire que Nimué et Merlin sont les deux faces de l'oracle : Nimué en est la face amicale, qui fournit la meilleure réponse possible (du point de vue d'Arthur), mais qui ne peut pas communiquer directement à Arthur, elle fait un choix qui contraint celui de Merlin qui, lui, est la face hostile de l'oracle ; et Arthur ne voit que sortie finale (celle que lui donne Merlin). On peut aussi dire que l'oracle est la seule personne de Merlin, et alors Arthur et Nimué l'interrogent de façon conjointe, Arthur étant limité à mener une stratégie calculable, alors que Nimué, son ange gardien, complète magiquement ses coups sans qu'Arthur puisse voir directement ce qu'elle fait. Ou on peut voir le jeu comme un problème de communication entre Arthur et Nimué : Nimué est omnisciente mais elle ne peut envoyer d'informations à Arthur qu'en passant par Merlin, qui est leur adversaire.

  Le personnage de Nimué est aussi une façon commode de définir rigoureusement ce que cela signifie d'interroger un oracle omniscient, en évitant l'embêtement des questions auto-référentielles du style quelle ne sera pas ta réponse à cette question ? — on postule un personnage qui n'est pas limité à agir de façon calculable, et qui fournit ou oriente les réponses en ayant intérêt à faire gagner Arthur (celui qui pose les questions).

[Lire la suite…]