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

@Nico:

Encore une fois, la définition mathématiquement correcte, c'est avec le jeu à trois joueurs. Au lieu de poser des questions à un oracle, Arthur convient d'une stratégie à l'avance avec Nimué, et donc le sens précis d'une « question bien posée à l'oracle » c'est une stratégie que Nimué peut appliquer pour choisir son coup en fonction des coups précédemment joués par Arthur et Merlin (enfin, Merlin, parce que pour ce qui est d'Arthur, Nimué peut de toute façon prédire ce qu'il fait puisqu'elle a convenu de sa stratégie avec lui et qu'il n'a pas plus d'information qu'elle). Dans cette version à trois joueurs, Arthur n'a pas besoin de poser explicitement des questions, puisque Nimué va jouer selon ce qu'ils ont convenu à l'avance, mais mentalement on peut s'imaginer qu'Arthur a posé une question et que Nimué y a répondu (et qu'ensuite Merlin encode la réponse de Nimué sous forme de machines de Turing).

À titre d'exemple, si je propose qu'au 42e coup et dans certaines circonstances, Arthur demande à l'oracle « est-ce que jusqu'à présent tu me m'as donné que des machines qui ne s'arrêtent pas ? », c'est juste une façon de dire que Nimué, au 42e coup et dans certaines circonstances, va jouer « oui » si Merlin n'a joué que des machines qui ne s'arrêtent pas, et « non » sinon, et c'est une stratégie qui a un sens (c'est-à-dire que ça définit une fonction des coups précédents du jeu vers les coups possibles de Nimué) donc c'est une question légitime à l'oracle. Une fonction ne peut pas dépendre de ses propres valeurs ni des coups ultérieurs, donc ce genre de choses auto-référentiels ou dépendant de l'avenir n'est pas possible. C'est-à-dire qu'en pratique, une stratégie bien définie c'est juste quelque chose qui dépend du passé et pas de l'avenir. Mais encore une fois, la définition qui fait foi mathématiquement, c'est celle avec le jeu à trois joueurs (que je peux écrire de façon ultra-formelle si on a un doute, mais ce sera illisible).

J'espère que c'est clair, maintenant.

(Et effectivement, pédagogiquement, je me demande bien quelle est la meilleure façon de présenter les choses pour à la fois rendre l'énigme intuitive comme ce que j'ai écrit au début du billet, mais en même temps expliquer qu'on ne peut pas faire le malin à poser des questions auto-référentielles.)

@Thierry:

Il est bien connu et évident que si on permet d'interroger un oracle en faisant référence aux réponses de l'oracle lui-même, on arrive immédiatement à des conclusions absurdes (ici, il suffit de demander « vas-tu me répondre par deux machines de Turing ayant le même comportement ? » et l'oracle disparaît dans un pouf de logique).

C'est pour ça que dans la version mathématiquement précise du problème, l'oracle est remplacé par deux joueurs, Nimué qui cherche à nous aider (nous = Arthur) mais ne peut pas communiquer directement avec nous, et Merlin qui cherche à nous embêter, et Nimué ne peut pas prédire les coups que va faire Merlin ni réciproquement (en revanche, les deux sont capables d'utiliser n'importe quelle stratégie, pas forcément calculable). Ça c'est le legalese pour les gens qui font les malins. Mais en pratique, ça veut dire que l'oracle est omniscient pour tout ce qui n'est pas « l'avenir » (ses propres réponses, ou ce qui peut en dépendre).

En revanche, on a parfaitement le droit de poser à l'oracle des questions sur ses réponses passées et/ou sur le comportement de machines de Turing. Par exemple « est-ce que jusqu'à présent tu me m'as donné que des machines qui ne s'arrêtent pas ? » est une question légitime, et l'oracle y répondra correctement (toujours suivant le même code).