David Madore's WebLog: Oracles en calculabilité : degrés de Turing et diverses généralisations

Réduction de Turing ordinaire et degrés de Turing

La notion la plus standard est la réduction de Turing ordinaire (j'ajoute ordinaire parce que toutes les notions qui viennent peuvent légitiment être aussi qualifiées de réduction de Turing), et je vais commencer par la définir précisément et dire quelques choses basiques à son sujet. Elle concerne les fonctions ℕ→ℕ (c'est-à-dire, totales, prenant une seule valeur pour chaque entier naturel), ou éventuellement ℕ→{0,1} mais ça ne changera rien à l'histoire.

Une fonction f:ℕ→ℕ est dite réductible au sens de Turing (=Turing-réductible) à une fonction g:ℕ→ℕ, ou bien calculable avec g pour oracle, et on note (disons) f ≼_T g, lorsqu'il existe une machine de Turing (i.e., un algorithme) qui calcule f en ayant accès à un oracle calculant g, c'est-à-dire un gadget magique capable de fournir à l'algorithme la valeur de g en tout point souhaité.

Plus précisément, f ≼_T g signifie qu'il existe une machine de Turing qui, quand on lui donne un entier n en entrée, termine toujours en temps fini et calcule f(n) comme sortie (peu importent les manières dont n et f(n) sont codés sur la bande de la machine de Turing tant que c'est raisonnable), sachant que la machine dispose de l'accès à un oracle qui peut calculer g(m) pour n'importe quel m donné. (Voici un exemple de protocole d'interrogation de l'oracle : la machine écrit m sur un ruban dédié, entre dans un état spécial interrogation de l'oracle, l'oracle remplace m par g(m) et place la machine dans l'état réponse de l'oracle ; mais les détails sont peu importants tant qu'on parle de calculabilité.) La machine peut interroger l'oracle autant de fois qu'elle le souhaite (y compris pas du tout, mais ça ne changerait d'ailleurs rien si on imposait d'appeler l'oracle puisqu'on peut ignorer sa réponse), et elle l'interroge sur les valeurs qu'elle veut et fait ce qu'elle veut des réponses : la réponse de l'oracle pour une valeur m est toujours exactement g(m), et c'est tout. (Le temps d'interrogation de l'oracle est une étape de calcul, mais ceci est peu important puisqu'on parle de calculabilité et pas de complexité.)

En particulier, toutes les fonctions calculables (c'est-à-dire : sans oracle) sont réductibles à n'importe quelle fonction, tout simplement en utilisant un programme qui ne fait aucun appel à l'oracle (en particulier, elles sont réductibles les unes aux autres, ou par exemple à la fonction constante égale à zéro).

J'insiste bien (parce que c'est ce qui va changer dans la suite) sur le fait que cette réduction de Turing « ordinaire » concerne des fonctions totales. Notamment, l'algorithme réputé calculer f en ayant g pour oracle est censé terminer pour toute valeur n qu'on lui fournit en entrée (du moins tant que n est une représentation légitime d'un entier naturel, et la valeur calculée doit aussi en être une ; mais là non plus, ces subtilités ne changent essentiellement rien). Je réitère aussi le fait que la consultation de l'oracle n'est pas limitée (ou payante) : l'algorithme a le droit de s'en servir aussi souvent qu'il le veut.

La réduction de Turing (ordinaire, mais ça restera vrai pour les généralisations que je vais introduire après) ≼_T forme ce qu'on appelle un préordre (relation réflexive et transitive) sur l'ensemble des fonctions ℕ→ℕ, c'est-à-dire que :

• d'une part, f ≼_T f : toute fonction f est Turing-réductible à elle-même (c'est évident) ; et
• d'autre part, f ≼_T g et g ≼_T h impliquent f ≼_T h : si f est Turing-réductible à g et que g est Turing-réductible à h, alors f est Turing-réductible à h (c'est assez facile à voir : si je sais calculer f en utilisant g et que je sais calculer g en utilisant h, alors pour calculer f en utilisant h je vais utiliser l'algorithme qui me permet f au moyen de g et, à chaque fois que cet algorithme fait appel à l'oracle, j'utilise le programme qui me permet g au moyen de h à la place, en utilisant l'oracle donnant h comme boîte noire).

Ce qui manque à une relation de « préordre » pour être un ordre, c'est l'antisymétrie, et c'est justement ce qui justifie la définition suivante.

On dit que f et g sont Turing-équivalentes ou de même degré de Turing quand chacune est réductible à l'autre (i.e., on peut calculer f en ayant un oracle qui donne g, et réciproquement) : c'est-à-dire qu'on note (disons) f ≡_T g lorsque f ≼_T g et g ≼_T f. Ceci est une relation d'équivalence (c'est la notion de relation d'équivalence associée à un préordre) : les classes d'équivalence sont appelées les degrés de Turing. Autrement dit, le degré de Turing [f]_T de f est l'ensemble {g:ℕ→ℕ : g ≡_T f} de toutes les fonctions ℕ→ℕ qui sont Turing-équivalentes à f, et notamment, elles sont toutes Turing-réductibles les unes aux autres. C'est-à-dire que deux fonctions sont Turing-équivalentes exactement quand elles ont le même degré de Turing.

Intuitivement, un degré de Turing est la mesure de la puissance d'un oracle. On peut aussi considérer que c'est une forme d'« impossibilité à calculer » la fonction ou bien de « quantité d'information » (totale) contenue dans la fonction f (mais ce n'est pas exactement la même façon de la mesurer que, disons, la complexité de Kolmogorov, pour ceux qui savent ce que c'est que ça : il y a des rapports, bien sûr, mais disons très sommairement que le degré de Turing est une mesure plus grossière que la complexité de Kolmogorov ; comme ce n'est pas mon propos ici, je ne vais pas en dire plus).

Le « préordre » de la réduction de Turing devient un vrai ordre (partiel) sur les degrés de Turing : on dit qu'un degré de Turing f est inférieur ou égal à un degré de Turing g, et on note f≤g, lorsque une (ou, ce qui revient au même, toute) fonction du degré f est Turing-réductible à une (ou, ce qui revient au même, toute) fonction du degré g. (Autrement dit, [f]_T ≤ [g]_T signifie par définition exactement la même chose que f ≼_T g.)

Parmi les degrés de Turing, il en est un plus petit, qu'on note 0, c'est celui des fonctions calculables (c'est notamment celui de la fonction constante égale à 0, c'est-à-dire un oracle qui ne répond rien d'intéressant, et on peut voir ça comme une raison de cette notation ; si on préfère, c'est la puissance des oracles qui n'ont aucun intérêt comme oracles parce qu'on peut les calculer directement sans oracle).

Le problème de l'arrêt, et le saut de Turing

Un autre degré de Turing particulièrement intéressant est celui noté 0′ : c'est le degré du problème de l'arrêt. Le problème de l'arrêt est la fonction qui, sur le codage ⟨e,n⟩ d'un couple d'entiers naturels, vaut 1 si la valeur de la e-ième fonction calculable partielle en n est définie (notation : φ_e(n)↓), et 0 sinon, i.e., le problème de l'arrêt vaut 1 si l'algorithme codé par l'entier e termine quand on lui fournit n en entrée, et 0 s'il ne termine pas. (Bref, le problème de l'arrêt consiste à savoir si un algorithme donné s'arrête sur une entrée donnée ; ou, considéré comme un oracle, il permet justement de répondre à cette question.) Le problème de l'arrêt est notoirement non calculable, c'est-à-dire que 0′ > 0 dans l'ordre qu'on vient de définir sur les degrés de Turing. (Je vais dire dans un instant qu'il y a des choses strictement entre 0 et 0′, il y en a même plein.)

☞ Note en passant : Le fait de définir le problème de l'arrêt comme l'ensemble des ⟨e,n⟩, codant à la fois une machine de Turing et une entrée à celle-ci, tels que φ_e(n)↓, est sans importance : on pourrait se contenter de e et prendre, disons, n=0 (ou n=e, ce qui est peut-être moins intuitif mais c'est essentiellement ce que fait la démonstration), i.e., définir le problème de l'arrêt comme l'ensemble des e tels que φ_e(0)↓ ou φ_e(e)↓, cela ne changerait rien du tout. La même chose vaudra relativement à un oracle, et pour la machine universelle dont je parlerai plus bas, et toutes sortes de variations sur le même thème : à chaque fois, le fait de prendre des (codages de) couples ⟨e,n⟩ est une sorte de tradition plus qu'autre chose (même si ça peut simplifier certains énoncés). Néanmoins, comme cette convention est fréquente, il peut être intéressant d'avoir un nom pour désigner, dans une phrase, (le codage d')un couple formé d'une machine de Turing (éventuellement avec oracle) et d'une entrée à fournir à celle-ci : sans en faire une définition formelle ou une convention rigide, je vais avoir tendance à appeler ça un plan (d'exécution) dans ce qui suit.

Plus généralement, on peut définir une version « relative » du problème de l'arrêt, c'est-à-dire le problème de l'arrêt pour les machines disposant de g comme oracle (autrement dit, la fonction qui, sur le codage ⟨e,n⟩ d'un couple d'entiers naturels, vaut 1 ou 0 selon que la machine de Turing codée par l'entier e termine sur l'entrée n lorsqu'elle a accès à g comme oracle ; notation : φ_e^g(n)↓). Il n'est pas difficile de vérifier que ce problème de l'arrêt relativisé permet de recalculer g, et aussi que si on remplace g par une fonction qui lui est Turing-équivalente, cela fournit un problème de l'arrêt Turing-équivalent : ceci définit une opération sur les degrés de Turing qu'on appelle le saut de Turing : le saut de Turing d'un degré d, noté d′, c'est le degré de Turing du problème de l'arrêt pour les machines disposant comme oracle d'une fonction de d (fixée, peu importe laquelle). De même qu'un machine de Turing ne peut pas calculer le problème de l'arrêt, une machine de Turing ayant g pour oracle ne peut pas calculer le problème de l'arrêt des machines de Turing ayant g pour oracle, ce qui dit que d′ > d pour tout degré de Turing d.

Je peux peut-être mentionner brièvement au passage le concept de degré de Turing bas, qui est un degré d ayant le même saut de Turing que 0, c'est-à-dire d′=0′, ce qui n'implique pas d=0 comme on pourrait peut-être le croire, en revanche, ça implique évidemment que d<0′. (Symétriquement, il y a le concept de degré haut, qui est un degré d≤0′ tel que d′=0′′, ce qui n'implique pas d=0′ comme on pourrait le croire.) Un théorème important de la calculabilité est le théorème de la base basse de Jockusch et Soare, qui affirme que tout sous-arbre infini et calculable de l'arbre binaire infini (représenté, disons, comme l'ensemble {0,1}* des mots finis sur l'alphabet {0,1} et qu'on peut coder par des entiers naturels) a une branche basse, c'est-à-dire une branche infinie qui, considérée comme un ensemble d'entiers naturels, a un degré de Turing bas.

Toutes ces notions sont classiques. Il y a énormément de questions qu'on peut ensuite se poser sur les degrés de Turing, et énormément de résultats à leur sujet. Je vais mentionner quelques faits (peut-être un peu rapidement) juste pour donner une idée, mais ce n'est pas vraiment mon propos : on peut lire ce qui suit en diagonale.

Degrés de Turing calculablement énumérables

Il faut sans doute que je mentionne au moins la notion de degré de Turing calculablement énumérable (même si ce n'est pas vraiment de ça que je vais parler dans la suite, donc ceci est une sorte de digression).

Rappelons qu'un ensemble D⊆ℕ d'entiers naturels est dit semi-décidable ou calculablement énumérable (c.e.) lorsqu'il existe une machine de Turing qui, donné un élément de D, termine en temps fini et répond oui et qui, donné un élément qui n'est pas dans D, ne termine pas (elle a aussi le droit de terminer et répondre non, ça ne change rien) : on dit parfois qu'une telle machine semi-décide D ; il revient au même de demander que D soit l'image d'une fonction ℕ→ℕ. calculable (du moins pour D≠∅ ; ou disons plutôt que D soit l'ensemble des éléments >−1 de l'image d'une fonction calculable ℕ → ℕ∪{−1}). À titre d'exemple (fondamental !), le problème de l'arrêt est calculablement énumérable mais non calculable. (Voir mes notes à Télécom liées ci-dessus pour ces différentes affirmations.)

On dit qu'un degré de Turing est calculablement énumérable ou c.e. (ou semi-décidable ou semi-calculable) lorsqu'il est le degré de Turing d'(au moins) une fonction indicatrice d'un ensemble calculablement énumérable ; on notera bien qu'un degré de Turing calculablement énumérable contient plein de fonctions qui ne sont pas de cette forme, on demande juste qu'il y en ait une dans le tas.

Un degré de Turing c.e. est forcément compris au sens large entre 0 (le degré des fonctions calculables) et 0′ (le degré du problème de l'arrêt) : en effet, il s'agit simplement de montrer que si D est calculablement énumérable, alors la fonction indicatrice de D peut être calculable en ayant accès à un oracle du problème de l'arrêt, mais c'est facile car, donné une machine qui « semi-décide » D, l'oracle de l'arrêt permet justement de savoir si cette machine s'arrête, donc si un élément proposé est dans D. Bref, 0 est le plus petit degré de Turing c.e. et 0′ est le plus grand. Mais il ne faut pas s'imaginer que tout degré de Turing entre 0 et 0′ est forcément c.e.

Un problème qui a longtemps été ouvert (problème de Post) a été celui de savoir s'il existe d'autres degrés de Turing c.e. que 0 et 0′, i.e., strictement intermédiaires entre les deux. Autrement dit, des ensembles calculablement énumérables qui ne soient pas calculables, mais auxquels on ne puisse pas non plus ramener le problème de l'arrêt. La réponse est positive (c'est le théorème de Friedberg-Mučnik en réponse au problème de Post), et la démonstration est d'ailleurs explicite (on construit explicitement un programme qui énumère un certain ensemble D auquel on ne puisse pas décider algorithmiquement l'appartenance, mais qui ne permet pas pour autant de décider le problème de l'arrêt), mais cette construction fait appel à une technique (la méthode de priorité) qui dépend fortement des détails de la machine de Turing, et on ignore toujours s'il existe des problèmes de décision « naturels » qui sont ainsi de difficulté strictement intermédiaire entre 0 et 0′ (car dans la pratique, à chaque fois qu'on montre qu'un problème est algorithmiquement indécidable, c'est en lui ramenant le problème de l'arrêt).

Évocation de quelques questions sur les degrés de Turing

Il y a énormément de questions subtiles (et que j'ai d'ailleurs énormément de mal à retenir) sur les degrés de Turing et leur ordre, ou sur les degrés de Turing c.e. et leur ordre. Les deux théories (celle des degrés de Turing en général et celles des degrés de Turing c.e.) sont d'ailleurs tout à fait différentes.

À titre d'exemple, il existe des degrés de Turing non-calculables minimaux, c'est-à-dire tels que 0 < d mais qu'il n'y ait pas de degré strictement intermédiaire entre les deux ; en revanche, il n'y a pas de tel degré qui soit c.e. : au contraire, entre deux degrés de Turing c.e. comparables il y en a toujours un troisième qui soit strictement intermédiaire entre eux. Mais je ne veux pas parler de toutes ces choses.

On peut aussi chercher à itérer le saut de Turing à travers les ordinaux : c'est-à-dire qu'après les degrés 0, 0′, 0′′, 0′′′, etc., on peut construire un degré 0^(ω) (c'est, par exemple, le degré de Turing de l'oracle qui dit si un énoncé arithmétique quelconque est vrai ou faux), et plus généralement, des degrés 0^(α) pour « plein » d'ordinaux α (au moins jusqu'à l'ordinal de Church-Kleene, voire l'ordinal de l'analyse ramifiée, voire le ω₁ constructible, voyez ce billet passé poru des explications de ces termes), mais il y a plein de subtilités (par exemple, 0^(ω) n'est pas la borne supérieure de 0, 0′, 0′′… 0⁽ⁱ⁾ pour i∈ℕ ; et en outre, 0^(α) va dépendre non seulement de l'ordinal α mais de sa notation ordinale, ce qui est la raison pour laquelle on ne peut pas itérer transfiniment sans se poser de question). Je ne veux pas non plus parler de toutes ces choses, je les évoque juste pour dire que ce sont des questions abondamment étudiées.

Bornes sup et inf binaires sur les degrés de Turing

Mentionnons quand même un point important : l'existence d'une borne supérieure et l'inexistence (en général) d'une borne inférieur pour deux degrés de Turing.

Donnés deux degrés de Turing a et b il y a un degré de Turing noté a∨b (ou parfois a⊕b) qui est leur borne supérieure, c'est-à-dire le plus petit degré de Turing supérieur ou égal à a et b.

C'est même assez intuitif : si a est représenté par une fonction a (rappelons que ça signifie notamment qu'une fonction est de degré ≤a exactement quand on peut la calculer avec a pour oracle) et b par une fonction b, alors a∨b devrait correspondre aux fonctions calculables avec accès à la fois à a et b pour oracles. Mais comment réaliser cette notion d'avoir accès à la fois à a et b pour oracles ? C'est facile : il suffit de construire un oracle c qu'on interroge en demandant soit je voudrais la réponse de a sur la question suivante soit je voudrais la réponse de b sur la question suivante : précisément, on pose c(⟨0,m⟩) = a(m) et c(⟨1,m⟩) = b(m) (et pour toute autre valeur, c vaut 0, disons), le 0 en premier argument servant à dire je souhaite interroger a et le 1 en premier argument servant à dire je souhaite interroger b. (Il revient au même, si on préfère, et c'est peut-être plus courant, d'alterner valeurs de a et de b sur les entiers pairs et impairs, c'est-à-dire de poser c(2m)=a(m) et c(2m+1)=b(m) : la seule chose qui importe est qu'en interrogeant c on puisse, dans les faits, interroger a et b comme on le souhaite et que les éventuelles autres valeurs soient sans objet.) Alors cette fonction c (parfois notée a⊕b) sert à encoder l'information de a et b à la fois, et a∨b est précisément le degré de Turing de la fonction c ainsi construite (notamment, il ne dépend pas du choix de a et b dans a et b respectivement), et c'est bien la borne supérieure au sens de l'ordre sur les degrés de Turing.

Intuitivement, le paragraphe précédent signifie qu'on a une façon naturelle et assez évidente de combiner la puissance de deux oracles en un seul, leur borne supérieure.

En revanche, il n'y a pas de façon de former la borne inférieure de deux degrés de Turing en général : ce degré de Turing a∧b qui n'existe pas en général (mais il existe parfois) serait tel que les fonctions de degré ≤a∧b sont exactement celles qui sont calculables avec un oracle dans a et avec un oracle dans b : le problème est qu'il n'y a pas moyen de faire une fonction qui reflète les choses qu'on peut calculer au moyen de a et aussi (peut-être différemment) au moyen de b, une sorte d'information commune, comme on l'a fait pour fabriquer a∨b ci-dessus en réunissant l'information qu'elles apportent. On peut considérer que c'est là une limitation des degrés de Turing, et le signe qu'il peut être intéressant de les généraliser.

Notons aussi qu'il n'y a pas non plus, en général, de borne supérieure d'une infinité de degrés de Turing : même pour une suite a₀, a₁, a₂… de degrés de Turing, la construction qui semble pourtant évidente c(⟨i,m⟩)=a_i(m) ne fournit pas une borne supérieure, et d'ailleurs ne fournit même pas un degré de Turing bien-défini, car elle dépend de la manière dont les a_i ont été choisis et indexés dans les degrés a_i. (Ce qui n'empêche que cette construction a un intérêt : par exemple, 0^(ω) est effectivement défini de la sorte à partir des degrés 0, 0′, 0′′, 0′′′, etc.)

Réduction des fonctions partielles

Comme expliqué dans l'introduction, je veux maintenant évoquer différentes généralisations de la notion de réduction de Turing, et d'oracle au sens de celle-ci. Plus exactement, on va généraliser les fonctions auxquelles on applique la réduction de Turing, tout en cherchant à garder autant que possible la même notion de réduction. La première généralisation, assez évidente, consiste à autoriser les fonctions partielles. (Je vais noter ℕ⇢ℕ, avec une flèche en pointillés, pour une fonction partielle de ℕ vers ℕ, c'est-à-dire une fonction définie sur un sous-ensemble de ℕ et à valeurs dans ℕ. Par ailleurs, faute de terminologie standard ou adéquate, je vais appeler degrés T1 les degrés définis ici quand il s'agit de lever une ambiguïté, même s'il peut être légitime de les appeler degrés de Turing des fonctions partielles.)

En fait, il y a plein de notions subtilement différentes qu'on peut imaginer utiliser pour dire qu'une fonction partielle f:ℕ⇢ℕ est calculablement réductible à une autre g:ℕ⇢ℕ : voir cette question MathOverflow où je définis six notions subtilement différentes (notées S, N, W, S*, N* et W*). Mais je vais me contenter ici d'une seule de ces notions, parce que c'est elle qui va se prêter aux généralisations ultérieures que je vais introduire après (dans la terminologie de la question que je viens de lier, la réductibilité T1 est la notion S*, ou sous-réductibilité de Sasso) : je vais juste dire réductible pour simplifier, mais on prendra garde au fait que, comme je viens de le dire, ce n'est pas la seule notion possible, et il est même plausible que ce ne soit pas la plus standard.

L'idée intuitive, quand l'oracle est une fonction partielle g:ℕ⇢ℕ, est qu'il y a des questions interdites : si on interroge l'oracle sur une question interdite, c'est-à-dire qu'on lui demande la valeur g(m) alors que g(m) n'est pas défini, on n'obtient jamais de réponse et le calcul dans son ensemble ne termine pas. De façon encore plus frappante : si on pose une question interdite à l'oracle, alors l'oracle vous tue pour votre impudence. En contrepartie, la fonction f qu'on est censée calculer ne sera elle-même interrogée que sur des valeurs où elle est définie : c'est-à-dire que si f(n) n'est pas définie, on ne place aucune contrainte sur ce que le calcul fera (peu importe s'il ne termine pas, peu importe s'il pose des questions interdites à l'oracle, mais peu importe aussi s'il termine alors que la valeur demandée n'est pas définie), tout ce qu'on demande c'est que f(n) soit calculée correctement quand f(n) est définie. Autrement dit :

Une fonction partielle f:ℕ⇢ℕ est dite réductible (au sens T1 s'il y a besoin de préciser) à une fonction partielle g:ℕ⇢ℕ, ou bien calculable avec g pour oracle lorsqu'il existe une machine de Turing (i.e., un algorithme) qui, quand on lui fournit un entier n en entrée tel que f(n) soit définie, termine toujours en temps fini et calcule f(n) comme sortie, sachant que la machine dispose de l'accès à un oracle qui peut calculer g(m) pour n'importe quel m tel que g(m) soit défini, mais n'a pas le droit d'interroger g(m) sur une valeur non définie. La machine peut interroger l'oracle autant de fois qu'elle le souhaite (y compris pas du tout) tant que les valeurs interrogées sont toutes définies et elle fait ce qu'elle veut des réponses : la réponse de l'oracle pour une valeur m est toujours exactement g(m), et c'est tout.

Je ne sais pas bien quelle terminologie ou quelle notation utiliser. On peut considérer que c'est toujours la réduction de Turing (pour les fonctions totales c'est la même), elle a simplement été généralisée à un ensemble plus grand. Pour faire quand même la différence, mettons que je vais noter f ≼_T1 g pour la réductibilité définie au paragraphe précédent.

Pour être bien clair, cette définition fait notamment que toute restriction de g à un domaine de définition plus petit est réductible à g (la réductibilité ≼_T1 dont je parle est la composition de la réductibilité de Sasso et de la restriction des fonctions). Symboliquement : si g étend f en tant que fonction partielle, alors en particulier f ≼_T1 g. Intuitivement, si vous interdisez bêtement certaines questions, cela rend toujours votre oracle moins puissant.

Comme précédemment, la notion définit un préordre. Lorsque f et g sont totales, évidemment, il s'agit du même préordre qu'on a déjà défini (on l'a étendu à un ensemble de fonctions plus large, mais pour f et g totales, les relations f ≼_T g et f ≼_T1 g disent exactement la même chose). Comme précédemment, on peut définir une relation d'équivalence f ≡_T1 g lorsque f ≼_T1 g et g ≼_T1 f (et je répète que, lorsque f et g sont totales, les relations f ≡_T g et f ≡_T1 g sont équivalentes).

Les classes d'équivalence pour cette relation ≡_T1 peuvent s'appeler degrés de Turing des fonctions partielles ou quelque chose de ce genre (mais attention, j'ai signalé plus haut en petits caractères que ce n'est pas la seule notion qui peut être appelée ainsi) : disons degrés T1 si j'ai besoin d'un terme.

Vu que f ≡_T g et f ≡_T1 g sont équivalentes lorsque f et g sont totales, on peut identifier un degré de Turing ordinaire (i.e., une classe d'équivalence pour ‘≡_T’) avec un degré T1 en identifiant la classe d'équivalence [f]_T d'une fonction f:ℕ→ℕ totale pour l'équivalence de Turing ordinaire ‘≡_T’ avec la classe d'équivalence [f]_T1 de la même fonction pour ‘≡_T1’ (même si cette dernière classe d'équivalence est, en fait, plus grande et contient toujours des fonctions partielles). Cette injection [f]_T ↦ [f]_T1 permet de considérer, et on le fera toujours, les degrés de Turing ordinaires comme un sous-ensemble des degrés T1. Précisément, les degrés de Turing ordinaires s'identifient au sous-ensemble des degrés T1 qui contiennent (au moins) une fonction totale. C'est un sous-ensemble strict (i.e., il y a des degrés T1 qui ne contiennent aucune fonction totale), même si ce n'est pas tout à fait évident à montrer.

Bornes sup et inf binaires sur les degrés T1 ; la construction ‘⌘’

On dispose toujours d'une opération a∨b sur deux degrés au sens définis ici (deux degrés T1) : l'idée intuitive est la même (on autorise à interroger librement les deux oracles). Formellement, si a et b sont deux fonctions partielles ℕ⇢ℕ, on peut définir une fonction partielle c:ℕ⇢ℕ par c(⟨0,m⟩) = a(m) lorsque celle-ci est définie et c(⟨1,m⟩) = b(m) lorsque celle-ci est définie, et toute autre valeur indéfinie. Il est facile de voir, comme pour les degrés de Turing ordinaires, que le degré de c ne dépend que des degrés a et b de a et b respectivement, et que ceci constitue la borne supérieure de a et b, et aussi qu'elle coïncide avec celle des degrés de Turing ordinaires lorsque a et b sont des degrés de Turing ordinaires (i.e., représentables par a et b totales). Bref, tout se passe comme avant.

Mais une différence importante, et peut-être surprenante, avec les degrés de Turing ordinaires, est que cette fois on a aussi une borne inférieure de deux degrés (T1, donc) quelconques : pour deux degrés a et b on peut définir un degré a∧b tel que x≤(a∧b) si et seulement si x≤a et c≤b. Ou, ce qui revient au même, données a et b sont deux fonctions partielles ℕ⇢ℕ, on peut définir une fonction partielle c:ℕ⇢ℕ telle que les fonctions réductibles à c soient exactement celles réductibles à la fois à a et à b. Pourquoi peut-on faire cela alors qu'on ne le peut pas (en général) pour des fonctions totales ? Ça vaut la peine d'y réfléchir un moment. Avant d'y répondre, il faut que je donne l'idée-clé qui fait que les fonctions partielles se comportent mieux que les fonctions totales ici :

Rappelons ce qu'est la machine de Turing universelle : c'est une fonction qui, sur le codage ⟨e,n⟩ d'un couple d'entiers naturels, a la même valeur (généralement notée φ_e(n)) que la e-ième fonction calculable partielle en n si elle est définie (et sinon, n'est pas définie) ; autrement dit, c'est un algorithme qui prend en entrée un autre algorithme e et une entrée n à fournir à cet algorithme (appelons ça un plan d'exécution), et qui exécute le plan en question et renvoie la même valeur si l'algorithme termine lui-même (et ne termine pas sinon). Ça n'a rien de magique : il s'agit juste de dire qu'on peut exécuter un algorithme fourni en entrée, i.e., on peut écrire, par exemple, un interpréteur de machine de Turing en machine de Turing.

La machine de Turing universelle fonctionne aussi bien avec oracle que sans oracle : donné un oracle g (fonction totale ou même partielle), on peut considérer la machine de Turing universelle avec cet oracle : donné le codage ⟨e,n⟩ d'un couple d'entiers naturels, elle fait la même chose que la machine de Turing codée par l'entier e sur l'entrée n lorsqu'elle a accès à g comme oracle. Ceci définit une nouvelle fonction partielle qu'on pourrait appeler, euh, disons, ⌘g : ℕ⇢ℕ (formellement, ⌘g est la fonction ⟨e,n⟩ ↦ φ_e^g(n)). Intuitivement, il faut imaginer ça comme un « oracle g programmable » : au lieu de répondre bêtement à une question comme le fait g, cette fonction ⌘g prend en entrée tout un plan d'interrogation de g (c'est le couple ⟨e,n⟩), l'exécute et renvoie le résultat. Remarquez que la fonction ⌘g est partielle même si g était totale, parce qu'il y a toujours des machines de Turing qui ne terminent pas.

Pour qu'il n'y ait pas de doute que les définitions sont cohérentes entre elles, la réduction f ≼_T1 g définie au-dessus signifie exactement, et par définition, qu'il existe e∈ℕ tel que pour tout n du domaine de définition de f on ait ⌘g(⟨e,n⟩) défini et égal à f(n).

Bref, ⌘g doit se comprendre intuitivement comme une version de l'oracle g avec programmation intégrée, une version plus flexible de celui-ci.

Néanmoins, au niveau calculabilité, ce ⌘g vaut exactement autant que g : d'une part il est évident que g ≼_T1 ⌘g (pour calculer g(m) il suffit de construire le programme qui appelle l'oracle sur son argument, et de l'exécuter), mais d'autre part il est aussi vrai que ⌘g ≼_T1 g justement parce qu'on peut réaliser une machine universelle. Donc ⌘g a le même degré (T1) que g. (Ceci ne serait plus vrai si nos oracles étaient limités à un unique appel, parce qu'un unique appel à ⌘g permet de faire n'importe que plan d'appels à g ; donc il est crucial ici que je parle depuis le début de réduction de Turing et pas de « réduction de Weihrauch » : pour la réduction de Turing, g ou ⌘g sont équivalentes.) Néanmoins, la construction g ↦ ⌘g a un intérêt parce qu'elle remplace une fonction g quelconque par une fonction qui se comporte de façon bien plus « robuste ». Et notamment, c'est ça qui nous permet de construire a∧b.

Justement, supposons données a et b sont deux fonctions partielles ℕ⇢ℕ, et on veut définir une fonction partielle c:ℕ⇢ℕ telle que les fonctions réductibles à c soient exactement celles réductibles à la fois à a et à b. On va la définir comme ceci : c(⟨m₁,m₂⟩) est égale à la valeur commune de ⌘a(m₁) et de ⌘b(m₂) si ces deux valeurs sont toutes les deux définies et sont égales, et n'est pas définie sinon. Pour dire les choses autrement, pour interroger l'oracle c, vous devez fournir un plan m₁=⟨e₁,n₁⟩ d'interrogation de a et un plan m₂=⟨e₂,n₂⟩ d'interrogation de b, et si ces plans calculent une même valeur bien définie, alors, et seulement alors, c vous renvoie cette valeur.

Il n'est pas difficile de voir que cette construction donne bien la borne inférieure recherchée : d'une part on a bien c ≼_T1 a (il suffit d'ignorer le second argument et de passer le premier à ⌘a ; je rappelle que ma définition de la réduction T1 autorise à calculer plus de valeurs que ce qui était demandé), et bien sûr, symétriquement, c ≼_T1 b ; d'autre part, si on a f ≼_T1 a et f ≼_T1 b, c'est qu'il existe un programme permettant de calculer f(n) en fonction de n donné l'accès à un oracle qui renvoie a, et symétriquement pour b : si on fournit ces deux programmes à c (avec la même entrée n), il calculera f(n) puisque, justement, nos deux programmes calculent la même valeur.

Voici donc les degrés de Turing ordinaires (ceux des fonctions totales ℕ→ℕ) inclus dans l'ensemble plus gros des degrés T1 (degrés « de Turing » des fonctions partielles ℕ⇢ℕ) en préservant l'ordre et la borne supérieure binaire mais en ajoutant les bornes inférieures. Il y a sans doute beaucoup plus de choses intéressantes à dire sur cet ensemble des degrés T1, mais je veux passer à la généralisation suivante.

Réduction des fonctions non-déterministes

La généralisation suivante consiste à ce que les fonctions (celle qu'on cherche à calculer, et les oracles auxquels on a accès) soient non-déterministes : elles renvoient possiblement plusieurs valeurs. (Faute de terminologie standard ou adéquate, je vais parler ici de degrés T2.)

Autrement dit, on s'intéresse maintenant à des fonctions ℕ⇢𝒫(ℕ), c'est-à-dire que non seulement g(m) n'est pas forcément définie, mais elle renvoie un ensemble de valeurs (il sera utile de distinguer le cas où g(m) est non défini et le cas où g(m) est défini mais vide, c'est-à-dire ne renvoie aucune valeur : même si on peut vouloir interdire cette dernière situation, le fait de l'autoriser semble plus satisfaisant).

L'idée intuitive est que g(m) est l'ensemble des réponses à votre question, i.e., des valeurs que l'oracle pourra vous renvoyer : quand vous faites appel à l'oracle, il vous renverra une valeur de l'ensemble, mais vous ne contrôlez pas laquelle (et il faut plus ou moins s'imaginer qu'il va renvoyer celle qui vous arrange le moins ; ou en tout cas, on doit se vous préparer à cette possibilité, c'est-à-dire que quand on fait un calcul utilisant l'oracle g, le calcul doit fonctionner quelle que soit la valeur retournée à chaque étape). Symétriquement, quand on vous demande de calculer f et que f(n) a plusieurs éléments, vous pouvez renvoyer celui qui vous arrange, votre but est d'en produire un (et celui que vous produisez peut dépendre de ce que l'oracle vous aura donné quand vous avez fait appel à lui).

Et si un ensemble est vide, alors ? Si la fonction f que vous devez calculer est (définie et) vide pour une certaine valeur n, alors vous n'avez aucun moyen d'y arriver (sauf de mettre en échec l'oracle comme je vais le dire), donc vous ne pouvez pas la calculer (sauf…). Mais symétriquement, quand vous appelez l'oracle sur une valeur m (pour laquelle g(m) est défini), il doit choisir une des valeurs dans l'ensemble g(m) : donc si g(m)=∅, vous venez de mettre l'oracle en échec, et vous avez gagné la partie (il vous donne les clés du royaume des cieux, quelque chose comme ça), quelle que soit la fonction que vous aviez comme mission de calculer (même si elle comporte elle-même des ensembles vides).

Mon explication intuitive peut sembler assez vaseuse, donc voici une version précisément formalisée :

Une fonction partielle multivaluée, c'est-à-dire une fonction f:ℕ⇢𝒫(ℕ), est dite réductible (au sens T2 s'il y a besoin de préciser) à une autre telle fonction g:ℕ⇢𝒫(ℕ), ou bien calculable avec g pour oracle, et on notera ça f ≼_T2 g, lorsqu'il existe une machine de Turing (i.e., un algorithme) qui, quand on lui fournit un entier n en entrée tel que f(n) soit définie, termine toujours en temps fini et calcule un certain élément de f(n) comme sortie, sachant que la machine dispose de l'accès à un oracle qu'on peut interroger pour n'importe quel m tel que g(m) soit défini (mais on n'a pas le droit d'interroger g(m) sur une valeur non définie) et qui, dans ce cas, renvoie un élément quelconque de g(m). La machine peut interroger l'oracle autant de fois qu'elle le souhaite (y compris pas du tout) tant que les valeurs interrogées sont toutes définies et elle fait ce qu'elle veut des réponses : la réponse de l'oracle pour une valeur m est un élément quelconque de g(m). Le calcul est valable quand chaque interrogation de l'oracle porte sur une valeur pour laquelle g(m) est définie, et que, quel que soit l'élément de g(m) que l'oracle répond à chaque valeur pour laquelle on l'interroge, l'algorithme termine et renvoie un élément de f(n) (qui a le droit d'être différent selon les choix effectués par l'oracle).

Pour être parfaitement clair sur les cas « non défini » et « vide » :

• peu importe ce que fait l'algorithme sur l'entrée n lorsque f(n) n'est pas défini, ces valeurs ne seront pas consultées ni interrogées,
• l'algorithme n'a pas le droit d'interroger g(m) si g(m) n'est pas défini (le faire cause son plantage immédiat, i.e., c'est une forme de non-terminaison comme une boucle infinie),
• si g(m)=∅, alors l'algorithme est considéré comme ayant gagné son calcul (quel que soit la fonction à calculer, arriver à mettre en défaut l'oracle est une façon d'y arriver),
• si f(n)=∅, alors il n'y a pas moyen de mener le calcul (autrement qu'en mettant en défaut l'oracle, comme au point précédent).

On voit à cette description que la relation entre l'algorithme et l'oracle commence à devenir adversariale, et voici une façon de le redire :

Chercher une réduction de f à g revient à faire gagner Arthur à un jeu à deux joueurs, dont les joueurs s'appellent Arthur (l'algorithme) et Merlin (l'oracle) :

• au premier tour, Merlin (qui commence) joue un élément n∈ℕ ; Merlin perd dès le premier tour (i.e., Arthur gagne) si f(n) n'est pas défini ;
• à chaque tour suivant, Arthur a deux types de coups possibles : il peut soit « déclarer la fin du calcul » avec une valeur k∈ℕ, soit « lancer une interrogation de l'oracle » avec une valeur m∈ℕ ;
• lorsque Arthur déclare la fin du calcul avec une valeur k, le jeu prend fin ; Arthur gagne si k ∈ f(n), sinon Merlin gagne ;
• lorsque Arthur lance une interrogation de l'oracle avec une valeur m, Merlin joue ensuite un élément ℓ∈ℕ ; Merlin perd à ce stade (i.e., Arthur gagne) si ℓ∉g(m), sinon le jeu continue (avec un coup d'Arthur).

Le jeu prend fin dès qu'un des joueurs a gagné, c'est-à-dire soit lorsque Arthur a déclaré la fin du calcul soit lorsqu'un des joueurs a violé une contrainte sur le coup. Si le jeu dure indéfiniment (Arthur ne déclare jamais la fin du calcul), alors Arthur a perdu (i.e., Merlin a gagné).

Par ailleurs, Arthur (simple mortel !) joue conformément à un algorithme, c'est-à-dire qu'il suit une stratégie qui calcule le coup qu'il fait (soit la valeur k sur laquelle il déclare la fin du calcul, soit la valeur m sur laquelle il lance une interrogation) en fonction de tous les coups joués précédemment, tandis que Merlin joue arbitrairement. Plus exactement, ce que je veux dire, c'est que la définition de f ≼_T2 g (f est réductible à g) pour deux fonctions f et g partielles multivaluées (i.e., ℕ⇢𝒫(ℕ)) est : il existe un algorithme (prenant en entrée les coups joués précédemment et renvoyant le coup d'Arthur) constituant une stratégie gagnante d'Arthur, contre n'importe quelle stratégie de Merlin, dans le jeu qui vient d'être décrit. La stratégie de Merlin, elle, n'a pas à être calculable : l'intérêt de la réduction réside justement dans le fait qu'une stratégie calculable d'Arthur gagne contre Merlin quoi que fasse Merlin.

Comme dans le cas T1 (celui des fonctions partielles simplement valuées), toute restriction de g à un domaine de définition plus petit est réductible à g. C'est aussi, maintenant, le cas de toute fonction qui élargit l'ensemble g(m) pour tout m.

De nouveau, la notion définit un préordre. Lorsque f et g sont simplement valuées (chaque f(n) qui est défini est un singleton, et pareil pour g, et en identifiant ça à des fonctions ℕ⇢ℕ), il s'agit du même préordre T1 qu'on a déjà défini (et qui généralise lui-même la réduction de Turing ordinaire). De nouveau, on peut définir une relation d'équivalence f ≡_T2 g lorsque f ≼_T2 g et g ≼_T2 f (et je répète que, lorsque f et g sont simplement valuées, les relations f ≡_T1 g et f ≡_T2 g sont équivalentes, et en particulier si f et g sont totales et simplement valuées c'est exactement la réduction de Turing ordinaire).

On a donc de nouveau un ensemble de degrés, qu'on peut appeler les degrés T2, ou degrés de Turing des fonctions partielles multivaluées.

Comme précédemment, vu que f ≡_T1 g et f ≡_T2 g sont équivalentes lorsque f et g sont simplement valuées, on obtient une injection [f]_T1 ↦ [f]_T2 des degrés T1 dans les degrés T2 en envoyant la classe d'équivalence pour ‘≡_T1’ de f vers la classe d'équivalence pour ‘≡_T2’ de cette même fonction. Ceci permet de considérer, et on le fera toujours, les degrés T1 (et a fortiori les degrés de Turing ordinaires) et comme un sous-ensemble des degrés T2. Précisément, les degrés T1 s'identifient au sous-ensemble des degrés T2 qui contiennent (au moins) une fonction simplement valuée. C'est un sous-ensemble strict pour la raison évidente qui va être dite dans deux paragraphes.

Comme précédemment, ces degrés ont des bornes supérieures et inférieures binaires : et elles sont données, mutatis mutandis par les mêmes constructions que pour les degrés T1… enfin, si le mutare mutanda est assez évident pour la borne supérieure, il l'est un peu moins pour la borne supérieure qui ne semble pas coïncider avec celle sur les degrés T1, donc je vais en parler un peu plus précisément dans la section suivante, qu'on peut sauter ainsi que celle d'après si on veut passer rapidement aux degrés T3.

Dans les degrés T2, cette fois, il y a un plus grand degré (on pourrait le noter ⊤) : dès que g(m)=∅ pour au moins un entier m, toute fonction f est réductible à g : il suffit d'interroger l'oracle sur la valeur de g(m) (i.e., pour Arthur d'appliquer la stratégie consistant à lancer l'interrogation pour m, à laquelle Merlin ne peut pas répondre). Inversement, les seules fonctions auxquelles se ramènent une telle fonction g sont les fonctions qui vérifient la même propriété, car si Merlin joue m au permier coup, la seule stratégie permettant à Arthur de gagner est de lancer une interrogation à laquelle Merlin ne peut pas répondre. Plus loin, j'appellerai degré omnipotent ce plus grand degré.

Bornes sup et inf binaires sur les degrés T2

Comme pour les degrés de Turing ordinaires et T1, la borne supérieure de deux degrés T2 ne pose pas de problème à définir : données deux fonctions partielles multivaluées a et b, on en définit une qui consiste à permettre à Arthur de choisir s'il veut interroger a ou b : précisément, si a,b : ℕ⇢𝒫(ℕ), on définit simplement c : ℕ⇢𝒫(ℕ) par c(⟨0,m⟩) = a(m) lorsque celle-ci est définie et c(⟨1,m⟩) = b(m) lorsque celle-ci est définie, et toute autre valeur indéfinie. Ceci définit bien la borne supérieure des degrés T2 comme on l'attend, et il n'y a pas de surprise particulière.

La construction étant exactement la même, la borne supérieure binaires de degrés de Turing ordinaires, ou de degrés T1, est toujours la même dans les degrés T2 (i.e., le plongement de ces différents ensembles de degrés préserve l'opération de borne supérieure binaire : on peut noter a∨b sans avoir à dire dans quel ensemble de degrés on se place).

Pour la borne inférieure, il faut modifier un petit peu la construction qu'on a utilisée pour les degrés T1.

Je rappelle que, pour une fonction g : ℕ⇢ℕ (partielle déterministe, c'est-à-dire du niveau T1), j'ai défini une fonction ⌘g : ℕ⇢ℕ (ma notation !) qui consiste à faire tourner la machine de Turing universelle ayant accès à g comme oracle ; cette fonction est de même degré T1 que g mais permet de construire sur les degrés T1 la borne inférieure binaire (qui n'existe généralement pas pour les degrés de Turing ordinaires).

Au niveau T2, la construction ⌘g est définie ainsi : donné un plan ⟨e,n⟩ (c'est-à-dire le code e d'une machine de Turing avec oracle et une entrée n à lui passer), alors ⌘g(⟨e,n⟩) est définie lorsque l'exécution du plan termine quelle que soit la valeur renvoyée par g à chaque interrogation de l'oracle, et, si c'est bien le cas, l'ensemble des valeurs ⌘g(⟨e,n⟩) est l'ensemble de toutes les valeurs possibles renvoyées par la machine. (C'est donc ce qu'on attend raisonnablement de la fonction non-déterministe définie par un calcul faisant appel à un oracle non-déterministe g, mais je souligne une fois de plus que s'il y a une possibilité quelconque que le calcul ne termine pas — que ce soit parce qu'il fait appel à une valeur non-définie de g ou parce que la machine part en boucle infinie — alors ⌘g(⟨e,n⟩) n'est pas définie.)

Pour qu'il n'y ait pas de doute que les définitions sont cohérentes entre elles, la réduction f ≼_T2 g définie au-dessus signifie exactement, et par définition, qu'il existe e∈ℕ tel que pour tout n du domaine de définition de f on ait ⌘g(⟨e,n⟩) défini et ⊆ f(n).

Comme dans le cas T1, on a g ≡_T2 ⌘g.

On peut alors définir la borne inférieure binaire des degrés T2 : supposons données a et b sont deux fonctions partielles multivaluées ℕ⇢𝒫(ℕ), et on veut définir une fonction partielle c : ℕ⇢𝒫(ℕ) telle que les fonctions réductibles à c soient exactement celles réductibles à la fois à a et à b. On va la définir comme ceci : c(⟨m₁,m₂⟩) est égale à la réunion disjointe étiquetée (je vais définir ça tout de suite) ⌘a(m₁) ⊔ ⌘b(m₂) de ⌘a(m₁) et de ⌘b(m₂) si ces deux valeurs sont toutes les deux définies, et n'est pas définie sinon.

Si P et Q sont deux parties de ℕ, la réunion disjointe étiquetée P⊔Q, désigne ici l'ensemble des ⟨0,p⟩ pour p∈P et des ⟨1,q⟩ pour q∈Q.

Pour dire les choses autrement, pour interroger l'oracle c, vous devez fournir un plan m₁=⟨e₁,n₁⟩ d'interrogation de a et un plan m₂=⟨e₂,n₂⟩ d'interrogation de b, ces deux plans doivent tous les deux terminer correctement (si l'un des deux échoue, l'oracle vous tue) ; et si c'est le cas, l'oracle c vous renvoie une valeur de l'un ou de l'autre plan, en vous disant lequel.

Comme au niveau T1, il n'est pas difficile de voir que cette construction donne bien la borne inférieure recherchée. La construction est presque la même, mais ça vaut la peine de souligner la différence : dans la construction au niveau T1, l'oracle c exige que les deux plans d'exécution (à a et à b) soient valables et donnent exactement le même résultat, alors que dans la construction au niveau T2, l'oracle c exige que les deux plans d'exécution (à a et à b) soient valables, et il renvoie non-déterministement une valeur renvoyée par l'un des deux (avec l'information de laquelle il a choisi).

Notons que lorsque a et b se trouvent être toutes les deux des fonctions partielles simplement valuées (ℕ⇢ℕ), les deux constructions ont un sens : on a alors c₁ : ℕ⇢ℕ qui est donnée par la première, et c₂ : ℕ⇢𝒫(ℕ) donnée par la seconde. Il est clair que c₁ ≼_T2 c₂, et, en fait, le degré de c₁ est le plus grand degré T1 qui est ≤ au degré de c₂. J'ignore, cependant, si ces degrés peuvent vraiment être différents (j'imagine que oui, mais je n'ai pas de preuve) : si c'est bien le cas, cela signifie que le plongement des degrés T1 dans les degrés T2, bien qu'il préserve l'ordre et les bornes supérieures binaires, ne préserve pas les bornes inférieures binaires. Bref, quand on parle de a∧b pour a et b deux degrés T1, il faut préciser si cette borne est prise dans les degrés T1 ou dans les degrés T2.

J'en profite d'ailleurs pour réfuter une erreur possible : on aurait pu croire que la borne inférieure dans les degrés T2 entre le degré de a et le degré de b s'obtient plus simplement en prenant la réunion a(m)∪b(m) des valeurs possibles des deux fonctions, ou, de façon un chouïa moins naïve, la réunion disjointe étiquetée a(m)⊔b(m) : la fonction c ainsi définie vérifie certes c ≼_T2 a et c ≼_T2 b (de façon évidente), mais ce n'est pas parce qu'une fonction est réductible à a et à b à la fois qu'elle sera réductible à cette fonction c (même si on a pris l'opération ‘⊔’), essentiellement parce que la construction en question insiste trop naïvement pour combiner a et b prises à la même valeur m. Pour illustrer le problème, si on définit a comme valant 0 en 2m et Halting(m) en 2m+1 (où Halting désigne le problème de l'arrêt), et b comme valant Halting(m) en 2m et 0 en 2m+1, alors manifestement a ≡_T2 b donc la borne inférieure de leurs degrés est leur degré commun ; pourtant, si on les combine comme je viens de dire, alors c est de degré trivial (0) car Merlin peut choisir de renvoyer a quand on l'interroge sur une valeur paire et b quand on l'interroge sur une valeur impaire, et il ne fournit donc aucune information.

Un degré T2 intermédiaire naturel

Il y a autre chose qui mérite d'être noté au niveau T2 : j'ai mentionné plus haut qu'on ne connaît pas de degré de Turing ordinaire « naturel » (calculablement énumérable, mais peu importe ici) qui soit strictement intermédiaire entre 0 (degré de ce qui est calculable) et 0′ (degré du problème de l'arrêt). Quand on passe aux fonctions non-déterministes, en revanche il y a un tel degré (enfin, il y en a plein mais celui-ci semble raisonnablement intéressant, et en tout cas me semble mériter le qualificatif de naturel). Je vais en parler un petit peu : tout ceci est essentiellement une digression, donc on peut sauter la fin de cette section, mais je pense que c'est quand même pertinent d'en dire un mot, à la fois parce que ça remet en perspective le problème de Post, et aussi parce que ça donne un exemple de la manière dont fonctionne la réduction T2.

Je vais décrire trois fonctions non-déterministes (i.e., ℕ⇢𝒫(ℕ)) différentes, toutes les trois du même degré T2 (je vais expliquer pourquoi), pour définir le degré en question (l'une de ces descriptions, ainsi que la preuve de l'équivalence, suppose quelques connaissances en logique ; on peut sauter ce passage, mais sinon je pense que ce billet passé explique assez pour suivre) :

• Première fonction, appelons-la LLPO pour des raisons en lien avec les maths constructives mais je n'ai pas envie d'en dire plus ici. La fonction LLPO prend en entrée les codes ⟨⟨e₁,n₁⟩, ⟨e₂,n₂⟩⟩ de deux machines de Turing ordinaires e₁, e₂ avec des entrées n₁,n₂ à leur fournir. La fonction LLPO est définie lorsque au moins une des deux machines fournies ne termine pas, c'est-à-dire lorsque φ_e₁(n₁)↑ ou bien φ_e₂(n₂)↑ (la notation φ_e(n)↑ signifiant que l'algorithme codé par l'entier e ne termine pas quand on lui fournit n en entrée ; le ou bien est évidemment un ou inclusif). Si les deux machines terminent, la valeur de LLPO est non-définie (c'est une « question interdite »). Si au moins une des deux machines ne termine pas, alors LLPO renvoie, de façon non-déterministe, une des machines qui ne termine pas. Pour être tout à fait clair, la fonction LLPO : ℕ⇢𝒫(ℕ) dont je parle est la suivante : son domaine de définition est l'ensemble des ⟨⟨e₁,n₁⟩, ⟨e₂,n₂⟩⟩ tels que φ_e₁(n₁)↑ ou bien φ_e₂(n₂)↑ ; et, sur le codage d'un tel couple, la fonction LLPO vaut {⟨e_i,n_i⟩ : i∈{0,1} et φ_ei(n_i)↑}, c'est-à-dire que ses valeurs possibles sont les ⟨e_i,n_i⟩ pour lesquelles φ_ei(n_i)↑.
• La seconde fonction, appelons-la LLPO⁺, est presque identique à la précédente, mais la différence est que, quand les deux machines terminent, au lieu que la question soit interdite, la fonction vous renvoie n'importe laquelle des deux (toujours de façon non-déterministe). Autrement dit, LLPO⁺ est définie sur tous les ⟨⟨e₁,n₁⟩, ⟨e₂,n₂⟩⟩ ; mais cette fois l'ensemble des valeurs possibles est {⟨e_i,n_i⟩ : i∈{0,1} et (si (φ_e₁(n₁)↑ ou bien φ_e₂(n₂)↑) alors φ_ei(n_i)↑)}.
• La troisième fonction, appelons-la Consist, prend en entrée un énoncé logique P dans le langage de l'arithmétique (du premier ordre), et elle peut renvoyer P si P est cohérent avec l'arithmétique de Peano (c'est-à-dire : si sa négation ¬P n'est pas un théorème), ou bien ¬P si ¬P est cohérent avec (c'est-à-dire, si P n'est pas un théorème). En clair, l'ensemble des valeurs possibles est Consist(P) = {Q∈{P,¬P} : Peano ⊬ ¬Q}, où le symbole ‘⊬’ signifie ne démontre pas. Comme l'arithmétique de Peano est cohérente, il y a forcément l'un de P et de ¬P qui est cohérent avec Peano, donc Consist peut toujours renvoyer quelque chose (l'ensemble n'est jamais vide). Peut-être que c'est plus clair si je le dis ainsi : Consist(P) va renvoyer P si P est un théorème de l'arithmétique de Peano, ¬P si ¬P est un théorème, et l'un quelconque des deux de façon non-déterministe si P est indécidable dans l'arithmétique de Peano.

Notons de plus Halting le problème de l'arrêt (dont le degré est 0′ par définition de ce dernier).

Il est facile de voir Consist ≼ LLPO ≼ LLPO⁺ ≼ Halting (en notant ‘≼’ pour ‘≼_T2’) :

• Si on disposant de l'accès à un oracle LLPO, pour calculer Consist, donné un énoncé arithmétique P, on considère ⟨e₁,n₁⟩ qui recherche une preuve de ¬P dans l'arithmétique de Peano et ⟨e₂,n₂⟩ qui recherche une preuve de P dans l'arithmétique de Peano. L'une des deux doit forcément ne pas terminer (parce que Peano est cohérent), si bien que ⟨⟨e₁,n₁⟩, ⟨e₂,n₂⟩⟩ est une question autorisée à LLPO (il est défini dessus). Si notre oracle LLPO répond 1 (i.e., ⟨e₁,n₁⟩ ne termine pas), on renvoie P, et s'il répond 2 on renvoie ¬P.
• Il est trivial que LLPO se réduit à LLPO⁺ puisque c'est une restriction de ce dernier.
• Si on dispose de l'accès à un oracle du problème de l'arrêt, il est évident de calculer LLPO⁺ : on utilise l'oracle pour décider si ⟨e₁,n₁⟩ s'arrête et si ⟨e₂,n₂⟩ s'arrête, et on renvoie ⟨e₁,n₁⟩ sauf lorsque φ_e₁(n₁)↓ et φ_e₂(n₂)↑ auquel cas on renvoie ⟨e₂,n₂⟩.

La chose qui est un petit peu subtile, c'est que LLPO⁺ ≼ Consist (du coup, Consist ≡ LLPO ≡ LLPO⁺ comme annoncé). Pour ça, il y a une astuce due à Rosser : donnés ⟨e₁,n₁⟩ et ⟨e₂,n₂⟩, on appelle P l'énoncé l'algorithme e₂ sur n₂ s'arrête avant l'algorithme e₁ sur n₁ (c'est-à-dire précisément : il existe une trace d'exécution de e₂ sur n₂ qui a une longueur strictement plus courte que toute trace d'exécution de e₁ sur n₁). L'intérêt de cet énoncé est que si φ_e₁(n₁)↑ et φ_e₂(n₂)↓ alors P est prouvable dans Peano (il suffit d'écrire la trace d'exécution complète de φ_e₂(n₂) et le début de la trace d'exécution de φ_e₁(n₁) de cette longueur, ceci constitue une preuve de P), et symétriquement, si φ_e₁(n₁)↓ et φ_e₂(n₂)↑ alors ¬P est prouvable dans Peano (il suffit d'écrire la trace d'exécution complète de φ_e₁(n₁) et le début de la trace d'exécution de φ_e₁(n₁) de cette longueur). Donc on interroge l'oracle Consist sur l'énoncé P, et s'il répond P on renvoie ⟨e₁,n₁⟩ tandis que s'il répond ¬P on renvoie ⟨e₂,n₂⟩ : ceci constitue une implémentation de LLPO⁺.

Le fait que le degré de Consist ≡ LLPO ≡ LLPO⁺ est > 0, c'est-à-dire qu'on ne peut pas implémenter ces oracles algorithmiquement, est expliqué ici. Le fait que ce degré T2 est < 0′ est plus subtil : je le démontrerai plus bas en comparant à un degré T3 (Error_1/3), mais mentionnons que c'est, par exemple, une conséquence du théorème de la base basse (que j'ai brièvement évoqué ci-dessus en petits caractères ; cf. ici pour une discussion sur la question) : grosso modo, le théorème de la base basse assure qu'il existe une fonction d:ℕ→{0,1} (totale et déterministe) qui pour chaque P choisit P ou ¬P pour être cohérent avec Peano et même, si on veut, pour être cohérent avec les choix faits par cette même fonction (ce qui donne donc une extension cohérente et complète de l'arithmétique de Peano) et dont le degré de Turing d est bas, c'est-à-dire qu'il vérifie d′=0′, et en particulier d<0′. On a alors Consist ≼ d (précisément parce que d fait des choix de réponses valables pour Consist), et notamment, comme le degré (ordinaire, donc aussi T2) de d est <0′, il en va de même de celui de Consist. Donc le degré de Consist ≡ LLPO ≡ LLPO⁺ est strictement intermédiaire entre 0 et 0′ comme annoncé.

Mais par ailleurs, même si je n'ai pas défini le concept pour un degré T2 et je ne sais pas exactement ce qu'il devrait être, il est plausible que le degré en question mérite d'être qualifié de calculablement énumérable (on peut énumérer les ⟨⟨e₁,n₁⟩, ⟨e₂,n₂⟩⟩ pour lesquels φ_e₁(n₁)↓ ou bien φ_e₂(n₂)↓, ce qui oblige à répondre ⟨e₂,n₂⟩ ou ⟨e₁,n₁⟩ respectivement, et pour les autres, on peut faire n'importe quelle réponse). Donc on peut dire qu'au niveau T2 on a une réponse satisfaisante et naturelle au problème de Post.

Réduction des fonctions avec conseil

Pour récapituler, pour l'instant, on a défini la réduction de Turing ordinaire (celle des fonctions ℕ→ℕ totales simplement valuées), puis on a généralisé d'abord (réduction T1) aux fonctions partielles, et ensuite (réduction T2) aux fonctions partielles multivaluées, c'est-à-dire pouvant prendre plusieurs valeurs (quand vous l'appelez, la fonction vous renvoie une valeur que vous ne contrôlez pas, c'est-à-dire choisie par votre adversaire, Merlin).

Quelle est la généralisation suivante ? C'est là que je trouve ça très intéressant : on va introduire une sorte de non-déterminisme « dual » (co-non-déterminisme ? le terme est de moi), où la valeur choisie est non pas celle qui vous arrange le moins (choisie par votre adversaire, Merlin) mais celle qui vous arrange le plus (choisie par votre fée protectrice, Nimué) ! C'est un peu subtil, et il y a diverses façons de présenter la chose. Je vais décrire deux points de vue différents légèrement différents pour la même chose (ci-après, le point de vue parties et le point de vue bicouche), au risque de compliquer la présentation mais dans l'espoir de plaire à tout le monde. (Je conseille de lire une première fois en diagonale pour essayer de trouver quelle présentation semble la plus claire, et une deuxième fois plus précisément une fois qu'on a cette idée.)

La présentation la plus économique et peut-être la plus élégante est d'appeler fonction avec conseil (« point de vue parties ») une fonction (totale) g : ℕ→𝒫(𝒫(ℕ)) de l'ensemble ℕ des entiers naturels vers l'ensemble 𝒫(𝒫(ℕ)) des ensembles d'ensembles d'entiers naturels. Je vais expliquer plus précisément quel est le jeu auquel on va jouer et qui sont ses joueurs, mais pour donner déjà une idée de quoi il s'agit, si m est choisi par Arthur, alors Nimué (qui est alliée d'Arthur) choisit un élément de g(m), et Merlin (qui est adversaire d'Arthur) choisit un élément de l'élément que Nimué aura choisi (et c'est ça qu'Arthur verra). Une fonction partielle multivaluée (cas T2) g : ℕ⇢𝒫(ℕ) est identifiée à la fonction avec conseil ℕ→𝒫(𝒫(ℕ)) valant {g(m)} lorsque g(m) est défini (c'est lui-même un ensemble d'entiers naturels), et valant ∅ lorsque g(m) n'est pas défini (autrement dit, Nimué a un seul choix dans le premier cas, et aucun choix dans le second) ; en particulier, une fonction partielle simplement valuée (cas T1) g : ℕ⇢ℕ est identifiée à la fonction avec conseil ℕ→𝒫(𝒫(ℕ)) valant {{g(m)}} lorsque g(m) est défini (c'est un entier naturel), et ∅ lorsque g(m) n'est pas défini. Bref, les cas que nous avons précédemment considérés sont les cas des fonctions avec conseil où chaque élément de 𝒫(𝒫(ℕ)) pris par la fonction est de cardinal ≤1.

Un autre point de vue (« point de vue bicouche »), peut-être moins élégant mais éventuellement plus pratique et peut-être plus intuitif, sur le cas T3 qu'on cherche à définir, consiste à regarder des fonctions ℕ×Λ ⇢ 𝒫(ℕ), c'est-à-dire partielles multivaluées, mais prenant maintenant deux entrées, un entier naturel et un élément d'un ensemble Λ non spécifié dépendant de la fonction, ce deuxième élément étant appelé l'entrée secrète ou (lorsque la fonction est utilisée comme oracle) le choix de Nimué. Pour distinguer notationnellement ces deux arguments, on notera g(n|c) la valeur de la fonction sur le couple formé d'un élément n∈ℕ et c∈Λ. Avec ce point de vue, si m est choisi par Arthur, alors Nimué choisit un élément c∈Λ tel que g(m|c) soit défini, et Merlin choisit un élément de g(m|c).

J'utiliserai le terme de fonction avec conseil pour désigner l'un ou l'autre de ces deux points de vue (fonction ℕ→𝒫(𝒫(ℕ)) ou ℕ×Λ ⇢ 𝒫(ℕ)) : je vais de toute façon dire qu'ils sont équivalents et définiront les mêmes degrés T3. Si je dois les distinguer, j'ajouterai point de vue parties pour une fonction ℕ→𝒫(𝒫(ℕ)) ou point de vue bicouche pour une fonction ℕ×Λ ⇢ 𝒫(ℕ).

Je ne sais pas si ça éclaircit les choses où si ça les embrouille de donner ces deux points de vue à la fois (fonction ℕ→𝒫(𝒫(ℕ)) ou ℕ×Λ ⇢ 𝒫(ℕ)), mais en tout cas, la conversion entre les deux points de vue est la suivante : donnée une fonction avec conseil point de vue parties g : ℕ→𝒫(𝒫(ℕ)), on appelle Λ = 𝒫(ℕ), et on définit une fonction avec conseil point de vue bicouche gˆ : ℕ×Λ ⇢ 𝒫(ℕ) ainsi : si n∈ℕ et c∈Λ=𝒫(ℕ), alors la fonction gˆ est définie en (n|c) exactement lorsque c∈g(n) et dans ce cas elle vaut c ; inversement, donnée une fonction avec conseil point de vue bicouche g : ℕ×Λ ⇢ 𝒫(ℕ), on définit une fonction avec conseil point de vue parties gˇ : ℕ→𝒫(𝒫(ℕ)) ainsi : gˇ(n) est l'ensemble de toutes les valeurs g(n|c) qui sont définies lorsque c parcourt Λ. Ces opérations ne sont pas inverses l'une de l'autre (on a bien gˆˇ=g mais dans l'autre sens ce n'est pas vrai), mais pour ce qui nous concerne ce sera tout comme (la fonction gˇˆ sera T3-équivalente à g).

Avant de passer à une description plus formelle, l'idée intuitive de notre niveau T3 peut être décrite très informellement comme suit. Arthur est en train de mener un calcul algorithmique et dispose d'un oracle de nature ℕ→𝒫(𝒫(ℕ)) ou ℕ×Λ ⇢ 𝒫(ℕ) selon le point de vue par lequel on préfère le représenter : il (Arthur) va choisir une valeur m sur laquelle interroger l'oracle. L'oracle est, en quelque sorte, formé de deux personnes : Nimué, qui est l'alliée d'Arthur, et Merlin, qui est son adversaire. Nimué cherche à aider Arthur mais ne peut pas communiquer directement avec lui. Merlin cherche à l'emmerder. Dans le point de vue parties g : ℕ→𝒫(𝒫(ℕ)), Arthur choisit m pour interroger l'oracle, Nimué choisit un élément de g(m), et Merlin choisit un élément de cet élément-là (c'est donc un entier naturel) et c'est là la valeur qu'Arthur voit comme réponse de l'oracle, et avec laquelle il continue son calcul. (Si g(m) est vide, Nimué ne peut pas jouer et Arthur/Nimué a perdu ; en revanche, si l'élément de g(m) choisi par Nimué est vide, Merlin ne peut pas jouer, et Arthur a gagné.) Dans le point de vue bicouche g : ℕ×Λ ⇢ 𝒫(ℕ), Arthur choisit m pour interroger l'oracle, Nimué choisit un élément c∈Λ tel que g(m|c) soit défini, et Merlin choisit un élément de cet ensemble-là (c'est donc un entier naturel) et c'est là la valeur qu'Arthur voit comme réponse de l'oracle, et avec laquelle il continue son calcul. Dans les deux points de vue, il est crucial de noter qu'Arthur ne voit pas la valeur choisie par Nimué, il voit uniquement la valeur choisie par Merlin. (De toute façon, Arthur joue selon un algorithme donc ça n'a même pas de sens de lui permettre de voir un élément d'un ensemble Λ abstrait.)

Inversement, quand c'est Arthur (aidé de Nimué) qui doit calculer une fonction f, il faut « inverser les rôles » mais comme il y a trois rôles il faut être un peu précis sur ce qu'inverser signifie. Il se passe les choses suivantes. Dans le point de vue parties f : ℕ→𝒫(𝒫(ℕ)), Merlin choisit à la fois n (sur lequel Arthur est interrogé) et un élément de f(n), mais le premier est montré à Arthur et Nimué tandis que le second n'est montré qu'à Nimué, et le but d'Arthur est de fabriquer un élément de cet ensemble. Dans le point de vue bicouche f : ℕ×Λ ⇢ 𝒫(ℕ), Merlin choisit à la fois n∈ℕ et c∈Λ tels que f(n|c) soit défini, mais n est montré à Arthur et Nimué tandis que c n'est montré qu'à Nimué, et le but d'Arthur est de fabriquer un élément de l'ensemble f(n|c).

Bon, tout ceci était peut-être désespérément vague, donc voici une définition précise. Je vais prendre le point de vue bicouche ℕ×Λ ⇢ 𝒫(ℕ) et ensuite dire ce qu'il faut changer pour le point de vue parties ℕ→𝒫(𝒫(ℕ)).

Données deux fonctions f : ℕ×Θ ⇢ 𝒫(ℕ) et g : ℕ×Λ ⇢ 𝒫(ℕ), on dit que f est réductible à g (réductible au sens T3 s'il y a besoin de préciser, mais je pourrais aussi l'appeller réductible au sens de Turing-Kihara) lorsqu'il existe une stratégie calculable pour Arthur et une stratégie pour Nimué qui leur assurent de gagner au jeu suivant.

Le jeu : se joue entre trois joueurs, Arthur+Nimué (qui font équipe) et Merlin (leur adversaire) : Arthur voit uniquement les coups qui seront indiqués visibles ci-dessous, tandis que Nimué et Merlin voient tous les coups passés ; les coups se font dans l'ordre suivant : Merlin, Arthur, Nimué, Merlin, Arthur, Nimué, etc.

• au premier tour, Merlin joue un élément n∈ℕ, qui sera visible d'Arthur, et un élément d∈Θ qui ne sera pas visible d'Arthur ; Merlin perd dès le premier tour (i.e., Arthur+Nimué gagnent) si f(n|d) n'est pas défini ;
• à chaque tour suivant, Arthur a deux types de coups possibles : il peut soit « déclarer la fin du calcul » avec une valeur k∈ℕ, soit « lancer une interrogation de l'oracle » avec une valeur m∈ℕ ;
• lorsque Arthur déclare la fin du calcul avec une valeur k, le jeu prend fin ; Arthur+Nimué gagnent si k ∈ f(n|d), sinon Merlin gagne ;
• lorsque Arthur lance une interrogation de l'oracle avec une valeur m :
  • Nimué joue ensuite un élément c∈Λ, qui ne sera pas visible d'Arthur ; Arthur+Nimué perdent à ce stade (i.e., Merlin gagne) si g(m|c) n'est pas défini, sinon le jeu continue ;
  • puis Merlin joue un élément ℓ∈ℕ, qui sera visible d'Arthur ; Merlin perd à ce stade (i.e., Arthur+Nimué gagnent) si ℓ∉g(m|c), sinon le jeu continue (avec un coup d'Arthur).

Le jeu prend fin dès qu'un des joueurs a gagné, c'est-à-dire soit lorsque Arthur a déclaré la fin du calcul soit lorsqu'un des joueurs a violé une contrainte sur le coup. Si le jeu dure indéfiniment (Arthur ne déclare jamais la fin du calcul), alors Arthur+Nimué ont perdu (i.e., Merlin a gagné).

Arthur (simple mortel !) joue selon une stratégie calculable, c'est-à-dire qu'on exige qu'il existe une fonction calculable qui, données toutes les informations dont il dispose à ce stade (et qui sont toutes des entiers naturels) renvoie le coup qu'il joue. Nimué et Merlin, en revanche, ne sont pas ainsi limités : la condition de réduction est donc qu'il existe une stratégie calculable pour Arthur et une stratégie pour Nimué telles que pour toute stratégie de Merlin, Arthur+Nimué gagnent au jeu qui vient d'être décrit.

Pour ce qui est du point de vue parties ℕ→𝒫(𝒫(ℕ)), données deux fonctions f : ℕ→𝒫(𝒫(ℕ)) et g : ℕ→𝒫(𝒫(ℕ)), on dit que f est réductible à g (réductible au sens T3, je ne ferai pas de différence avec la notion précédente, parce que c'est vraiment interconvertible) lorsqu'il existe une stratégie calculable pour Arthur et une stratégie pour Nimué qui leur assurent de gagner au jeu suivant.

Le jeu ne comporte que de petites variations par rapport à la description précédente.

• au premier tour, Merlin joue un élément n∈ℕ, qui sera visible d'Arthur, et un élément D∈𝒫(ℕ) qui ne sera pas visible d'Arthur ; Merlin perd dès le premier tour (i.e., Arthur+Nimué gagnent) si D∉f(n) ;
• à chaque tour suivant, Arthur a deux types de coups possibles : il peut soit « déclarer la fin du calcul » avec une valeur k∈ℕ, soit « lancer une interrogation de l'oracle » avec une valeur m∈ℕ ;
• lorsque Arthur déclare la fin du calcul avec une valeur k, le jeu prend fin ; Arthur+Nimué gagnent si k ∈ D, sinon Merlin gagne ;
• lorsque Arthur lance une interrogation de l'oracle avec une valeur m :
  • Nimué joue ensuite un élément C∈𝒫(ℕ), qui ne sera pas visible d'Arthur ; Arthur+Nimué perdent à ce stade (i.e., Merlin gagne) si C∉g(m) n'est pas défini, sinon le jeu continue ;
  • puis Merlin joue un élément ℓ∈ℕ, qui sera visible d'Arthur ; Merlin perd à ce stade (i.e., Arthur+Nimué gagnent) si ℓ∉C, sinon le jeu continue (avec un coup d'Arthur).

Les autres remarques s'appliquent à l'identique.

Quel que soit le point de vue que l'on choisit, la relation de réduction qu'on vient de définir, et qu'on notera f ≼_T3 g est, comme dans les cas précédents (réduction de Turing ordinaire, T1 et T2) un préordre. C'est un tout petit peu plus compliqué à voir que dans les cas précédents parce qu'on a un jeu à trois joueurs, mais il n'y a pas de difficulté majeure (en gros : si on suppose f ≼_T3 g et g ≼_T3 h et qu'on veut prouver f ≼_T3 h, Arthur et Nimué appliquent chacun la stratégie qui montre que f ≼_T3 g sauf que, à chaque fois que celle-ci préconise à Arthur de lancer une interrogation de l'oracle, celle-ci est remplacée par une application des stratégies qui montrent g ≼_T3 h en faisant semblant que Merlin a fait le coup que les stratégies précédentes auraient préconisé pour Arthur et Nimué).

Lorsque f et g sont « sans conseil » (i.e., que Nimué n'a aucun choix à faire, c'est-à-dire, dans le point de vue parties ℕ→𝒫(𝒫(ℕ)), que leurs valeurs sont soit ∅ soit un singleton, ou, dans le point de vue bicouche ℕ×Λ ⇢ 𝒫(ℕ) que Λ est un singleton), il s'agit du même préordre T2 qu'on a déjà défini (et qui généralise lui-même la réduction T1 et la réduction de Turing ordinaire). De nouveau, on peut définir une relation d'équivalence f ≡_T3 g lorsque f ≼_T3 g et g ≼_T3 f (et je répète que, lorsque f et g sont « sans conseil », les relations f ≡_T2 g et f ≡_T3 g sont équivalentes).

On a donc de nouveau un ensemble de degrés, qu'on peut appeler les degrés T3, ou degrés de Turing des fonctions avec conseil.

Comme précédemment, vu que f ≡_T2 g et f ≡_T3 g sont équivalentes lorsque f et g sont « sans conseil », on obtient une injection [f]_T2 ↦ [f]_T3 des degrés T2 dans les degrés T3 en envoyant la classe d'équivalence pour ‘≡_T2’ de f vers la classe d'équivalence pour ‘≡_T3’ de cette même fonction. Ceci permet de considérer, et on le fera toujours, les degrés T2 (et a fortiori les degrés de Turing ordinaires et T1) et comme un sous-ensemble des degrés T3. On va maintenant dire un mot des degrés « basiques » qui sont une sorte de supplémentaire des degrés T2 dans les degrés T3.

Les degrés « basiques », les fonctions Error_1/ℓ

La notion de degré T3 est sans doute plus délicate à visualiser intuitivement que celle de degré de Turing ordinaire, T1 ou T2. Quelques commentaires et exemples sont sans doute bienvenus.

La première chose à comprendre, c'est que Nimué est extrêmement puissante : le point crucial des règles du jeu définies ci-dessus est qu'elles ne permettent pas à Nimué de communiquer directement en direction d'Arthur (je vais dire ci-dessous que si elle le peut, on peut tout calculer), elle peut juste restreindre les coups de Merlin pour aider Arthur.

Si Nimué ne joue pas (i.e., si elle n'a pas de choix), on obtient exactement les degrés T2 définis précédemment (et si Merlin lui non plus n'a pas de choix, on obtient les degrés T1, peut-être avec une petite discussion sur ce que pas de choix signifie exactement entre ≤1 option ou =1 option, mais ne pinaillons pas ici).

Mais on peut aussi considérer la situation symétrique où c'est Arthur qui ne joue pas (disons, par exemple, que le nombre qu'il joue est ignoré, ou bien que s'il est ≠0 alors Nimué n'a aucun coup ce qui force Arthur à jouer 0). On parlera d'oracle basique pour cette situation : un oracle basique est donc juste un élément de 𝒫(𝒫(ℕ)), ou une fonction Λ ⇢ 𝒫(ℕ), selon le point de vue qu'on préfère (parties ou bicouche : je rappelle que l'élément de 𝒫(𝒫(ℕ)) donné par le point de vue parties est juste l'image de la fonction Λ ⇢ 𝒫(ℕ) du point de vue bicouche) ; et on parlera de degré basique pour le degré T3 d'une telle fonction.

Commençons par examiner la situation la plus simple qui ne soit pas triviale : l'oracle basique, appelons-le provisoirement q (plus bas il sera aussi nommé Error_½), donné par {{0},{1}} ∈ 𝒫(𝒫(ℕ)), ou, dans le point de vue bicouche, la fonction {0,1} ⇢ 𝒫(ℕ) donnée par 0↦{0}, 1↦{1}. Autrement dit : Arthur n'a pa de choix à faire (c'est un oracle basique), Nimué a le choix entre deux options que nous avons notées “0” et “1”, et Merlin n'a pas de choix derrière, il doit juste reprendre la valeur choisie par Nimué parmi 0 et 1 ; concrètement, cet oracle consiste donc pour Nimué à communiquer un bit à Arthur, en forçant Merlin à le lui donner. (Enfin, un bit par appel de l'oracle !, mais comme les appels à l'oracle sont illimités, on devine bien que ça va être très puissant.) On peut se convaincre que toute fonction partielle f:ℕ⇢ℕ est réductible à l'oracle q en question (i.e., f ≼_T3 q) : en effet, voici une stratégie possible d'Arthur et Nimué : en réponse à un coup n∈ℕ de Merlin, Nimué calcule f(n)∈ℕ et, au k-ième coup (compté à partir de 0), elle répond 1 si f(n)=k et 0 sinon ; Arthur va donc interroger l'oracle de façon répétée jusqu'à ce que l'oracle réponde 1, et si ça se produit à la k-ième interrogation (comptée à partir de 0), il déclare la fin du calcul avec la valeur en question ; clairement, cette stratégie est calculable, et gagnante pour Arthur+Nimué, prouvant que f ≼_T3 q lorsque f est une fonction partielle ; le même argument fonctionne pour une fonction non-déterministe ℕ⇢𝒫(ℕ), tant que celle-ci ne prend pas la valeur ∅. Encore plus généralement, le même argument montre que pour toute fonction f : ℕ×Θ ⇢ 𝒫(ℕ) on a f ≼_T3 q dès lors que f(n|d)≠∅ pour tout n∈ℕ et tout d∈Θ (si on préfère le point de vue parties ℕ→𝒫(𝒫(ℕ)), on a f ≼_T3 q dès lors que tous les éléments de f(n) sont non vides) : en effet, donnés n∈ℕ et d∈Θ, Nimué va utiliser q pour communiquer à Arthur, disons, la valeur du plus petit élément de f(n|d), ce qui constitue une stratégie gagnante pour eux deux.

J'appellerai degré omniscient, et je noterai ॐ (oui, c'est une blague, mais je ne sais pas quel symbole utiliser) le degré T3 de l'oracle (q ou Error_½) défini au paragraphe précédent, c'est-à-dire celui permettant à Nimué de communiquer directement un bit à Arthur. En fait, en gros, dès que Nimué peut communiquer avec Arthur, on tombe sur ce degré ॐ (notamment, si un oracle basique, dans le point de vue parties, c'est-à-dire élément de 𝒫(𝒫(ℕ)), contient deux parties disjointes et calculables — ou même simplement disjointes et calculablement énumérables, ou même simplement calculablement séparables — alors son degré est ॐ, parce que Nimué va pouvoir jouer l'une de ces parties pour communiquer un bit à Arthur et Arthur saura décoder la réponse de Merlin pour savoir ce que Nimué cherche à lui dire). Comme montré au paragraphe précédent, ce degré omniscient ॐ majore tout degré T3 à la seule exception du plus grand de tous. Ce dernier (le plus grand degré T3) sera appelé degré omnipotent, c'est le degré d'une fonction met Merlin en échec (par exemple, représenté par l'oracle basique {∅}∈𝒫(𝒫(ℕ)) dans le point de vue parties : Nimué joue ∅ et Merlin ne peut pas répondre, donc Arthur+Nimué ont gagné). Je noterai ⊤ pour ce degré omnipotent, qui est, je répète, le seul strictement plus grand que ॐ (et encore moins intéressant que lui).

(Les notations sont assez pourries, j'en conviens. Déjà, ça n'aide pas qu'on veuille parfois parler des fonctions, parfois de leur degré. Il est standard de noter 0 pour le plus petit degré — celui des fonctions calculables — comme degré de Turing ordinaire, donc comme degré T1, T2 ou T3. Pour les degrés de Turing ordinaires ou les degrés T1, il n'y a pas de plus grand degré. Dans les degrés T2 et T3 apparaît ce plus grand degré, que je note ⊤ parce que c'est une notation standard pour le plus grand élément d'un treillis. Mais comment noter le deuxième plus grand élément ? J'ai écrit ॐ parce que c'est une blague sur OMniscient, mais aussi parce que c'est sûr que ce symbole n'est pas utilisé ailleurs en maths. Il peut être légitime de le noter ¬¬ parce qu'il correspondra à la topologie du non-non au sens de Lawvere-Tierney, mais je pense que ce serait confusant de le noter ainsi à ce stade. C'est le degré de la fonction Error_½ introduite ci-dessous, mais c'est un petit peu long pour un objet aussi fondamental.)

J'ai défini le degré omniscient ॐ par l'oracle basique {{0},{1}} ∈ 𝒫(𝒫(ℕ)) qui permet à Nimué de communiquer un bit à Arthur. Plus généralement, on peut considérer l'oracle basique suivant : Error_m/k est défini comme l'ensemble des parties à k−m éléments de {0,…,k−1}, c'est-à-dire qu'on peut voir l'utilisation de cet oracle de la manière suivant : parmi k possibilités, Nimué en exclut secrètement m, et Merlin montre une des k−m restantes à Arthur. (Si on préfère le point de vue bicouche, il peut être préférable d'appeler Λ l'ensemble des parties à m éléments de {0,…,k−1}, et alors Error_m/k : ℕ×Λ ⇢ 𝒫(ℕ) renvoie le complémentaire de son deuxième argument dans {0,…,k−1}.) Le cas précédemment considéré était Error_½ (qui définit, je répète, le degré omniscient ॐ qui est le plus grand après le degré omnipotent).

Du point de vue calculatoire, on peut dire que Error_m/k est un gadget qui vous permet de lancer k fils d'exécution en parallèle, dont (au plus) m d'entre eux ont le droit de se tromper : si au moins k−m donnent un bon résultat, vous avez réussi votre calcul.

La question de si Error_m′/k′ ≼_T3 Error_m/k peut être tournée de façon un peu ludique comme suit : un aventurier (Arthur) est dans un donjon, il est face à k′ portes identiques dont m′ conduisent à la mort, mais il ignore lesquelles. Son but est d'ouvrir une porte non-mortelle. Son ange gardien (Nimué, qui connaît notamment les bonnes et mauvaises portes) peut l'aider dans cette tâche, mais Nimué ne peut pas communiquer directement d'information à Arthur : tout ce qu'elle peut faire c'est, parmi un ensemble de m possibilités (choisies par Arthur), en exclure k, après quoi Merlin (le concepteur du donjon, qui cherche à nuire à Arthur) va en sélectionner une et la communiquer à Arthur. L'énigme que j'avais posée à la fin du billet précédent était le cas (k,m,k′,m′) = (5,2,3,1), c'est-à-dire, sous une formulation un peu différente, demandait de montrer Error_1/3 ≼_T3 Error_2/5 (sachant que Error_2/5 ≼_T3 Error_1/3 est évident, donc, en fait, on a Error_1/3 ≡_T3 Error_2/5).

Kihara donne, en fait (en adaptant la preuve d'un article de Cenzer et Hinman dans un contexte un petit peu différent), le rapport précis entre les degrés T3 des oracles Error_m/k : il montre que Error_m/k ≡_T3 Error_1/ℓ où ℓ := ⌈k/m⌉, la notation ⌈z⌉ désignant la partie entière supérieure de z (c'est-à-dire le plus petit entier supérieur ou égal à z), et que les Error_1/ℓ sont de degrés distincts (or est évident que Error_1/ℓ′ ≼_T3 Error_1/ℓ si ℓ′ ≤ ℓ). Bref, finalement, Error_m′/k′ ≼_T3 Error_m/k se produit si et seulement si ⌈k′/m′⌉ ≤ ⌈k/m⌉.

Ce résultat est peut-être un peu décevant au sens où on pouvait espérer une structure plus riche et plus complexe. On peut se demander s'il existe des degrés T3 de nature complètement « combinatoire » (disons, des oracles basiques définies par un élément de 𝒫_fin(𝒫_fin(ℕ)) où 𝒫_fin désigne l'ensemble des parties finies, c'est-à-dire que Nimué et Merlin ont chacun un nombre fini de choix) autres que ceux des Error_1/ℓ : je ne sais pas quelle est la réponse.

(Je me suis notamment demandé quel était le degré de l'oracle suivant : parmi les k éléments {0,…,k−1}, Nimué en exclut secrètement p, et Merlin montre q parmi les des k−p restants à Arthur. Mais en fait, il est assez facile de voir que c'est le même que Error_p/(k−q+1), donc finalement Error_{1/⌈(k−q+1)/p⌉} : donc la généralité supplémentaire donnée par q n'apporte en fait rien de nouveau.)

Comme je l'ai expliqué ci-dessus, Error_½ est du degré omniscient ॐ, donc permet d'implémenter n'importe quelle fonction ℕ⇢ℕ. D'après ce que j'ai dit, le plus puissant des Error_m/k après Error_½ est Error_1/3. Celui-ci n'apporte rien quand il s'agit de calculer une fonction déterministe ℕ⇢ℕ. En effet :

Proposition : si f:ℕ⇢ℕ (déterministe !) est telle que f ≼_T3 Error_1/3 (et, en particulier, si f ≼_T3 Error_1/ℓ pour ℓ≥3) alors f est, en fait, calculable. Autrement dit l'ensemble des degrés T1 majorés par le degré T3 de Error_1/3 est réduit à {0}.

(Je fais la preuve de façon un peu précise parce que Kihara ne l'écrit pas. Voir le paragraphe suivant si on en veut juste un résumé.)

Preuve. Considérons une stratégie σ (calculable !) d'Arthur témoignant du fait que f ≼_T3 Error_1/3. On souhaite implémenter f algorithmiquement (sans oracle). Donnée une entrée n∈ℕ, considérons l'arbre ternaire 𝒯 suivant : Arthur joue selon σ en supposant que Merlin a joué n au coup initial, et, à chaque fois que (selon cette stratégie σ) Arthur fait appel à l'oracle, on crée un nœud dans l'arbre avec trois descendants en imaginant que la réponse de Merlin (visible d'Arthur) vaut 0, 1 ou 2, en continuant la construction de chaque sous-arbre d'après la réponse que σ préconise pour Arthur à ce coup de Merlin ; en revanche, si (toujours selon σ) Arthur déclare la fin du calcul avec une valeur v, on arrête la construction du sous-arbre en créant une feuille étiquetée par v. (Notons qu'il est possible que certains bouts de la construction de l'arbre ne terminent jamais, parce que certains coups de Merlin auraient été écartés par Nimué, mais comme on ignore les coups de Nimué on ne peut pas le savoir. Ce n'est pas grave.) L'hypothèse que σ est gagnante signifie qu'il y a un sous-arbre binaire 𝒯₂ de l'arbre 𝒯 que nous avons construit (sous-arbre correspondant à l'élimination d'une branche par Nimué à chaque nœud) qui soit fini et terminé par des feuilles étiquetées toutes par la même valeur f(n) — c'est là qu'on utilise le fait que f est déterministe. Ne voyant pas les coups de Nimué, on ne sait pas quel est ce sous-arbre 𝒯₂, mais on peut quand même calculer f(n) selon l'algorithme suivant : on lance la construction algorithmique de l'arbre 𝒯 qu'on vient de décrire (en simulant en parallèle toutes les branches possibles du calcul ; tout ceci est possible algorithmiquement car σ est calculable) et, dès qu'un nœud a deux de ses trois fils étiquetés par la même valeur, on étiquette ce nœud lui-même par cette valeur (et on arrête l'exécution de l'éventuel troisième sous-arbre). Par l'existence du sous-arbre binaire 𝒯₂ qui a été décrit, la racine de 𝒯 va finir par être étiquetée par une certaine valeur, et ceci est la valeur de f(n) recherchée. ∎

Résumé de la démonstration : on lance en parallèle tous les fils de calcul possibles en simulant les réponses de l'oracle Error_1/3 et, comme à chaque appel, il y a deux des trois fils qui doivent terminer avec la même réponse, on peut se considérer comme satisfait à ce point.

En particulier, le problème de l'arrêt ne se réduit pas à Error_1/3. En revanche, si on a lu la section plus haut sur le degré intermédiaire (Consist ≡ LLPO ≡ LLPO⁺) entre 0 et le degré du problème de l'arrêt, il est intéressant de noter que ce degré-là se réduit bien à Error_1/3 (en effet, mettons que je veuille réduire Consist à Error_1/3 : donné un énoncé P, je demande à Error_1/3 d'éliminer une des trois possibilités : ① P est un théorème, ② ¬P est un théorème, ou bien ③ P n'est ni l'un ni l'autre, i.e., est indécidable : si l'oracle élimine ① je réponds que ¬P est cohérent, si l'oracle élimine ② je réponds que P est cohérent, et si l'oracle élimine ③, je recherche en parallèle une démonstration de P et de ¬P avec la certitude que l'une des deux va terminer, et je renvoie l'énoncé en question). Ceci montre en particulier que le problème de l'arrêt ne se réduit pas à Consist ≡ LLPO ≡ LLPO⁺ puisque ces derniers se réduisent à Error_1/3 et que ce n'est pas le cas du problème de l'arrêt d'après la proposition précédente.

La proposition ci-dessus affirme que Error_1/3 ne présente aucun intérêt pour calculer une fonction déterministe (niveau T1). Mais inversement, Error_1/3 n'est pas non plus calculable par une fonction de niveau T1 (déterministe partielle ℕ⇢ℕ) ou même T2 (non-déterministe ℕ⇢𝒫(ℕ), en supposant bien sûr que cette dernière ne prend jamais la valeur ∅) : il n'existe pas de telle g tel que Error_1/3 ≼_T3 g. C'est facile à montrer, mais je pense que ça vaut la peine de faire l'exercice pour comprendre le sens qu'a cette affirmation : une telle réduction pour g déterministe voudrait dire qu'Arthur arriverait à éviter de façon certaine une valeur d∈{0,1,2} que Merlin lui a cachée, or Arthur ne peut pas voir d, et le fait d'avoir accès à une fonction g qui n'a aucun rapport avec le schmilblick ne l'aide pas à éviter d : il devra de toute façon renvoyer une valeur indépendante de d, et Merlin peut mettre en échec sa stratégie en choisissant justement cette valeur pour d ; et même si g n'est pas déterministe, ça n'aide pas Arthur, parce que si on avait Error_1/3 ≼_T3 g avec g non-déterministe alors on aurait à plus forte raison Error_1/3 ≼_T3 g₀ en appelant g₀ une fonction déterministe quelconque qui choisit une valeur particulière pour chaque ensemble de valeurs de g (que je rappelle que j'ai supposé ≠∅, parce que sinon la fonction est de degré ⊤, c'est-à-dire qu'Arthur gagne pour une raison idiote à savoir que Merlin ne peut pas jouer).

Plus généralement, un argument combinant les idées simples du paragraphe précédent avec celles de la démonstration de la proposition précédente (pour les détails, voir la preuve de la proposition 4.6 dans Lawvere-Tierney topologies for computability theorists) montre que Error_1/ℓ n'est pas réductible à la borne supérieure entre Error_1/(ℓ+1) et une fonction non-déterministe g quelconque (supposée bien sûr avoir un ensemble ≠∅ de valeurs, comme ci-dessus). Je vais y revenir, mais comme dans les cas des degrés de Turing ordinaires, T1 et T2, la borne supérieure signifie en pratique qu'on a librement accès aux deux oracles considérés. Donc, concrètement, le fait d'avoir accès à Error_1/(ℓ+1) et à g fonction non-déterministe quelconque ne permet pas d'implémenter Error_1/ℓ.

L'oracle de Pitts

J'ai introduit ci-dessus l'oracle basique Error_1/ℓ qui permet à Arthur de demander d'écarter une possibilité parmi ℓ. Plus ℓ est grand, moins cet oracle est puissant. Je peux aussi mentionner Error_1/ℕ qui est défini par l'élément 𝒫(𝒫(ℕ)) donné par l'ensemble des complémentaires de tous les singletons, i.e., Arthur demande à l'oracle d'éliminer un entier naturel : cet Error_1/ℕ est intéressant parce qu'on peut montrer que son degré est le plus petit degré basique qui soit >0 (pour la preuve, voir Basic Subtoposes of the Effective Topos, proposition 5.5). Comme je l'ai montré plus haut, à part Error_½ qui confère l'omniscience, aucun de ces oracles ne présente le moindre intérêt pour calculer une fonction déterministe.

On peut être tenté de penser que, plus généralement, aucun oracle basique ne présente d'intérêt pour calculer une fonction déterministe (niveau T1) sauf à être carrément omniscient. Il n'en est rien ! L'exemple qui suit montre qu'on peut avoir un oracle basique qui soit très puissant pour calculer les fonctions déterministes sans pour autant être omniscient.

L'oracle de Pitts est l'oracle basique Cofinite défini par l'élément de 𝒫(𝒫(ℕ)) donné par l'ensemble {{ℓ∈ℕ : ℓ≥c} : c∈ℕ} des demi-droites {ℓ∈ℕ : ℓ≥c} (dans le point de vue bicouche, c'est la fonction ℕ ⇢ 𝒫(ℕ) qui à c associe la demi-droite {ℓ∈ℕ : ℓ≥c}). Autrement dit : quand Arthur fait appel à cet oracle Cofinite, Nimué choisit un entier c∈ℕ, et Merlin montre à Arthur un entier ℓ≥c. Pourquoi cet oracle est-il très puissant ?

Pour l'illustrer (et montrer comment on se sert de Cofinite), expliquons pourquoi le problème de l'arrêt Halting est (T3-)réductible à Cofinite. Pour montrer Halting ≼_T3 Cofinite, on doit donner une stratégie d'Arthur+Nimué (calculable de la part d'Arthur) permettant à Arthur d'annoncer, donné ⟨e,n⟩ choisi par Merlin, si φ_e(n)↓. La stratégie de Nimué est la suivante : donnés ⟨e,n⟩, elle regarde si φ_e(n)↓ (rappelons que Nimué peut jouer n'importe quelle stratégie, elle n'est pas tenue par une quelconque exigence de calculabilité) : si c'est le cas, elle joue pour c le nombre d'étapes d'exécution du calcul avant terminaison, tandis que si ce n'est pas le cas elle joue 0. La stratégie d'Arthur est la suivante : il prend note des valeurs ⟨e,n⟩ jouées par Merlin au premier coup, et il commence par interroger l'oracle (c'est un oracle basique, donc il n'a rien à dire) : Merlin lui renvoie une valeur ℓ qui, par définition de Cofinite, est supérieure ou égale à la valeur c jouée par Nimué (et qu'Arthur ne peut pas voir) ; Arthur lance alors l'exécution de φ_e(n) pour ℓ étapes : si le calcul est fini après ce nombre d'étapes, alors Arthur répond que φ_e(n) termine (i.e., il déclare la fin du calcul avec la valeur de retour 1), tandis que si l'exécution n'a pas fini, il répond que φ_e(n) ne termine pas. Il est clair que cette stratégie fonctionne : tout ce dont Arthur a besoin pour savoir si φ_e(n)↓, c'est un majorant du nombre d'étapes sur lequel l'exécuter pour décider si le calcul termine, et c'est ce que Nimué lui fournit, via Merlin : tout ce que Merlin peut faire, c'est augmenter ce majorant, donc forcer Arthur à faire des calculs inutiles, mais sans impacter la justesse du résultat final. Ceci montre bien que Halting ≼_T3 Cofinite, i.e., le degré T3 de Cofinite vaut au moins 0′.

Mais il n'y a pas de raison de s'arrêter là : puisque Arthur peut effectivement utiliser Cofinite pour simuler une machine de Turing ayant accès à l'oracle de l'arrêt, on peut refaire le même argument sur ce type de machines (en comptant la consultation de l'oracle comme une seule « étape » : Nimué ne peut pas savoir combien ça en prendra vraiment à simuler parce que ça dépend du coup de Merlin, mais ce n'est pas important), et ceci montre que le degré T3 de Cofinite vaut au moins 0′′, et en refaisant ce raisonnement, 0′′′ « et ainsi de suite ». Bien sûr, le ainsi de suite finit par s'arrêter, mais l'analyse de comment il s'arrête exactement dépasse le cadre de ce billet de blog : disons juste que les fonctions calculables (totales, déterministes) ℕ→ℕ calculables avec Cofinite (c'est-à-dire, réductibles à lui) sont les fonctions dites hyperarithmétiques, un concept que j'avais tenté d'expliquer il y a quelques années. Mais peut-être que la présentation en question (les fonctions calculables au moyen de l'oracle de Pitts) est en fait la façon la meilleure ou la plus élégante d'expliquer ce qu'est une fonction hyperarithmétique !

Les oracles Error_1/ℓ (pour ℓ≥3 fixé) et Cofinite ne sont pas comparables : d'un côté, Cofinite n'est certainement pas réductible à Error_1/3 (et a foriori Error_1/ℓ pour ℓ≥3) car on a vu que Error_1/3 ne permet pas de calculer le problème de l'arrêt ; de l'autre côté (en considérant un analogue de LLPO pour les machines hyperarithmétiques, cf. le corollaire 5.13 dans Lawvere-Tierney topologies for computability theorists) on peut montrer que Error_1/ℓ n'est pas non plus réductible à Cofinite. Ceci montre qu'il existe au moins deux degrés basiques incomparables.

Kihara définit encore d'autres oracles basiques, par exemple celui qu'il note DenError_ε pour ε≥0, et qui peut se décrire brièvement ainsi : Nimué choisit une partie de ℕ de densité asymptotique inférieure ≥ 1−ε, et Merlin choisit un entier dans cette partie (donc même pour ε, qui est le plus faible de tous, c'est déjà au moins aussi fort que l'oracle de Pitts Cofinite). Mais je pense que j'en ai ai assez dit, donc je m'arrête ici.

Bornes sup et inf binaires sur les degrés T3

Comme pour les degrés de Turing ordinaires, T1 et T2, la borne supérieure de deux degrés T3 ne pose pas de problème : données deux fonctions avec conseil a et b, on en définit une qui consiste à permettre à Arthur de choisir s'il veut interroger a ou b (dans le point de vue parties ℕ→𝒫(𝒫(ℕ)), on posera simplement c(⟨0,m⟩)=a(m) et c(⟨1,m⟩)=b(m), et, disons, c(n)=∅ pour toute autre valeur ; dans le point de vue bicouche ℕ×Λ ⇢ 𝒫(ℕ), on peut d'abord passer à un Λ commun et ensuite définir c(⟨0,m⟩|c) = a(m|c) lorsque celle-ci est définie et c(⟨1,m⟩|c) = b(m|c) lorsque celle-ci est définie, et toute autre valeur indéfinie). Ceci définit bien la borne supérieure des degrés comme on l'attend, et il n'y a pas de surprise particulière ; l'opération de borne supérieure binaire est la même entre les degrés de Turing ordinaires, T1, T2 et T3.

Pour la borne inférieure, la même construction que pour les degrés T2 (qui est elle-même une variation de celle pour les degrés T1) va fonctionner, mais elle mérite un petit peu plus de soin dans l'exposition.

Je rappelle que, pour une fonction g : ℕ⇢ℕ (partielle déterministe, c'est-à-dire du niveau T1), j'ai défini plus haut une fonction ⌘g : ℕ⇢ℕ (ma notation !) qui consiste à faire tourner la machine de Turing universelle ayant accès à g comme oracle ; cette fonction est de même degré T1, mais la construction a un certain nombre d'intérêts, notamment de permettre de définir la borne inférieure des degrés T1 (je rappelle : c(⟨m₁,m₂⟩) est égale à la valeur commune de ⌘a(m₁) et de ⌘b(m₂) si ces deux valeurs sont toutes les deux définies et sont égales, et n'est pas définie sinon). Au niveau T2, la construction ⌘g fonctionne en gros pareil (elle va renvoyer de façon non-déterministe une valeur possible renvoyée par le plan d'exécution passé en argument, selon les différentes valeurs possibles de g à chaque appel — bref, « ce qu'on attend » de l'exécution d'une machine faisant appel à un oracle non-déterministe).

Mais si g est une fonction avec conseil, quel sens donner à ⌘g (Kihara note ça g^⅁) ? Ici, le point de vue bicouche sera plus agréable, donc supposons donnée g : ℕ×Λ ⇢ 𝒫(ℕ), et on veut définir une fonction ⌘g : ℕ×Λ′ ⇢ 𝒫(ℕ).

Pour la définir, on va considérer le jeu (explicité plus haut) qui a servi à définir la notion de réduction f ≼_T3 g, à une petite modification près : il n'y a pas de fonction f dans la variante considérée maintenant ; du coup, au premier coup, Merlin peut jouer n'importe quel (n|d) (il n'y a pas de contrainte que f(n|d) soit définie puisque la fonction f n'existe pas), et, quand Arthur déclare la fin du calcul avec une valeur k, il a gagné (il n'y a pas la contrainte que k ∈ f(n|d)), et cette valeur k sera appelée la sortie du jeu (i.e., de la partie considérée). (Si on préfère, il revient au même de considérer le jeu d'origine pour la fonction f qui prend toutes les valeurs entières en toute valeur. Manifestement, Arthur a toujours une stratégie gagnante au jeu ainsi modifié puisqu'il peut juste immédiatement déclarer la fin du calcul avec la valeur 42.)

Bref, les entrées de la fonction ⌘g seront les suivantes : (⟨e,n⟩ | (σ,d)) où :

• e est le code d'une stratégie calculable d'Arthur, c'est-à-dire un programme qui prend en entrée (le codage de) la liste des coups antérieurs visibles par Arthur, et qui renvoie un coup d'Arthur en réponse (si le programme ne termine pas, bien sûr, Arthur est considéré comme ayant perdu par forfait) ;
• n est un entier naturel qui sera la partie visible du premier coup joué par Merlin (ce paramètre ne sert à rien, on aurait pu décider que Merlin ne joue pas initialement, ou joue forcément 0, ou quelque chose comme ça, mais je l'inclus par cohérence avec le fait que mes machines universelles prennent le codage d'un couple ⟨e,n⟩ en entrée : si ce n vous embrouille, oubliez-le) ;
• σ est une stratégie de Nimué, c'est-à-dire une fonction (pas forcément calculable !) qui, en fonction de la liste de tous les coups antérieurs, et qui renvoie un coup de Nimué en réponse ;
• d est un élément d'un certain ensemble Θ qui sera la partie secrète du premier coup joué par Merlin (ce paramètre ne sert à rien non plus, il est juste là pour la cohérence des définitions, et on me pardonnera d'ignorer le petit tracas que Θ devrait être explicité dans la notation ⌘g : ça n'aura aucune importance ; comme pour n, si ce d vous embrouille, oubliez-le).

La fonction ⌘g est définie en (⟨e,n⟩ | (σ,d)) lorsque Arthur+Nimué gagnent le jeu (modifié !, c'est-à-dire sans fonction f) en jouant selon e et σ dès que Merlin commence par jouer (n|d), autrement dit, quels que soient les coups de Merlin après le premier coup (n|d), si Arthur joue selon e et Nimué joue selon σ, alors Arthur+Nimué gagnent (au jeu modifié !), c'est-à-dire qu'Arthur finit par déclarer la fin du calcul. Lorsque c'est le cas, l'ensemble des valeurs de ⌘g est l'ensemble de toutes les sorties possibles du jeu (c'est-à-dire, en considérant tous les coups possibles de Merlin).

Si on n'aime pas les paramètres n et d, on peut les supprimer et décider que dans le jeu modifié, Merlin ne joue pas son premier tour (le jeu commence avec alors un coup d'Arthur). J'ai mis n et d dans l'histoire surtout pour éviter d'avoir à changer le jeu plus que nécessaire, et pour pouvoir faire l'affirmation assez simple qui se situe deux paragraphes plus bas.

Bref, l'idée est toujours la même : ⌘g prend en argument un « plan d'interrogation de l'oracle », mais cette fois le plan d'interrogation, au lieu de concerner le seul Arthur, implique aussi Nimué, c'est-à-dire qu'il s'agit d'une stratégie pour chacun des deux, avec les contraintes le concernant (et, pour des raisons de cohérence avec ce qui précède, j'ai aussi inclus un coup initial de Merlin, mais je répète que ce n'est pas ce qui est important dans l'histoire).

Pour qu'il n'y ait pas de doute que les définitions sont cohérentes entre elles, la réduction f ≼_T3 g définie plus haut signifie exactement, et par définition, qu'il existe e et σ tels que pour tout (n|d) du domaine de définition de f on ait ⌘g(⟨e,n⟩|(σ,d)) défini et ⊆ f(n|d).

Comme dans le cas T1 ou T2, on a g ≡_T3 ⌘g : le fait que g ≼_T3 ⌘g est évident (Arthur et Nimué construisent chacun la stratégie consistant à lancer une unique interrogation de l'oracle sur la valeur en laquelle ils cherchent à évaluer g, et soumettent cette stratégie à ⌘g). Mais pour voir que ⌘g ≼_T3 g, en fait, c'est évident aussi : dans le jeu de réduction, la définition de ⌘g fait que Merlin soumet, au premier tour, une stratégie gagnante pour Arthur et (de façon non visible d'Arthur) une stratégie gagnante pour Nimué : les joueurs ont donc simplement à appliquer la stratégie gagnante que leur adversaire leur fournit obligeamment !

Une fois qu'on a cette construction ⌘g, on peut définir la borne inférieure de deux degrés comme précédemment : c(⟨m₁,m₂⟩|(ϑ₁,ϑ₂)) est égale à la réunion disjointe étiquetée de ⌘a(m₁|ϑ₁) et de ⌘b(m₂|ϑ₂) si ces deux valeurs sont toutes les deux définies. Pour dire les choses de façon plus intuitive : pour jouer au jeu correspondant à c, Arthur soumet une stratégie (calculable) d'interrogation de a et une stratégie (calculable) d'interrogation de b, et Nimué soumet des stratégies secrètes correspondantes, et Merlin choisit entre les deux, et renvoie une valeur correspondant soit à a soit à b, avec l'indication de laquelle il a choisi, où Arthur et Nimué ont joué selon les stratégies fournies. C'est exactement l'analogue de ce qu'on a fait au niveau T2 mais avec la complication qu'il faut ajouter les stratégies de Nimué partout.

Réduction de Weihrauch

J'ai raconté tout ce qui précède en mettant au centre de mon propos la réduction de Turing : c'est-à-dire (cf. mon autre billet à ce sujet) que les oracles peuvent être interrogés de façon illimitée. Mais on peut aussi faire le même genre de jeu avec la réduction de Weihrauch, c'est-à-dire avec des oracles qu'on a le droit d'interroger une et une seule fois (et même qu'on doit interroger une fois, ce qui n'est pas anecdotique parce que si l'oracle a des questions interdites ce n'est pas forcément évident de trouver une question qui n'est pas interdite ! notamment, interroger un oracle qui vous tue quelle que soit la question que vous posez n'est pas un cadeau).

Si on s'intéresse à la réduction de Weihrauch au lieu de Turing, les fonctions auxquelles on a affaire aux niveaux T1, T2 et T3, qu'il faudrait du coup peut-être plutôt appeler W1, W2 et W3, sont les mêmes, mais la réduction est différente : dans le jeu entre Arthur+Nimué et Merlin, le nombre de coups sera limité : Merlin joue d'abord (pour lancer le défi à calculer), puis Arthur puis Nimué (pour poser une question à l'oracle), puis Merlin (qui fournit la réponse de l'oracle) et enfin Arthur (qui doit déclarer la fin du calcul exactement à ce coup-là). Essentiellement tout ce qui concerne l'opération ‘⌘’ disparaît de l'histoire, et les choses sont globalement plus simples mais aussi, à mon avis, moins intéressante (l'équivalence de Weihrauch étendue W1, W2 ou W3 est beaucoup plus fine que l'équivalence de Turing T1, T2 ou T3, mais il me semble qu'elle est trop fine pour que les problèmes soient vraiment intéressants).

On peut trouver une correspondance avec des fonctions 𝒫(ℕ) → 𝒫(ℕ) analogues aux opérateurs effectifs locaux que j'ai décrits dans le cas de la réduction de Turing. Cette fois ce seront les opérateurs effectifs monotones qui sont définis en retranchant la 2e et la 3e condition de la définition des opérateurs effectifs locaux donnée plus haut (i.e., on demande juste que ⋂_{P,Q∈𝒫(ℕ)} ((P⇛Q) ⇛ (J(P)⇛J(Q))) soit habité). La définition de l'opérateur effectif monotone associé à un oracle (à usage unique !) est la même que celle que j'ai donnée pour J_a ci-dessus mais en oubliant le ‘⌘’ ; dans l'autre sens, la définition est la même : si je n'ai pas merdé mes définitions, ceci doit donner des bijections entre l'ensemble des degrés W3 (Weihrauch pour les fonctions avec conseil) et l'ensemble des classes d'équivalence (pour ‘≡’) des opérateurs effectifs monotones, et celles-ci préservent l'ordre partiel, les niveaux W2 resp. W1 correspondant aux cas où on préserve ⋂ resp. ⋂ et ⋃.

L'opération que j'ai notée ‘⌘’, que Kihara note ‘⅁’, que d'autres gens notent ‘◇’, correspond à prendre le plus petit degré de Turing (ici, T1, T2, T3) au-dessus d'un degré de Weihrauch (ici, W1, W2, W3) donné : les degrés de Turing se voient donc comme une rétraction des degrés de Weihrauch.

Fonctions sur ℕ^ℕ

Si on a lu mon billet sur le topos effectif, à la fin je parle de deux sortes de calculabilité sur l'espace de Baire ℕ^ℕ des suites d'entiers. (Cette section-là est relativement indépendante du reste, donc même si on n'a pas lu l'ensemble du billet sur le topos effectif, on peut la lire en sautant les bouts qui concernent la définition des topoi.) D'une part, il y a la seconde algèbre de Kleene, qui est une façon de définir des fonctions Φ_ε : ℕ^ℕ ⇢ ℕ^ℕ pour ε∈ℕ^ℕ (et énumérant toutes les fonctions continues sur un G_δ), qui se comporte de façon très analogue à la définition des fonctions calculables partielles φ_e(n) : ℕ⇢ℕ pour e∈ℕ. D'autre part, on peut utiliser les machines de Turing pour définir des fonctions Φ_e : ℕ^ℕ ⇢ ℕ^ℕ pour e∈ℕ, par exemple on peut dire que c'est juste Φ_φe (lorsque φ_e est totale, et non définie sinon) ou quelque chose comme ça (ou bien on peut dire que Φ_e(g) : ℕ→ℕ est la fonction calculée par la e-ième machine de Turing quand on lui fournit g:ℕ→ℕ comme oracle, si cette fonction est totale, et non définie sinon ; je crois bien que ça revient essentiellement au même).

Bref, il y a trois situations classiques à étudier :

• la calculabilité de Church-Turing des fonctions ℕ⇢ℕ (« première algèbre de Kleene »),
• la continuité des fonctions ℕ^ℕ ⇢ ℕ^ℕ (« seconde algèbre de Kleene »),
• la situation hybride, c'est-à-dire la calculabilité de Church-Turing des fonctions ℕ^ℕ ⇢ ℕ^ℕ (partie calculable de la seconde algèbre de Kleene).

(Et à la fin de mon billet sur le topos effectif, j'évoque trois topos correspondants : ce sont respectivement le topos effectif, le topos de la réalisabilité fonctionnelle, et le topos de Kleene-Vesley.)

Ces trois situations sont unifiées par la notion d'algèbre combinatoire partielle (relative), mais je pense que ça n'éclaircira rien que j'en dise plus à ce sujet.

Le fait est que beaucoup de ce ce que j'ai raconté ici en partant de la calculabilité de Church-Turing des fonctions ℕ⇢ℕ (en gros tout ce qui est complètement général, mais pas la description de tel ou tel oracle précis) peut se faire aussi aux deux autres niveaux : donc on a aussi des degrés T1, T2 et T3 pour les fonctions ℕ^ℕ ⇢ ℕ^ℕ pour la continuité et pour la calculabilité, et on a la correspondance avec les opérateurs effectifs locaux correspondants, et cela correspond à des topologies de Lawvere-Tierney sur le topos de la réalisabilité fonctionnelle et le topos de Kleene-Vesley respectivement. (Et, pour combiner les choses dont je n'ai pas parlé, on peut aussi faire des degrés de Weihrauch.)

Par exemple, pour la situation « seconde algèbre de Kleene », un opérateur effectif local J : 𝒫(ℕ^ℕ) → 𝒫(ℕ^ℕ) est une application telle qu'il existe un élément dans chacun des trois ensembles primo ⋂_{P,Q∈𝒫(ℕ^ℕ)} ((P⇛Q) ⇛ (J(P)⇛J(Q))), secundo ⋂_{P∈𝒫(ℕ^ℕ)} (P ⇛ J(P)), et tertio ⋂_{P∈𝒫(ℕ^ℕ)} (J(J(P)) ⇛ J(P)), et on note J₁ ≼ J₂ lorsqu'il existe un élément dans ⋂_{P∈𝒫(ℕ^ℕ)} (J₁(P) ⇛ J₂(P)), mais où cette fois ‘⇛’ désigne { ε∈ℕ^ℕ : ∀α∈P. (Φ_ε(α)↓ et Φ_ε(α)∈Q) } = { e∈ℕ : Φ_ε définit une fonction (totale) P→Q }. Tandis que dans la situation « hybride » on demande que les trois éléments exigés par la définition de J soient calculables (en tant que fonctions ℕ→ℕ, calculables au sens usuel), et de façon analogue pour la définition de ‘≼’ entre ces opérateurs.

J'avoue ne pas être très sûr de comment il faut modifier la définition côté oracles (par exemple comment se déroule le jeu Arthur-Nimué-Merlin) sur ℕ^ℕ, mais la description avec les opérateurs effectifs locaux assure au moins une définition robuste des degrés T3.

Les degrés T3 pour la situation hybride, c'est-à-dire la calculabilité des fonctions ℕ^ℕ ⇢ ℕ^ℕ (ou, ce qui revient au même, les topologies de Lawvere-Tierney sur le topos de Kleene-Vesley), bien que plus complexes à définir, sont peut-être un objet d'étude finalement plus satisfaisant que pour les fonctions ℕ ⇢ ℕ (ou, ce qui revient au même, les topologies de Lawvere-Tierney sur le topos effectif) : car dans ce dernier cas (celui dont j'ai parlé tout au long de ce billet), il semble qu'on n'ait pas vraiment d'autre exemple intéressant que les exemples déjà évoqués (les degrés de Turing ordinaires, les Error_1/ℓ, l'oracle de Pitts Cofinite et quelques autres), tandis que dans la situation ℕ^ℕ ⇢ ℕ^ℕ les exemples abondent : on a une structure extrêmement riche, qui inclut le treillis de Medvedev des degrés de difficulté (en fait, deux fois : une fois à l'endroit et une fois à l'envers) mais aussi toutes sortes de choses qui peuvent servir à fabriquer des modèles intéressants des maths constructives.