David Madore's WebLog: Premier article en calculabilité ?

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

Mathématiquement, un oracle de niveau T3 se définit indifféremment soit par une fonction g : ℕ → 𝒫(𝒫(ℕ)) soit par une fonction partielle ǧ : ℕ × Λ ⇢ 𝒫(ℕ) (où Λ est un ensemble non spécifié quelconque, qui dépend de l'oracle). Quand Arthur interroge l'oracle, il choisit un élément n∈ℕ (la question qu'il pose). Dans la première présentation, Nimué choisit un élément G ∈ g(n) (en essayant d'aider Arthur, mais qu'Arthur ne voit pas) puis Merlin choisit un v∈G (en essayant d'embêter Arthur, et qui est la seule chose qu'Arthur voit), c'est la réponse de l'oracle. Dans la seconde présentation, Nimué choisit un élément λ∈Λ tel que ǧ(n,λ) soit défini (en essayant d'aider Arthur, mais qu'Arthur ne voit pas) puis Merlin choisit un v ∈ ǧ(n,λ) (en essayant d'embêter Arthur, et qui est la seule chose qu'Arthur voit), c'est la réponse de l'oracle. Il n'est pas difficile de voir que ces deux présentations reviennent au même.

Dans tous les cas, ce qui nous intéresse est de savoir si Arthur possède une stratégie calculable, en fonction des réponses faites par l'oracle, pour aboutir à certains résultats : c'est-à-dire en supposant que Nimué fasse le meilleur choix possible à chaque fois, et quels que soient ceux faits par Merlin. De façon mathématiquement plus précise, une fonction f : ℕ → 𝒫(𝒫(ℕ)) de niveau T3 est (Arthur-Nimué-Merlin-)réductible à g : ℕ → 𝒫(𝒫(ℕ)) lorsqu'il existe une stratégie calculable d'Arthur et une stratégie de Nimué telles que, quels que soient m∈ℕ (connu d'Arthur) et F∈f(m) (qu'Arthur ne voit pas), si Arthur et Nimué jouent en fonction de leurs stratégies respectives, Arthur finit (à coup sûr et en temps fini !) par déclarer une valeur dans F quels que soient les coups joués par Merlin. (La stratégie d'Arthur reçoit en entrée la valeur m et les réponses précédentes de Merlin, et doit choisir entre interroger l'oracle sur une nouvelle valeur n, ou bien annoncer la fin du calcul avec une valeur u, auquel cas il gagne lorsque u∈F.) Si on trouve ce que j'ai dit trop vague, je renvoie aux ¶2.1–¶2.6 de notre papier (ou à l'un ou l'autre texte de Kihara).

La réduction d'Arthur-Nimué-Merlin possède les propriétés de base de la réduction de Turing (c'est un « préordre »), donc on a une notion de degré associée. Ou plus exactement, on a trois niveaux de degrés, trois ensembles inclus les uns dans les autres : les degrés que j'appelle T0, qui sont exactement les degrés de Turing, les degrés T1 correspondant aux oracles donnés par des fonctions partielles (ni Nimué ni Merlin n'ont de choix à faire à proprement parler), les degrés T2 correspondant aux oracles non-déterministes (Merlin joue vraiment, mais Nimué n'a toujours pas de choix à faire), et les degrés T3 les plus généraux.

Notre résultat dans le papier est qu'en plus du plongement « évident » des degrés de Turing dans les degrés T3, il existe aussi un plongement « à l'envers », c'est-à-dire qu'à chaque degré de Turing d on peut associer un degré de co-Turing coT(d) parmi les degrés T3, qui est d'autant plus petit (= moins puissant) que d est grand : (b≤a) ⇔ (coT(a)≤coT(b)) (la partie difficile dans l'histoire étant l'implication de la droite vers la gauche). De façon informelle, coT(d) est défini par un oracle qui répond à n'importe quelle question d'Arthur (c'est-à-dire, laisse Nimué communiquer avec Arthur) mais en « chiffrant » les réponses par le degré de Turing d : Nimué fournit une réponse, et Merlin la remplace par un programme qui, en utilisant d comme oracle, calcule la réponse en question, et Arthur ne voit que ça (donc s'il n'a pas accès à d, il ne peut pas faire grand-chose). C'est essentiellement ce que j'avais raconté dans ce billet, mais je note que les degrés de co-Turing « naïfs » définis dans le billet que je viens de lier sont différents[#5] (et moins bien compris) de ceux définis dans l'article. En quelque sorte, nous avons levé des difficultés en modifiant la définition (cf. la note qui suit). Mais la partie difficile restait de résoudre l'énigme difficile posée en tête du billet : c'est bien parce qu'il a fait ça[#6] (c'est le théorème 4.17 du texte) que mon co-auteur nous a permis de débloquer toute la suite.

[#5] La différence est la suivante : si D⊆ℕ, le degré de co-Turing naïf (celui de mon billet passé) va prendre la réponse booléenne (oui/non) fournie par Nimué et la transformer (au choix de Merlin) en un élément de D pour oui et un élément de ℕ∖D pour non ; tandis que le degré de co-Turing que nous avons finalement défini dans notre article renvoie une machine de Turing avec oracle qui, quand on lui fournit D comme oracle, va terminer et renvoyer 1 pour oui et 0 pour non. Cela laisse donc énormément plus de latitude à Merlin pour « chiffrer » sa réponse par rapport à la version naïve (il peut exiger la connaissance de quantité de choses sur D alors que dans la version naïve il ne peut tester la connaissance d'Arthur que sur une seule valeur, et dans un seul sens). Les degrés de co-Turing naïfs se comportent sans doute beaucoup moins bien, mais ça ne veut pas dire qu'ils sont inintéressants à étudier. (Pour l'instant, cependant, je n'en sais pas grand-chose.)

[#6] Normalement je préfère en dire le moins possible sur les contributions des auteurs à un papier : ce serait une atteinte au principe de collégialité qui fait que les matheux ou informaticiens théoriciens listent leur nom par ordre alphabétique, contrairement à la pratique d'autres disciplines ; et en pratique, accepter de s'expliquer sur qui a fait quoi donnerait des armes aux maniaques de l'évaluation (et donc, dégraderait encore plus l'utilité des publications pour communiquer, et l'ambiance des collaborations, sous l'effet de la loi de Campbell/Goodhart). Mais là, à cause de l'échange sur MathOverflow, on voit bien qui a posé la question et qui y a répondu, donc tant pis.

❦

Maintenant, comme je l'écrivais plus haut, ce qui m'intéresse n'est pas tant de faire la pub pour notre résultat que pour les degrés d'Arthur-Nimué-Merlin, qui ne sont pas notre invention (même si nous avons un tout petit peu changé la présentation par rapport à celle de Kihara, et surtout, la terminologie).

C'est toujours une question épineuse en mathématiques de convaincre les autres qu'une certaine définition est « la bonne » (parfois on a une opinion très forte à ce sujet, parfois moins), ou au moins digne d'être étudiée.

Comme je l'ai dit, les degrés de Turing ont été énormément étudiés. D'autres généralisations de ceux-ci (degrés de Medvedev, degrés de Weihrauch) l'ont aussi beaucoup été. Les degrés d'Arthur-Nimué-Merlin introduits par Kihara sont tout nouveaux, donc c'est peut-être un peu tôt pour juger, mais il me semble qu'un obstacle à leur popularité est que leur présentation peut poser problème, et le simple fait que Kihara les appelle topologies de Lawvere-Tierney sur le topos effectif fait peur aux gens qui ne savent ni ce qu'est un topos, ni ce qu'est le topos effectif, ni à plus forte raison une topologie de Lawvere-Tierney sur le topos effectif (et c'est dommage parce qu'il décrit justement le concept sans avoir besoin de tout ça).

À mes yeux, ce qui rend ces degrés d'Arthur-Nimué-Merlin intéressants est une combinaison de diverses choses :

Ils sont une généralisation des degrés de Turing, et qui reste tout de même pas mal dans l'esprit des degrés de Turing (que peut-on faire avec un oracle qui répond d'une certaine manière à certaines questions ?). De plus, les degrés de Turing s'inscrivent naturellement comme échelon (T0) d'une série de généralisations successives (T1, puis T2 puis T3).
Ils ont des propriétés algébriques plus satisfaisantes que les degrés de Turing (les degrés T1 sont un treillis, les degrés T2 et T3 sont un treillis distributif et même une algèbre de Heyting, et les opérations sont d'ailleurs compatibles entre le niveau T2 et le T3).
L'introduction du non-déterminisme adversarial (niveau T2) correspond à quelque chose qu'on fait très souvent en informatique, ce n'est pas tiré d'un chapeau. L'introduction du non-déterminisme coopératif (niveau T3) est peut-être un peu plus difficile à justifier, mais elle relève d'une sorte de dualité assez naturelle comme entre ‘∀’ et ‘∃’.
La présentation sous forme de jeu est élégante (bon, ceci est un jugement très subjectif, mais en tout cas c'est un fait que beaucoup de concepts mathématiques reconnus comme importants sont définis en termes de jeux).
Les degrés d'Arthur-Nimué-Merlin permettent de retrouver simplement des notions déjà étudiées sur les degrés de Turing.

Notamment, la notion de degré de Turing PA, qui a été beaucoup étudiée, se comprend naturellement dans le cadre des degrés d'Arthur-Nimué-Merlin : ce sont exactement les degrés T0 qui sont ≥s où s est (le degré de niveau T2 défini par) l'oracle qui répond 1 quand on lui présente un théorème, 0 quand on lui présente la négation d'un théorème, et peut répondre 0 ou 1 quand on lui présente quelque chose d'indécidable (dans l'arithmétique de Peano, disons). Ce degré s vérifie 0 < s < 0′ où 0′ est le degré du problème de l'arrêt, ce qui est intéressant parce que dans les degrés de Turing il n'y a pas de degré « naturel » connu comme ça (il y en a, mais tous ceux qui sont connus sont construits de façon artificiels) ; et s a, de plus, un rapport fort avec le principe LLPO en maths constructives (au sujet duquel je renvoie à ce billet). Bref, on a plein de raisons de trouver ce s intéressant, et les degrés d'Arthur-Nimué-Merlin sont un cadre où on peut l'étudier.

Autre exemple : il y a un degré T3, appelons-le Cofinite, facile à définir (quand Arthur interroge l'oracle Nimué choisit un entier naturel quelconque, Merlin peut l'augmenter comme il veut, et fournit cette valeur à Arthur) qui a la propriété que les degrés de Turing ≤Cofinite sont exactement les degrés dits hyperarithmétiques, là aussi quelque chose qui a été beaucoup étudié dans les degrés de Turing et qui peut se définir de plein de façons (j'avais écrit un billet à ce sujet) se retrouve de façon naturelle dans les degrés d'Arthur-Nimué-Merlin.
Les degrés d'Arthur-Nimué-Merlin correspondent exactement à une notion extrêmement importante (les topologies de Lawvere-Tierney ou opérateurs locaux) dans la théorie des topos en général. (Et pas que dans la théorie des topos, d'ailleurs : c'est un cas particulier de la notion de monade en théorie des catégories ou théorie des types ; c'est aussi un cas particulier de la notion de nucleus en topologie sans points. C'est une notion qui a été tellement redécouverte qu'elle a plein de noms différents, ce qui explique d'ailleurs une certaine confusion, mais le fait qu'on retombe tout le temps sur la même chose par plein de chemins différents est un argument à mes yeux puissant pour justifier que cette chose est importante.)

Plus exactement, les degrés d'Arthur-Nimué-Merlin décrivent exactement les topologies de Lawvere-Tierney sur le topos effectif, qui est lui aussi un objet largement reconnu comme très important comme point de vue sur la calculabilité (et je lui avais consacré un billet — même si a posteriori je trouve ce texte assez mal foutu).

En fait, on peut dire que le topos effectif correspond au « monde des mathématiques calculables » en un certain sens (ou de façon peut-être moins vague : au monde des objets mathématiques munis d'une notion de représentation calculable), le topos des ensembles correspond au « monde des mathématiques classiques », et les degrés d'Arthur-Nimué-Merlin décrivent précisément tous les degrés intermédiaires entre les deux (un degré de Turing d donne naissance au « monde des mathématiques calculables par d », mais, justement, ce ne sont pas les seuls possibles : il faut généraliser la notion de degré de Turing aux degrés d'Arthur-Nimué-Merlin pour obtenir toutes les notions de calculabilité possibles en ce sens).

Pour moi ce sont des arguments très convaincants, mais il faut reconnaître que si on ne sait pas et qu'on ne veut pas savoir ce qu'est un « topos » (ce que je peux comprendre : moi je ne sais pas ce qu'est un « ∞-topos », et je ne suis pas sûr de vouloir savoir, par exemple, donc je ne suis pas en position de jeter la pierre), le dernier argument disparaît, et les autres ne sont pas forcément si persuasifs. J'en ai discuté très longuement avec des calculabilistes(? — enfin, des spécialistes de calculabilité) la semaine dernière, et si certains semblent avoir été effectivement intéressés par la notion, voici quelques uns des contre-arguments qu'on m'a donnés :

Ce ne sont pas les généralisations des degrés de Turing qui manquent, y compris celles qui ont de bonnes propriétés algébriques. Les degrés de Medvedev, notamment, en sont une très classique. Notamment, un degré « naturel » qui vérifie 0<s<0′, on a déjà ça dans les degrés de Medvedev.

(Ceci appelle évidemment à mieux comprendre le rapport entre degrés de Medvedev et degrés d'Arthur-Nimué-Merlin. Pour les experts, j'ajoute : il est certain à mes yeux que le rapport ne peut se comprendre correctement qu'en introduisant le topos de Kleene-Vesley, parce que les degrés de Medvedev sont essentiellement les valeurs de vérité du topos de Kleene-Vesley, donc les deux se plongent naturellement dans les topologies de Lawvere-Tierney sur le topos de Kleene-Vesley — cf. le mème à la fin de ce billet —, qui peuvent elles aussi se décrire par un jeu à la Arthur-Nimué-Merlin, sauf que maintenant les joueurs jouent des fonctions ℕ→ℕ au lieu de jouer juste des entiers.)
La présentation sous forme de jeu est très ad hoc : pourquoi précisément ces règles et pas d'autres ? Qu'est-ce qui dit qu'on ne pourrait pas, par exemple, introduire un quatrième joueur dans l'histoire, et/ou des fonctions ℕ → 𝒫(𝒫(𝒫(ℕ))) ou quelque chose de ce genre, pour avoir des degrés encore plus généraux ?

(Il faudrait effectivement étudier ce qui se passe quand on modifie un peu la définition dans diverses directions. Mais si on regarde, par exemple, des fonctions ℕ → 𝒫(𝒫(𝒫(ℕ))), si le joueur qui choisit dans le premier 𝒫 est allié de Nimué et Arthur alors ça ne change rien parce que Nimué pourrait faire ce choix, tandis que s'il est allié de Merlin, on peut aussi écraser cette possibilité car après tout n'importe quel jeu de longueur finie entre deux joueurs revient à un jeu à un seul tour où chacun choisit directement une stratégie.)
L'opération de Heyting sur les degrés d'Arthur-Nimué-Merlin va dans le mauvais sens (en tout cas par rapport à celle sur les degrés de Medvedev).

C'est un point un peu philosophique, délicat mais important. L'interprétation dite de Brouwer-Heyting-Kolmogorov de la logique intuitionniste suggère l'idée vague suivante : pour tout « problèmes » P et Q, il devrait y avoir un « problème » P⇒Q qui consiste à convertir une solution de P en une solution de Q ; c'est-à-dire un problème qui est le S le plus facile possible tel que quand on sait résoudre à la fois P et S alors on sait résoudre Q. C'est la situation sur les degrés de Medvedev (où il faut comprendre que plus un ensemble de fonctions est petit, plus le degré de Medvedev qu'il définit est difficile). Mais dans les degrés d'Arthur-Nimué-Merlin (comme l'ordre est, en quelque sorte, inversé : plus un degré est petit plus il est faible, c'est-à-dire « facile »), on a exactement le dual : pour deux degrés P et Q, il y en a un P⇒Q qui est le S le plus puissant tel que Q permette de calculer l'inf entre P et S.

Pour être bien clair, ceci n'est pas un problème mathématique (il n'y a pas d'incohérence), c'est juste que c'est assez contre-intuitif et on peut voir ça comme un signe que la définition n'est pas du tout la bonne.

(L'explication technique, c'est que quand on plonge le cadre Ω des valeur de vérité d'un topos dans le cadre N(Ω) des nuclei sur Ω, c'est-à-dire des topologies de Lawvere-Tierney, eh bien le plongement le plus naturel ce n'est pas u ↦ (x ↦ u∨x), qui préserve l'ordre, mais plutôt v ↦ (x ↦ v⇒x), qui l'inverse. Et du coup l'opération de Heyting sur N(Ω) apparaît plutôt comme une opération de Heyting duale. Tout ça a certainement une pertinence pour nos degrés de co-Turing qui, justement, semblent être une sorte d'opération de négation duale de l'opération de Heyting sur les degrés d'Arthur-Nimué-Merlin. Mais clairement il me manque le bon point de vue.)

Il est évidemment difficile de savoir quand une définition est « la bonne » ou même ce que ça veut dire, et comme d'habitude je ne sais pas comment finir ce billet, alors je vais finir par un mème idiot et incroyablement niche (et qui n'est même pas vraiment nouveau). Faites-en ce que vous voulez.