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