David Madore's WebLog: Une devinette et des méditations sur les

Devinette mathématique (pas très difficile !) : Vous avez accès à un oracle omniscient auquel vous pouvez poser (de façon illimitée) des questions à réponse oui/non. Mais évidemment il y a une arnaque : au lieu de répondre oui ou non, l'oracle code sa réponse. Plus exactement, pour chaque question, il va vous donner la réponse sous forme d'une machine de Turing. Pour dire oui, il va vous présenter une machine de Turing qui s'arrête ; et pour non, il va vous présenter une machine de Turing qui ne s'arrête pas. Vous êtes limité par la thèse de Church-Turing, donc n'avez pas de moyen pour savoir en général si une machine de Turing s'arrête ou pas. (L'oracle, lui, peut évidemment répondre à cette question, puisqu'il est omniscient ; mais comme il vous donnera la réponse de façon codée, vous n'êtes pas plus avancé.) L'oracle cherche à vous embêter : il veut vous empêcher de récupérer des informations utiles de ses réponses. Problème : pouvez-vous forcer l'oracle à vous révéler des choses utiles, ou peut-il s'arranger pour rendre ses réponses complètement inutiles ?

(Si vous trouvez que c'est mathématiquement trop vague parce que je parle d'oracle omniscient sans définir ce terme, je vais présenter des versions beaucoup plus précises plus bas. Mais celle-ci me semble quand même raisonnablement claire et assez parlante pour attirer la curiosité et expliquer de quoi il est question.)

Cette devinette n'est pas trop difficile, et j'encourage à y réfléchir, ne serait-ce que pour comprendre pourquoi la suite m'intéresse. En tout cas, il ne suffit pas de dire il n'y a pas moyen calculable de résoudre le problème de l'arrêt (ce qui est, certes, vrai) pour avoir répondu au problème. Voici la réponse (cliquez ici pour la faire apparaître) :

Réponse (à la devinette facile) :

Maintenant, modifions la devinette pour la rendre plus difficile en empêchant la stratégie utilisée dans la réponse ci-dessus :

Devinette mathématique (beaucoup plus difficile !) : Comme précédemment, vous avez accès à un oracle omniscient auquel vous pouvez poser (de façon illimitée) des questions à réponse oui/non. Et comme précédemment, au lieu de répondre oui ou non, l'oracle code sa réponse. Mais cette fois, pour chaque question, il va vous donner la réponse sous forme de deux machines de Turing. Pour dire oui, il va vous donner deux machines de Turing dont l'une s'arrête et l'autre pas ; et pour non, il va vous donner deux machines de Turing qui soit s'arrêtent toutes les deux soit aucune ne s'arrête. Tout le reste est comme dans a devinette précédente : vous êtes limité par la thèse de Church-Turing, et l'oracle cherche à vous embêter. Problème : pouvez-vous forcer l'oracle à vous révéler des choses utiles, ou peut-il s'arranger pour rendre ses réponses complètement inutiles ?

Je n'ai pas la solution à cette devinette, et elle m'obsède un peu (je tourne autour de plein de variations autour d'elle, mais je n'ai vraiment aucune idée de comment l'attaquer). Donc j'essaie de la balancer dans la nature (i.e., sur le Web) dans l'espoir que quelqu'un ait une idée intelligente. (Comme je vais le dire plus bas, c'est une variation sur cette énigme que j'ai posée ici et là sur MathOverflow.)

Le but de la suite de ce billet est de tourner autour du pot de cette devinette : comme le font les mathématiciens qui ne savent pas répondre à une question, ils la formalisent, donc je vais expliquer comment on peut imaginer définir une notion en quelque sorte « duale » de la notion (habituelle) des degrés de Turing, les degrés de co-Turing (ou de coTuring ? Coturing ? coturne ?), et que la devinette ci-dessus s'inscrirait dans le cadre de cette notion. Mais je ne sais malheureusement à peu près rien dire à son sujet, donc c'est un peu du formalisme pour formaliser, mais j'espère au moins convaincre que la question est bien définie (elle a un sens mathématique précis) et au moins raisonnablement naturelle.

[Je précise que ce qui précède a été pour l'essentiel écrit avant ce qui suit, ce qui peut expliquer la présentation un peu étrange.]

⁂

Le but de ce billet, donc, est pour moi de réfléchir tout haut à une définition qui m'a traversé l'esprit : ce n'est pas vraiment de faire de la vulgarisation. Si vous ne connaissez pas un peu la théorie de la calculabilité, passez votre chemin (lisez plutôt ceci, ou bien, si vous voulez quelque chose de plus costaud, ça ou ça).

Bref. Je me suis rendu compte qu'il y a une notion en quelque sorte « duale » de la réduction de Turing, qui ne semble pas du tout avoir été étudiée. Je vais essayer de donner la définition de plusieurs manières différentes, de dire quelques propriétés évidentes, et de poser des questions auxquelles je ne sais pas répondre.

☞ Définition informelle de la « réduction de co-Turing »

Je commence par rappeler :

Si A,B⊆ℕ, on dit que A est Turing-réductible à B lorsqu'on peut répondre à la question est-ce que m∈A ? en posant librement des questions est-ce que n∈B ?, par un processus calculable.

Ceci est dit de façon informelle, mais je pense que c'est assez parlant. Mais formulons les choses un peu différemment en introduisant une terminologie un peu idiote : si A⊆ℕ, je vais dire qu'un m∈ℕ est un A-codage de oui lorsque m∈A, et que c'est un A-codage de non lorsque m∉A (autrement dit, un A-codage d'un booléen c est un m tel que c = 1_A(m), en notant 1_A la fonction indicatrice de A). Avec cette terminologie, on peut dire (toujours informellement) :

On dit que A est Turing-réductible à B lorsqu'on peut, par un processus calculable. A-décoder un booléen, à condition d'être librement capable de B-décoder des booléens.

En encore plus court : A est Turing-réductible à B lorsque la capacité de B-décoder les booléens permet (calculablement !) de A-décoder les booléens. I.e., je postule la capacité de B-décoder et j'obtiens la capacité de A-décoder.

De façon symétrique, je propose la définition suivante (dite de façon informelle, et que je vais rendre précise ensuite) :

Si A,B⊆ℕ, on dira que A est co-Turing-réductible à B lorsqu'on peut, par un processus calculable, répondre à n'importe quelle question booléenne de façon B-encodée, à condition d'être librement capable d'obtenir la réponse à n'importe quelle question booléenne de façon A-encodée.

En encore plus court : A est co-Turing-réductible à B lorsque la capacité de A-encoder des booléens cachés permet (calculablement !) de B-encoder des booléens cachés. (Attention ! il s'agit de booléens cachés, cf. ci-dessous pour plus d'explications.) I.e., je postule la capacité de A-encoder et j'obtiens la capacité de B-encoder.

Dit comme ça, j'espère que c'est clair pourquoi la notion que je propose est en quelque sorte duale de la notion de réduction de Turing : d'où le terme de réduction de co-Turing.

Entendons-nous bien : quand je parle d'encoder un booléen, il s'agit de booléens cachés. Encoder un booléen connu c'est toujours évident : une fois qu'on a un m₀∉A et un m₁∈A, il suffit de renvoyer l'un ou l'autre, et ceci est toujours calculable. (On peut objecter oui mais si je ne connais pas de tels m₀ et m₁ ? mais ce n'est pas ce dont je veux parler ici : ma partie étant fixée, et ni vide ni pleine, ces m₀ et m₁ existent et des algorithmes écrits avec eux existent aussi ; d'ailleurs, peut-être que je devrais postuler une fois pour toutes que 0∉A et que 1∈A.)

Mon problème, donc, c'est que quelqu'un (qu'on va appeler Merlin plus bas) a choisi un booléen et ne me l'a pas dit, et moi j'ai le droit de lui poser n'importe quelle question (portant sur son booléen caché ou sur « n'importe quoi ») mais il me répond de façon A-codée ; et mon but c'est de produire un B-codage du booléen choisi.

Note : Je dois signaler que j'ai « inversé » la réduction par rapport à ce qu'on pourrait peut-être imaginer, de manière à ce que les ensembles les plus « difficiles » soient toujours réductibles aux ensembles les plus « faciles », ce qui rend la comparaison avec d'autres réductions tout de même plus naturelle, mais du coup ça peut sembler à l'envers (A est co-Turing-réductible à B lorsque la capacité de A-encoder des booléens cachés permet calculablement de B-encoder des booléens cachés). Évidemment, cette « inversion » va se sentir dans toutes les autres versions de la définition.

☞ Définition avec des jeux à trois joueurs

Pour rendre la définition précise, le mieux est d'introduire des jeux à trois joueurs. J'ai évoqué ce type de jeux dans ce billet passé (qui est une tentative de semi-vulgarisation de cet article), mais je vais redire le nécessaire. Les règles générales (toujours valables) de ce type de jeu sont les suivantes :

Il y a trois joueurs, Arthur, Nimué et Merlin. Arthur et Nimué font équipe contre Merlin. Ils jouent dans l'ordre suivant : Merlin, Arthur, Nimué, Merlin, Arthur, Nimué, etc., jusqu'à ce qu'Arthur mette fin à la partie. Nimué et Merlin voient tous les coups précédemment joués par tous les joueurs ; Arthur ne voit que les coups explicitement déclarés visibles d'Arthur. De plus, Arthur devra jouer selon une stratégie calculable (alors que les deux autres joueurs n'ont pas de telle limitation). Le jeu continue jusqu'à ce qu'Arthur y mette fin en faisant une « annonce » : si cette annonce est correcte (selon les modalités spécifiques du jeu), Arthur et Nimué gagnent ; s'il fait une annonce incorrecte, ou qu'il n'en fait jamais (y compris si sa stratégie censée être calculable ne renvoie pas de coup à jouer, par exemple parce qu'elle ne termine pas), alors Arthur et Nimué ont perdu ; et bien sûr, si un joueur ne respecte pas les contraintes du coup, alors il perd immédiatement.

En gros, il faut imaginer ça comme un jeu de communication : Nimué essaie de passer de l'information à Arthur, mais elle ne peut pas communiquer directement avec Arthur, elle ne peut le faire qu'à travers Merlin, qui essaie de leur mettre des bâtons dans les roues. La question qu'on va se poser, c'est si Arthur et Nimué ont moyen d'avoir une stratégie commune pour gagner contre Merlin.

Dans le jeu de la réduction de Turing de A à B (les parties A,B⊆ℕ sont fixées à l'avance, font partie de la règle du jeu, et sont « connues » des joueurs au sens où leur stratégie est pour A et B précis, aucune uniformité n'est demandée), les règles spécifiques sont les suivantes :

au coup initial, Merlin joue un entier m∈ℕ, visible d'Arthur ;
Arthur a deux types de coups possibles : il peut soit annoncer un résultat en jouant un booléen, soit interroger l'oracle en jouant un entier n ;
si Arthur annonce un résultat, le jeu prend fin, et Arthur+Nimué gagnent lorsque le booléen annoncé par Arthur est la réponse correcte à la question m∈A ? où m est l'entier initialement choisi par Merlin ;
Nimué ne joue jamais dans ce jeu (elle ne fait que passer son tour) ;
lorsque Arthur interroge l'oracle, Merlin joue la réponse à la question n∈B ? où n est l'entier choisi par Arthur, et cette réponse est visible d'Arthur.

Il est vrai que ce jeu à trois joueurs est plutôt un jeu à un joueur, parce que Nimué ne fait rien du tout et que Merlin, à part son choix initial de m, n'a pas non plus de choix ; mais la présentation a l'intérêt de rentrer dans le cadre général.

On peut faire plein de petits changements dans la description. On peut par exemple changer un tout petit peu la description en disant que Merlin choisit d'abord un booléen a caché à Arthur, et joue ensuite de façon visible un A-codage de ce booléen, et que le but d'Arthur est de deviner a : ça ne change évidemment rien, mais ça rendra le jeu plus semblable au suivant.

Dans tous les cas, l'idée du jeu c'est qu'Arthur essaie de savoir si m∈A, et pour ça il a le droit de poser à Merlin des questions de la forme n∈B ? (et Merlin est obligé de répondre correctement). Ou, si on préfère, Arthur essaie de A-décoder un booléen caché, et pour ça il a le droit de demander librement de B-décoder des booléens.

Et la définition est alors : A est Turing-réductible à B exactement lorsque Arthur a une stratégie calculable à ce jeu (c'est-à-dire qu'elle doit prendre les informations visibles d'Arthur et décider quel coup Arthur joue) qui soit gagnante quels que soient les coups faits par Merlin (enfin, je répète, ici il n'y a qu'un seul vrai coup de Merlin, c'est le choix du m initial).

On pourra aussi noter que A est décidable (= calculable) lorsque A est Turing-réductible à {1} (ici ça signifie qu'Arthur ne peut poser que des questions triviales à l'oracle, donc en fait il doit se débrouiller tout seul).

Maintenant, dans le jeu de la réduction de co-Turing de A à B, les règles spécifiques sont les suivantes :

au coup initial, Merlin joue un booléen b caché à Arthur ;
Arthur a deux types de coups possibles : il peut soit annoncer un résultat en jouant un entier n, soit continuer à jouer (il n'a rien de particulier à jouer dans ce cas, juste je continue le jeu) ;
si Arthur annonce un résultat, le jeu prend fin, et Arthur+Nimué gagnent lorsque le booléen b initialement choisi par Merlin coïncide avec la réponse à la question n∈B ? où n est l'entier annoncé par Arthur (autrement dit, Arthur gagne en annonçant un B-codage du booléen caché b initialement choiis par Merlin) ;
lorsque c'est à son tour de jouer, Nimué joue un booléen a qui n'est pas visible d'Arthur ;
après un coup de Nimué, Merlin joue un entier m tel que la réponse à la question m∈A ? soit le booléen a qui vient d'être joué par Nimué (autrement dit, Merlin joue un A-codage de a), et cet entier m est visible d'Arthur.

L'idée du jeu c'est donc qu'Arthur essaie de B-encoder un booléen b caché choisi par Merlin, et pour ça il a le droit de demander librement de A-encoder des booléens (choisis par Nimué, son alliée, qui, elle, a vu b, et qui n'a pas de limitation de calculabilité).

Et la définition est alors : A est co-Turing-réductible à B exactement lorsque Arthur a une stratégie calculable à ce jeu (c'est-à-dire qu'elle doit prendre les informations visibles d'Arthur et décider quel coup Arthur joue) et que Nimué a une stratégie (pas supposée calculable) qui, mises ensemble, soient gagnantes quels que soient les coups faits par Merlin.

On pourra aussi dire que A est co-décidable (ou co-calculable) lorsque A est co-Turing-réductible à {1} (ici ça signifie qu'Arthur doit annoncer exactement le booléen b choisi par Merlin, il n'a pas le droit de le dire de façon codée).

(J'ai aussi décrit ce jeu dans cette question MathOverflow, à deux petites différences près : ① dans la question MO je considère deux parties P,Q⊆ℕ, alors que dans ce billet je postule que P et Q sont complémentaires l'une de l'autre, et j'appelle A la partie P ; et ② en revanche, ma question MO correspond au cas spécifique où B={1} disons, c'est-à-dire qu'Arthur doit annoncer le booléen caché lui-même plutôt que devoir juste en annoncer un B-codage de celui-ci, ce que je demande ici pour définir une notion de réduction. Pour être bien clair : ma question MO pour P=A et Q=ℕ∖A définit la notion d'ensemble co-décidable comme au paragraphe ci-dessus.)

Je mentionne aussi que ce jeu a une saveur analogue au jeu qui sert en cryptographie à définir la sécurité sémantique IND-CPA. Je me demande si on peut utiliser des idées de la cryptologie pour l'étudier. Ce qui est sûr, c'est que je n'arrive à rien.

☞ Définition avec des convertisseurs

Si vous n'aimez pas la description en termes de jeux, en voici une sur le modèle de ce billet. Je pense qu'elle est un peu opaque, mais elle a l'avantage de ne pas nécessiter de discussion lourdingue sur les règles du jeu, la notion de stratégie, etc.

D'abord je rappelle ce que j'avais écrit pour la réduction de Turing (en changeant minimalement la notation et la terminologie pour plus de cohérence avec le reste de ce billet-ci) :

✱ Définition : Si A,U⊆ℕ, un U-questionneur pour le A-décodage est un couple ⟨m,e⟩ où m∈ℕ et, si a=1_A(m) est la valeur de la fonction indicatrice de A en m, alors le programme e appelé sur l'entrée a, termine et renvoie un élément de U.

✱ Définition : Si A,U⊆ℕ, un U-répondeur pour le A-décodage est un programme qui, quand on lui passe un U-questionneur pour le A-décodage, termine et renvoie un élément de U.

✱ Définition : Si A,B,U⊆ℕ, un U-convertisseur du B-décodage vers le A-décodage est un programme qui, quand on lui passe un U-répondeur pour le B-décodage, termine et renvoie un U-répondeur pour le A-décodage. Et un convertisseur universel du B-décodage vers le A-décodage est un même programme h qui est un U-convertisseur du B-décodage vers le A-décodage pour n'importe quel U⊆ℕ.

✱ Définition ou théorème : Pour A,B⊆ℕ, un convertisseur universel du B-décodage vers le A-décodage existe si et seulement si A est Turing-réductible à B.

(J'écris définition ou théorème parce qu'on pourrait sans doute prendre ça comme définition de la réduction de Turing, mais sinon c'est un théorème que ça équivaut à la définition usuelle. La démonstration du théorème est dans le billet en question.)

L'intuition, comme je l'ai expliqué dans le billet déjà lié ci-dessus, c'est que le questionneur encode une question est-ce que m∈A ? et, en même temps, il fournit un programme e (une « continuation ») auquel on est chargé de fournir la réponse (a). Encore plus informellement, U est un ensemble de bonbons, le questionneur vous demande est-ce que m∈A ? et, si vous répondez correctement, il vous donne un bonbon en échange (à savoir φ_e(a)). Le répondeur, lui, accepte une question est-ce que m∈A ? et il est « plus ou moins censé » lui fournir la réponse : on « espère vaguement » qu'il va appeler e avec la vraie valeur a=1_A(m) pour produire un élément de U et renvoyer cet élément. (Mais ce n'est pas demandé : la définition demande juste qu'il renvoie un élément de U quand on lui passe un U-questionneur.) Encore plus informellement, le répondeur vous donne un bonbon si vous lui passez un machin qui donne un bonbon si on répond à une certaine question.

Dans le même esprit, voici comment on définirait la réduction de co-Turing (pour vous éviter de jouer au jeu des 7 différences, le principal changement est dans la définition du questionneur ; la définition du répondeur est essentiellement juste du copier-coller, et pour celle du convertisseur il y a un échange entre A en B qui est plus une question de commodité sur le sens de mes réductions, je l'ai déjà dit plus haut) :

✱ Définition : Si A,U⊆ℕ, un U-questionneur pour le A-encodage est un programme e tel qu'il existe a∈{0,1} tel que quel que soit m∈ℕ vérifiant 1_A(m)=a, le programme e appelé sur l'entrée m termine et renvoie un élément de U.

(Ou, dit de façon plus simple : soit e est défini sur tous les éléments de A et les envoie dans U, soit il est défini sur tous les éléments du complémentaire de A et les envoie dans U.)

✱ Définition : Si A,U⊆ℕ, un U-répondeur pour le A-encodage est un programme qui, quand on lui passe un U-questionneur pour le A-encodage, termine et renvoie un élément de U.

✱ Définition : Si A,B,U⊆ℕ, un U-convertisseur du A-encodage vers le B-encodage est un programme qui, quand on lui passe un U-répondeur pour le A-encodage, termine et renvoie un U-répondeur pour le B-encodage. Et un convertisseur universel du A-encodage vers le B-encodage est un même programme h qui est un U-convertisseur du A-encodage vers le B-encodage pour n'importe quel U⊆ℕ.

✱ Définition ou théorème : Pour A,B⊆ℕ, un convertisseur universel du A-encodage vers le B-encodage existe si et seulement si A est co-Turing-réductible à B.

L'intuition, c'est que le questionneur pose une question à Nimué (il n'a même pas besoin de formuler la question, parce qu'Arthur et Nimué ont mis leur stratégie d'accord pour commencer, donc tout ce qu'Arthur a à demander à Nimué est aide-moi !), et il fournit un programme e (une « continuation ») auquel on est chargé de fournir la réponse de Nimué A-encodée par Merlin (le m). Encore plus informellement, U est un ensemble de bonbons, le questionneur demande est-ce que la réponse à la question que j'ai en tête est oui ou non ? et, si vous répondez correctement, et que vous A-encodez la réponse n'importe comment, il vous donne un bonbon en échange (à savoir φ_e(m)). Le répondeur fonctionne comme précédemment.

☞ Définition dans le topos effectif

Pour ceux qui connaissent le topos effectif, on peut expliquer les choses de façon « sophistiquée » comme ceci. (Les gens qui ne connaissent pas le topos effectif sont invités à sauter jusqu'au point suivant.)

D'abord, rappelons que chaque partie A⊆ℕ définit un sous-objet de l'objet N des entiers naturels du topos effectif, que je suis tenté de noter encore A (une façon de le définir est que, si je ne me suis pas planté, il s'agit de l'intersection de N et de ∇A dans ∇ℕ, enfin, le tiré en arrière de ∇A ↪ ∇ℕ par N ↪ ∇ℕ, quoi) ; la fonction indicatrice N→Ω de ce sous-objet A ↪ N se factorise par le sous-objet ∇2→Ω (en voyant ∇2 comme {u:Ω | (¬¬u)⇒u}). L'image du N → ∇2 ainsi défini est un sous-objet X_A de ∇2 : si on veut, on peut l'écrire X_A = {a:∇2 | ∃m:N. (a⇔(m∈A))}. En supposant pour simplifier que A n'est ni vide ni plein (ou, de façon constructivement plus correcte, qu'on a un m₀∉A et un m₁∈A), on a ainsi défini 2 ↪ X_A ↪ ∇2.

(Si on préfère une description plus explicite, les objets 2, X_A et ∇2 sont trois assemblées sur l'ensemble {0,1} : je rappelle qu'une assemblée sur un ensemble S est la donnée d'une fonction E:S→𝒫(ℕ), et qu'un morphisme d'assemblées (S,E) → (S′,E′) est une application ensembliste f:S→S′ telle qu'il existe une fonction calculable envoyant n'importe quel élément de E(s) sur un élément de E′(f(s)) — la fonction calculable en question ne faisant pas partie de la donnée du morphisme, on demande juste son existence. L'assemblée 2 est définie par exemple par E(0)={0} et E(1)={1}, l'assemblée ∇2 est définie par exemple par E(0)=ℕ et E(1)=ℕ, et l'assemblée X_A, entre les deux, est définie par E(0) = ℕ∖A et E(1) = A. Les deux morphismes 2 → X_A → ∇2 sont simplement donnés par l'identité sur l'ensemble {0,1} sous-jacent.)

Ensuite, rappelons (cf. ici) que dès qu'on a un sous-objet E ↪ X dans un topos, on a une plus petite topologie[#] de Lawvere-Tierney j:Ω→Ω telle que E soit j-dense (c'est-à-dire : ∀x:X. j(x∈E)). Très précisément, il s'agit de la fonction u ↦ ∀v:Ω. ((((∃x:X. (x∈E ⇒ v)) ⇒ v) ∧ (u ⇒ v)) ⇒ v), mais je doute que ce soit franchement plus parlant sous cette forme.

[#] Une topologie de Lawvere-Tierney (ou opérateur local ou nuclei, ou plein d'autres noms possibles) est une fonction j:Ω→Ω sur l'ensemble Ω des valeurs de vérité en maths constructives qui vérifie les propriétés : ⓐ j(u∧v) = j(u) ∧ j(v), ⓑ u ≤ j(u), et ⓒ j(j(u)) ≤ j(u) (tout ça pour tous u,v∈Ω) ; noter en particulier qu'une telle fonction est forcément croissante : si u≤v alors j(u) ≤ j(v). Ces fonctions ont beaucoup de propriétés intéressantes et apparaissent de toutes sortes de manières (et notamment cet article explique pourquoi il faut y penser comme des sortes d'oracles généralisés). (On considère l'ensemble N(Ω) des topologie de Lawvere-Tierney comme muni de l'ordre point à point, c'est-à-dire que j≤k signifie que j(u) ≤ k(u) pour tout u∈Ω.) ❧ Par ailleurs, je mentionne un résultat folklorique (pour lequel je renvoie à la question MathOverflow que je viens de lier) qui est que si f:Ω→Ω est une fonction croissante quelconque, alors la plus petite topologie de Lawvere-Tierney j telle que f≤j est donnée explicitement par : u ↦ ∀v:Ω. (((f(v) ⇒ v) ∧ (u ⇒ v)) ⇒ v) (on va ensuite vouloir appliquer ça à la fonction f donnée par v ↦ ∃x:X. (x∈E ⇒ v)).

Tout ceci étant dit, A est Turing-réductible à B équivaut à la plus petite topologie de Lawvere-Tierney telle que 2 soit j-dense dans X_A est majorée par la plus petite topologie de Lawvere-Tierney telle que 2 soit j-dense dans X_B ; et A est co-Turing-réductible à B équivaut à la plus petite topologie de Lawvere-Tierney telle que X_B soit j-dense dans ∇2 est majorée par la plus petite topologie de Lawvere-Tierney telle que X_A soit j-dense dans ∇2.

(Et oui, encore une fois, je signale que j'ai fait une petite inversion des choses, ici, pour que les ensembles les plus « difficiles » soient réductibles aux ensembles les plus « faciles ». Mais ça veut dire que mes degrés de co-Turing sont plongés à l'envers dans les topologies de Lawvere-Tierney sur le topos effectif.)

Si je veux vraiment dérouler toutes les définitions (et qu'on ne veut pas entendre parler de topologie de Lawvere-Tierney), A est Turing-réductible à B se traduit par : ∀u:Ω. (((∃n:N. ((n∈B∨¬n∈B) ⇒ u)) ⇒ u) ⇒ ((∃m:N. ((m∈A∨¬m∈A) ⇒ u)) ⇒ u)). Tandis que A est co-Turing-réductible à B se traduit par : ∀u:Ω. (((∃a:∇2. ((∃m:N. (a ⇔ m∈A)) ⇒ u)) ⇒ u) ⇒ ((∃b:∇2. ((∃n:N. (b ⇔ n∈B)) ⇒ u)) ⇒ u)) (et si on veut vraiment aller jusqu'au bout[#2], on peut remplacer ∃c:∇2.(⋯) par ∃c:Ω.(((¬¬c)⇒c)⇒(⋯))). (Pour être bien clair, l'affirmation est que A est Turing-réductible [resp. co-Turing-réductible] à B équivaut à la validité de la formule donnée dans le topos effectif, i.e., à ce qu'elle soit réalisable. Comme un réalisateur de la formule est plus ou moins immédiatement équivalent à ce que j'ai appelé un convertisseur universel plus haut, on retombe sur nos pattes.) Mais je ne pense pas que ce soit franchement plus parlant écrit ainsi.

[#2] L'intérêt éventuel de cette remarque est que la formule fait alors sens dans n'importe quel topos muni d'un objet d'entiers naturels (l'objet ∇2 est un truc spécifique au topos effectif, mais Ω a un sens dans n'importe quel topos).

☞ Réduction de co-Turing et degrés de co-Turing : propriétés évidentes

Le problème maintenant que j'ai défini cette notion de réduction de co-Turing, c'est que je ne sais essentiellement rien dire de non-trivial dessus.

La réduction de co-Turing est un préordre (comme celle de Turing) : si je note A ≤_coT B pour A est co-Turing-réductible à B, alors on a évidemment A ≤_coT A, et par ailleurs A ≤_coT B et B ≤_coT C impliquent A ≤_coT C (sur les jeux, par exemple, ça se voit par un argument assez facile de composition de stratégies). Je peux donc définir l'équivalence de co-Turing : A ≡_coT B lorsqu'on a à la fois A ≤_coT B et B ≤_coT A, et appeler degrés de co-Turing les classes pour cette relation d'équivalence, qui sont partiellement ordonnées par la réduction de co-Turing.

Je dirai qu'un ensemble E⊆ℕ est co-décidable lorsque E ≤_coT {1}. Bon, là il y a une petite merdouille qui est que l'ensemble vide ∅ et l'ensemble plein ℕ sont encore plus bas que {1} pour la réduction de co-Turing (i.e., on a ∅ ≤_coT {1} mais pas le contraire, parce qu'il n'est pas possible de ∅-encoder le booléen 1) : ce n'est pas un problème intéressant, donc il est probablement pertinent soit de convenir qu'on ne s'intéresse à la réduction de co-Turing que pour des parties ni vide ni pleines, voire même de supposer que 0 n'est pas dedans et que 1 est dedans, soit de changer un peu le jeu pour toujours autoriser un booléen à être présenté de façon explicite (non codée). Je vais me permettre de glisser cette petite merdouille sous le tapis : dès lors, on a toujours {1} ≤_coT E (quel que soit E — ni vide ni plein, donc), et ceci permet de dire que les ensembles co-décidables forment le plus petit degré de co-Turing.

Concrètement, dire que E est co-décidable, ça signifie que si je dispose d'un oracle qui répond à n'importe quelle question booléenne en me donnant un entier qui appartient à E ssi la réponse est oui, alors je peux m'en servir pour répondre « en clair » à n'importe quelle question booléenne.

Tout ensemble décidable est co-décidable. En fait, il y a mieux : tout ensemble semi-décidable (= calculablement énumérable) est co-décidable : en effet, si E est semi-décidable, pour obtenir la réponse à n'importe quelle question booléenne, je pose deux fois la question, une fois positivement et une fois négativement, j'obtiens ainsi deux éléments dont exactement un est dans E, et pour savoir lequel c'est je peux énumérer E jusqu'à trouver l'un ou l'autre élément. (C'est là la réponse à la devinette « facile » qui ouvre ce billet.) Comme en outre le complémentaire d'un ensemble co-décidable est co-décidable (parce que la définition est complètement symétrique), on voit que le complémentaire d'un ensemble semi-décidable est aussi co-décidable.

Mais on peut trouver des ensembles co-décidables de degré de Turing arbitraire : en effet, si z est un réel quelconque, alors {r∈ℚ | r<z} (en passant sous silence un codage des rationnels par les entiers) est toujours co-décidable, puisque pour obtenir la réponse à n'importe quelle question booléenne, je pose deux fois la question, une fois positivement et une fois négativement, j'obtiens ainsi deux rationnels dont exactement un est <z et l'autre est ≥z, et je n'ai qu'à les comparer pour connaître la réponse. Comme cet ensemble a le même degré de Turing que z, on voit que co-décidable ne borne pas le degré de Turing.

Le fait qu'il existe des ensembles qui ne sont pas co-décidables n'est pas évident (en tout cas, ça ne l'était pas pour moi) : j'ai écrit une preuve sur MathOverflow (à la fin de cette question) qu'un ensemble suffisamment générique, ou suffisamment aléatoire, n'est pas co-décidable. La quantité de générique ou d'aléatoire nécessaire semble assez importante (je crois que ma preuve utilise en gros arithmétiquement générique/aléatoire, donc c'est plutôt fort), et je me demande si on peut faire mieux.

Du coup, on peut aussi dire que la réduction de Turing n'implique pas la réduction de co-Turing : prendre un ensemble non-co-décidable, et utiliser la construction {r∈ℚ | r<z} ci-dessus pour fabriquer un ensemble qui lui est Turing-équivalent mais qui est co-décidable. Il n'y a bien sûr pas d'implication dans l'autre sens non plus, puisque déjà co-décidable n'implique pas décidable.

Il est quand même vrai que la réduction many-to-one implique la réduction de co-Turing : si A ≤_m B (c'est-à-dire s'il existe une fonction calculable f:ℕ→ℕ telle que m∈A ssi f(m)∈B), alors on a A ≤_coT B (la stratégie d'Arthur et Nimué est évidente : Nimué reproduit le bit choisi par Merlin, Merlin en montre un A-codage à Arthur, et Arthur applique la fonction f pour en obtenir le B-codage souhaité).

☞ Quelques questions

Bon, le problème avec la réduction de co-Turing, c'est que je ne sais essentiellement rien dire dessus. (Si j'avais des choses intelligentes à dire, j'écrirais un texte un peu plus formel qu'un billet de blog.) Déjà j'ai eu beaucoup de mal à prouver qu'il existe un ensemble qui ne soit pas non-co-décidable (donc la notion n'est pas complètement triviale) ; je ne sais a fortiori pas en donner d'exemple explicite. Par exemple, je n'ai pas la réponse aux questions suivantes :

L'ensemble Tot des e tels que la e-ième fonction partielle récursive φ_e soit totale est-il co-décidable ?

(En clair, vous avez un oracle capable de répondre à n'importe quoi, mais qui au lieu de répondre oui ou non, vous donne soit le code d'une fonction calculable totale soit le code d'une fonction calculable qui n'est pas totale : pouvez-vous forcer cet oracle à répondre à une question qui vous intéresse ?)
(Question suggérée par Will Sawin en commentaire sous ma question MO, et qui est probablement plus intéressante.) Même question, de façon encore plus provocatrice, pour l'ensemble (H × (ℕ∖H)) ∪ ((ℕ∖H) × H) des couples ⟨e,e′⟩ où exactement un des deux programmes termine [sur l'entrée 0].

(En clair, cette fois-ci l'oracle dit oui ou non en vous donnant un couple ⟨e,e′⟩ de programmes : pour oui, l'un des deux programmes termine et l'autre pas, et pour non, soit les deux terminent soit aucun des deux ne termine.)

C'est cette dernière question (l'ensemble (H × (ℕ∖H)) ∪ ((ℕ∖H) × H) est-il co-décidable ?) qui fait l'objet de la devinette « difficile » posée en tête de ce billet. Et je répète que je n'ai pas la réponse ! (Et ça m'énerve beaucoup.)

Autre chose : dans les degrés de Turing, l'ensemble A⊕B (aussi noté A⊔B) formé des ⟨0,m⟩ pour m∈A et des ⟨1,n⟩ pour n∈B, i.e., la réunion disjointe étiquetée de A et B, représente la borne supérieure de A et B, c'est-à-dire qu'on a A⊕B ≤_T C si et seulement si A ≤_T C et B ≤_T C.

Qu'en est-il dans les degrés de co-Turing ? En remarquant que (A⊕B)-encoder un booléen c'est, en gros, avoir le choix entre le A-encoder ou le B-encoder, il est facile de voir que, comme pour les degrés de Turing, A⊕B majore A et B, c'est-à-dire A ≤_coT A⊕B et B ≤_coT A⊕B ; mais je ne sais pas si c'est forcément la borne supérieure. C'est d'ailleurs un peu piégeux, parce qu'on a l'impression que la démonstration suivante peut marcher : je suppose qu'Arthur et Nimué ont une stratégie gagnante α témoignant A ≤_coT C (c'est-à-dire capable de C-encoder si Merlin A-encode) et une β témoignant de B ≤_coT C, et pour prouver A⊕B ≤_coT C ils vont mener deux parties en parallèle, en jouant selon α à chaque fois que Merlin leur fournit un A-encodage et selon β quand il leur fournit un B-encodage… mais cette démonstration est bidon (en gros parce que Nimué doit choisir entre jouer selon α ou selon β avant que Merlin réponde).

Je peux quand même noter que si D est décidable (= calculable), alors A⊕D est co-Turing équivalent à A : parce que si Merlin a la fantaisie de fournir un D-codage, alors on peut le transformer en A-codage et travailler avec ça. Mais je ne sais pas si ça vaut encore pour D co-décidable (et il faut d'ailleurs reconnaître que si ce n'est pas le cas, ça suggère que la notion d'ensemble co-décidable, et plus généralement de degré de co-Turing, n'est probablement pas très intéressante, ou pas vraiment la bonne… à moins qu'il y ait une autre construction qui m'échappe pour faire des bornes inf ou sup binaires).

☞ Encore une petite variante

Encore une fois, je ne sais quasiment rien dire sur le sujet. Ce ne sont pas les idées qui manquent, mais aucune ne semble aboutir à rien. J'ai essayé de changer la question un peu et de la tourner de plein de manière. Par exemple (cf. cette question MathOverflow), j'ai envie de demander, comme variante, possiblement plus abordable et néanmoins intéressante, de la devinette « difficile » :

Si C := (H × (ℕ∖H)) ∪ ((ℕ∖H) × H) est l'ensemble des couples de machines de Turing dont exactement une s'arrête et si M est un ensemble quelconque, est-il vrai que l'ensemble des fonctions f:ℕ→ℕ telles que f⁻¹(C) = M (autrement dit, qui réalisent une réduction de M à C, ou qui « C-encodent » l'ensemble M tout entier) a une borne inférieure égale à 0 dans les degrés de Turing ? (Autrement dit, est-il vrai que pour tout ensemble E non calculable on peut trouver f:ℕ→ℕ telle que f⁻¹(C) = M et que f ≱_T E ?)

J'ai réussi à montrer (cf. la question MathOverflow que je viens de lier) un résultat partiel pour certains ensembles C essentiellement aléatoires, donc pas du tout comme celui que je viens de dire, mais cet ensemble précis m'intrigue vraiment.

David Madore's WebLog: Une devinette et des méditations sur les « degrés de co-Turing »

Une devinette et des méditations sur les « degrés de co-Turing »