Devinette mathématique (pas très difficile !) :
Vous avez accès à un oracle omniscient auquel vous pouvez poser (de
façon illimitée) des questions à réponse oui/non. Mais évidemment il
y a une arnaque : au lieu de répondre oui
ou non
,
l'oracle code sa réponse. Plus exactement, pour chaque question, il
va vous donner la réponse sous forme d'une machine de Turing. Pour
dire oui
, il va vous présenter une machine de Turing qui
s'arrête ; et pour non
, il va vous présenter une machine de
Turing qui ne s'arrête pas. Vous êtes limité par la thèse de
Church-Turing, donc n'avez pas de moyen pour savoir en
général si une
machine de Turing s'arrête ou pas. (L'oracle, lui, peut
évidemment répondre à cette question, puisqu'il est omniscient ; mais
comme il vous donnera la réponse de façon codée, vous n'êtes pas plus
avancé.) L'oracle cherche à vous embêter : il veut vous empêcher de
récupérer des informations utiles de ses réponses. Problème :
pouvez-vous forcer l'oracle à vous révéler des choses utiles, ou
peut-il s'arranger pour rendre ses réponses complètement
inutiles ?
(Si vous trouvez que c'est mathématiquement trop vague parce que je
parle d'oracle omniscient
sans définir ce terme, je vais
présenter des versions beaucoup plus précises plus bas. Mais celle-ci
me semble quand même raisonnablement claire et assez parlante pour
attirer la curiosité et expliquer de quoi il est question.)
Cette devinette n'est pas trop difficile, et j'encourage à y
réfléchir, ne serait-ce que pour comprendre pourquoi la suite
m'intéresse. En tout cas, il ne suffit pas de dire il n'y a pas
moyen calculable de résoudre le problème de l'arrêt
(ce qui est,
certes, vrai) pour avoir répondu au problème. Voici la réponse
(cliquez
ici pour la faire apparaître) :
Réponse (à la devinette
facile) : Je peux forcer l'oracle à répondre à n'importe quelle question
oui/non de la manière suivante. Si je veux savoir la réponse à une
question Q, je vais poser à l'oracle d'abord la
question Q elle-même, puis la question ¬Q
(c'est-à-dire la réponse à la question Q
code-t-elle
— ou, si on préfère, non
?la réponse que tu
viens de me donner est-elle
— de manière à échanger
les réponses non
?oui
et non
). J'ai donc maintenant deux
machines de Turing (celle fournie par l'oracle en réponse à la
question Q et celle fournie par l'oracle en réponse à la
question ¬Q) et la certitude qu'exactement une des deux
s'arrête. Je peux lancer leur exécution en parallèle, jusqu'à ce que
l'une termine (ce qui arrivera forcément en temps fini). Si la
première s'arrête, je sais que la réponse à Q
est oui
, et si la seconde s'arrête, je sais que la réponse
à Q est non
. J'ai donc obtenu la réponse à ma
question.
Maintenant, modifions la devinette pour la rendre plus difficile en empêchant la stratégie utilisée dans la réponse ci-dessus :
Devinette mathématique (beaucoup plus
difficile !) : Comme précédemment, vous avez accès à un oracle
omniscient auquel vous pouvez poser (de façon illimitée) des questions
à réponse oui/non. Et comme précédemment, au lieu de
répondre oui
ou non
, l'oracle code sa réponse. Mais
cette fois, pour chaque question, il va vous donner la réponse sous
forme de deux machines de Turing. Pour dire oui
, il
va vous donner deux machines de Turing dont l'une s'arrête et l'autre
pas ; et pour non
, il va vous donner deux machines de Turing
qui soit s'arrêtent toutes les deux soit aucune ne s'arrête. Tout le
reste est comme dans a devinette précédente : vous êtes limité par la
thèse de Church-Turing, et l'oracle cherche à vous embêter.
Problème : pouvez-vous forcer l'oracle à vous révéler des choses
utiles, ou peut-il s'arranger pour rendre ses réponses complètement
inutiles ?
Je n'ai pas la solution à cette devinette, et elle m'obsède un peu (je tourne autour de plein de variations autour d'elle, mais je n'ai vraiment aucune idée de comment l'attaquer). Donc j'essaie de la balancer dans la nature (i.e., sur le Web) dans l'espoir que quelqu'un ait une idée intelligente. (Comme je vais le dire plus bas, c'est une variation sur cette énigme que j'ai posée ici et là sur MathOverflow.)
Le but de la suite de ce billet est de tourner autour du pot de
cette devinette : comme le font les mathématiciens qui ne savent pas
répondre à une question, ils la formalisent, donc je vais expliquer
comment on peut imaginer définir une notion en quelque sorte « duale »
de la notion (habituelle)
des degrés de
Turing, les degrés de co-Turing
(ou
de coTuring
? Coturing
? coturne
?), et que la
devinette ci-dessus s'inscrirait dans le cadre de cette notion. Mais
je ne sais malheureusement à peu près rien dire à son sujet, donc
c'est un peu du formalisme pour formaliser, mais j'espère au moins
convaincre que la question est bien définie (elle a un sens
mathématique précis) et au moins raisonnablement naturelle.
[Je précise que ce qui précède a été pour l'essentiel écrit avant ce qui suit, ce qui peut expliquer la présentation un peu étrange.]
⁂
Le but de ce billet, donc, est pour moi de réfléchir tout haut à une définition qui m'a traversé l'esprit : ce n'est pas vraiment de faire de la vulgarisation. Si vous ne connaissez pas un peu la théorie de la calculabilité, passez votre chemin (lisez plutôt ceci, ou bien, si vous voulez quelque chose de plus costaud, ça ou ça).
Bref. Je me suis rendu compte qu'il y a une notion en quelque sorte « duale » de la réduction de Turing, qui ne semble pas du tout avoir été étudiée. Je vais essayer de donner la définition de plusieurs manières différentes, de dire quelques propriétés évidentes, et de poser des questions auxquelles je ne sais pas répondre.
☞ Définition informelle de la « réduction de co-Turing »
Je commence par rappeler :
Si A,B⊆ℕ, on dit que A est Turing-réductible à B lorsqu'on peut répondre à la question
est-ce que m∈A ?en posant librement des questionsest-ce que n∈B ?, par un processus calculable.
Ceci est dit de façon informelle, mais je pense que c'est assez
parlant. Mais formulons les choses un peu différemment en
introduisant une terminologie un peu idiote : si A⊆ℕ, je
vais dire qu'un m∈ℕ est
un A-codage de oui
lorsque m∈A, et que c'est un A-codage
de non
lorsque m∉A (autrement dit,
un A-codage d'un booléen c est un m
tel que c = 1A(m),
en notant 1A la fonction indicatrice
de A). Avec cette terminologie, on peut dire (toujours
informellement) :
On dit que A est Turing-réductible à B lorsqu'on peut, par un processus calculable. A-décoder un booléen, à condition d'être librement capable de B-décoder des booléens.
En encore plus court : A est Turing-réductible à B lorsque la capacité de B-décoder les booléens permet (calculablement !) de A-décoder les booléens. I.e., je postule la capacité de B-décoder et j'obtiens la capacité de A-décoder.
De façon symétrique, je propose la définition suivante (dite de façon informelle, et que je vais rendre précise ensuite) :
Si A,B⊆ℕ, on dira que A est co-Turing-réductible à B lorsqu'on peut, par un processus calculable, répondre à n'importe quelle question booléenne de façon B-encodée, à condition d'être librement capable d'obtenir la réponse à n'importe quelle question booléenne de façon A-encodée.
En encore plus court : A est co-Turing-réductible à B lorsque la capacité de A-encoder des booléens cachés permet (calculablement !) de B-encoder des booléens cachés. (Attention ! il s'agit de booléens cachés, cf. ci-dessous pour plus d'explications.) I.e., je postule la capacité de A-encoder et j'obtiens la capacité de B-encoder.
Dit comme ça, j'espère que c'est clair pourquoi la notion que je
propose est en quelque sorte duale de la notion de réduction de
Turing : d'où le terme de réduction de co-Turing
.
Entendons-nous bien : quand je parle d'encoder un booléen, il
s'agit de booléens cachés. Encoder un booléen connu c'est
toujours évident : une fois qu'on a un m₀∉A et
un m₁∈A, il suffit de renvoyer l'un ou l'autre,
et ceci est toujours calculable. (On peut objecter oui mais si je
ne connais pas de tels m₀ et m₁ ?
mais ce
n'est pas ce dont je veux parler ici : ma partie étant fixée, et ni
vide ni pleine, ces m₀ et m₁ existent et des
algorithmes écrits avec eux existent aussi ; d'ailleurs, peut-être que
je devrais postuler une fois pour toutes que 0∉A et que
1∈A.)
Mon problème, donc, c'est que quelqu'un (qu'on va appeler Merlin plus bas) a choisi un booléen et ne me l'a pas dit, et moi j'ai le droit de lui poser n'importe quelle question (portant sur son booléen caché ou sur « n'importe quoi ») mais il me répond de façon A-codée ; et mon but c'est de produire un B-codage du booléen choisi.
Note : Je dois signaler que j'ai « inversé » la réduction par rapport à ce qu'on pourrait peut-être imaginer, de manière à ce que les ensembles les plus « difficiles » soient toujours réductibles aux ensembles les plus « faciles », ce qui rend la comparaison avec d'autres réductions tout de même plus naturelle, mais du coup ça peut sembler à l'envers (A est co-Turing-réductible à B lorsque la capacité de A-encoder des booléens cachés permet calculablement de B-encoder des booléens cachés). Évidemment, cette « inversion » va se sentir dans toutes les autres versions de la définition.
☞ Définition avec des jeux à trois joueurs
Pour rendre la définition précise, le mieux est d'introduire des jeux à trois joueurs. J'ai évoqué ce type de jeux dans ce billet passé (qui est une tentative de semi-vulgarisation de cet article), mais je vais redire le nécessaire. Les règles générales (toujours valables) de ce type de jeu sont les suivantes :
Il y a trois joueurs, Arthur
, Nimué
et Merlin
.
Arthur et Nimué font équipe contre Merlin. Ils jouent dans l'ordre
suivant : Merlin, Arthur, Nimué, Merlin, Arthur, Nimué, etc., jusqu'à
ce qu'Arthur mette fin à la partie. Nimué et Merlin voient tous les
coups précédemment joués par tous les joueurs ; Arthur ne voit que les
coups explicitement déclarés visibles d'Arthur
. De plus,
Arthur devra jouer selon une stratégie calculable (alors que les deux
autres joueurs n'ont pas de telle limitation). Le jeu continue
jusqu'à ce qu'Arthur y mette fin en faisant une « annonce » : si cette
annonce est correcte (selon les modalités spécifiques du jeu), Arthur
et Nimué gagnent ; s'il fait une annonce incorrecte, ou qu'il n'en
fait jamais (y compris si sa stratégie censée être calculable ne
renvoie pas de coup à jouer, par exemple parce qu'elle ne termine
pas), alors Arthur et Nimué ont perdu ; et bien sûr, si un joueur ne
respecte pas les contraintes du coup, alors il perd immédiatement.
En gros, il faut imaginer ça comme un jeu de communication : Nimué essaie de passer de l'information à Arthur, mais elle ne peut pas communiquer directement avec Arthur, elle ne peut le faire qu'à travers Merlin, qui essaie de leur mettre des bâtons dans les roues. La question qu'on va se poser, c'est si Arthur et Nimué ont moyen d'avoir une stratégie commune pour gagner contre Merlin.