An order-reversing embedding of Turing degrees into Arthur-Nimue-Merlin degrees

1. Contexte et Problématique

L'article s'inscrit dans le domaine de la théorie de la calculabilité et de la théorie des topos, en particulier l'étude du topos effectif (défini par Hyland). Ce topos modélise les mathématiques constructives et calculables. Un objet d'étude central est l'ensemble des topologies de Lawvere-Tierney sur ce topos, qui correspondent aux sous-topos et peuvent être vues comme des degrés de calculabilité généralisés.

Kihara (2023) a introduit une description de ces topologies via un jeu à trois joueurs : Arthur (l'ordinateur, stratégie calculable), Nimue (un agent bienveillant, non-déterminisme angélique) et Merlin (un agent malveillant, non-déterminisme démoniaque). Cela définit les degrés Arthur-Nimue-Merlin (ou degrés $T_3$), qui généralisent les degrés de Turing classiques ($T_0$).

Le problème abordé par les auteurs est de comprendre la structure d'ordre de ces degrés généralisés par rapport aux degrés de Turing classiques. Plus précisément, ils cherchent à déterminer comment les degrés de Turing s'insèrent dans cette hiérarchie élargie et s'il existe des relations d'ordre inverses ou des embeddings naturels.

2. Méthodologie

Les auteurs utilisent une approche combinant la théorie des jeux, la calculabilité relative et la théorie des topos :

• Jeux de réduction : Ils formalisent la notion de réduction entre oracles généralisés ($T_0$ à $T_3$) via un jeu où Arthur et Nimue tentent de gagner contre Merlin. Un oracle $f$ est réductible à $g$ ($f \preceq g$) s'il existe une stratégie gagnante pour Arthur et Nimue.
• Construction de degrés « co-Turing » : Ils définissent une nouvelle classe de degrés, les degrés co-Turing ($\text{coT}(d)$), associés à chaque degré de Turing $d$. Cette construction repose sur des problèmes de promesse (promise problems) spécifiques liés aux ensembles $H^A_0$ et $H^A_1$ (ensembles d'indices de programmes oracle qui terminent avec une sortie 0 ou 1).
• Analyse des opérations de treillis : L'étude des opérations de supremum ($\vee$) et d'infimum ($\wedge$) dans les degrés $T_1$, $T_2$ et $T_3$ est cruciale. En particulier, ils exploitent la propriété selon laquelle il n'existe pas de « paires minimales » (minimal pairs) de degrés de Turing non nuls dans le cadre des degrés $T_1$.
• Interprétation topos-théorique : La section 7 reformule les constructions en termes de topologies de Lawvere-Tierney et de faisceaux (sheaves) dans le topos effectif, reliant les résultats de calculabilité à la logique interne du topos.

3. Contributions et Résultats Clés

A. Définition des degrés co-Turing

Pour un ensemble $A \subseteq \mathbb{N}$, les auteurs définissent un oracle de codage $\tilde{c}_A$ (degré $T_3$) basé sur le problème de promesse $(H^A_0, H^A_1)$. L'oracle $\tilde{c}_A$ permet de répondre à une question binaire arbitraire, mais la réponse est encodée de manière adversaire dans un programme qui, exécuté avec l'oracle $A$, produit le résultat.

B. Embedding inversant l'ordre (Théorème 5.8)

Le résultat principal est que l'application $d \mapsto \text{coT}(d)$ (où $\text{coT}(d)$ est le degré de Turing de $\tilde{c}_A$ pour $A$ représentant $d$) est un embedding inversant l'ordre des degrés de Turing dans les degrés Arthur-Nimue-Merlin.

• Formellement : Pour tous degrés de Turing $d_0, d_1$, on a :
  $$d_0 \leq d_1 \iff \text{coT}(d_0) \geq \text{coT}(d_1)$$
• Cela signifie que plus un degré de Turing est « puissant », plus son image co-Turing est « faible » dans la hiérarchie $T_3$.

C. Incomparabilité avec les degrés de Turing (Théorème 6.4)

Les auteurs démontrent qu'un degré co-Turing non trivial (issu d'un $d > 0$) est incomparable avec tout degré de Turing non trivial.

• Si $\text{coT}(a) \geq b$ pour un degré de Turing $b > 0$, alors nécessairement $a = 0$.
• De même, $\text{coT}(a) \leq b$ est impossible si $a > 0$.
• Signification : Les degrés co-Turing ne permettent pas à Arthur de calculer de nouvelles fonctions déterministes (de type $N \to N$) qui ne seraient pas déjà calculables, sauf si l'oracle de départ est trivial. Ils occupent une « zone » de la hiérarchie qui échappe à la comparaison directe avec les degrés de Turing standards.

D. Résultats techniques intermédiaires

• Absence de paires minimales en $T_1$ : Ils redémontrent et généralisent le fait que si $f \in T_1$ et $g \in T_0$ sont tels que $f \wedge_{T_1} g = 0$, alors $f=0$ ou $g=0$.
• Caractérisation des degrés omniscients : Ils établissent que le degré de codage $c_{P,Q}$ est « omniscient » (égal à $\omega$, le degré maximal sous $\top$) si et seulement si le problème de promesse $(P \times Q, Q \times P)$ est décidable.

4. Signification et Implications

1. Structure des degrés généralisés : Ce travail révèle une structure riche et contre-intuitive dans les degrés $T_3$. L'existence d'un embedding inversant l'ordre montre que la hiérarchie des degrés de Turing est « repliée » à l'intérieur des degrés $T_3$ d'une manière qui préserve l'information mais inverse la puissance relative.
2. Lien avec la logique constructive : La reformulation topos-théorique (Section 7) montre que les degrés co-Turing correspondent à des opérations de « complétion » ou de « faisceautisation » spécifiques sur l'objet booléen $\mathbf{2}$ dans le topos effectif. Le degré $\text{coT}(d)$ correspond à la plus petite topologie rendant dense l'inclusion du faisceau associé à $d$ dans le faisceau classique.
3. Limites de la puissance computationnelle : Le résultat d'incomparabilité (Théorème 6.4) est surprenant : malgré la complexité introduite par le non-déterminisme angélique et démoniaque, les degrés co-Turing ne « surmontent » pas les degrés de Turing classiques pour le calcul de fonctions déterministes. Ils représentent une forme de puissance computationnelle qui est « orthogonale » à la hiérarchie de Turing standard.
4. Réponse à une question ouverte : Cette construction répond partiellement à une question de Kihara (2023) concernant l'existence d'autres degrés $T_3$ « intéressants » au-delà des degrés de base, en fournissant une famille infinie de degrés distincts et structurés.

En résumé, cet article établit un pont profond entre la calculabilité classique, les jeux à information imparfaite et la théorie des topos, en démontrant que les degrés de Turing peuvent être plongés de manière inversée dans un univers de calculabilité non-déterministe, tout en restant structurellement distincts de celui-ci.