Comments on Une énigme avec un dragon et de la calculabilité

Update : Je suis plongé périodiquement dans le bouquin *Calculabilité* de Benoît Monin et Ludovic Patey, et il y a une section (8.6) qui rassemble un certain nombre de propriétés intéressantes des degrés PA. Pour une fois, c'est accessible gratuitement *et* légalement, enfin seulement la première partie du bouquin, mais elle contient cette section : <URL:http://ludovicpatey.com/courses/comp-thy-2023/>

Bon, je l'ai posée là : https://cs.stackexchange.com/questions/164841/turing-degree-of-some-functions-related-to-rices-theorem

J'ai beau avoir trouvé la réponse [postée sur Twitter], je n'ai aucune idée de la formulation mathématiquement élégante du théorème dont cette énigme est censée être une reformulation. La conversion en énigme serait-elle une fonction de hachage cryptographique viable ? En tous cas, je suis bien curieux de lire l'entrée à venir sur le sujet.

Sinon, il me vient une question en repensant à la solution. Je n'ai pas trouvé pour l'instant — même si je n'ai pas cherché très longtemps non plus, mais je trouve la question intéressante, alors je la poste quand même et je continuerai à chercher demain.

Comme expliqué sur Twitter, mon point de vue sur ce problème (certes, j'aurais pu faire l'élimination des coupures pour tomber sur la solution que vous donnez) est de remarquer que s'il veut éviter de nous donner des informations, le programme de la porte du dragon doit (en appelant X la porte du dragon et Y, Z les portes sûres) :

a) Renvoyer Y sur toute entrée qui est le code d'un programme qui termine et renvoie Y
b) Renvoyer Z sur toute entrée qui est le code d'un programme qui termine et renvoie Z
c) Terminer sur toute entrée

Or ceci n'est pas possible, on peut s'en faire une intuition en repensant au mantra du théorème de Rice, « on ne peut pas analyser statiquement les programmes en toute généralité », ou encore « si je veux faire quelque chose qui dépend de la sortie d'un certain programme que j'ai pris en entrée, je ne peux pas le faire tout en terminant à coup sûr, parce que ma seule façon d'obtenir la sortie, en dehors de cas particuliers, est d'exécuter le programme que j'ai en entrée, et je ne peux pas savoir à l'avance s'il terminera ».

Après avoir déterminé qu'il suffisait de prouver qu'un programme satisfaisant aux conditions (a), (b), (c) ne pouvait pas exister, j'ai appliqué les préceptes qu'on m'a inculqués en cours de calculabilité, à savoir de ne pas se jeter sans réfléchir dans une preuve directe d'indécidabilité, mais d'essayer réduire un problème connu comme indécidable. Or, pour le théorème de Rice, il existe effectivement une preuve classique par réduction depuis le problème de l'arrêt, d'ailleurs c'est dans vos transparents, mais je la remets pour les autres lecteurs : Soit f une fonction extensionnelle non-triviale (i.e., l'entrée de f est le code d'un programme, f n'est pas constante, et f prend la même valeur sur deux programmes qui ont le même comportement, au sens où soit ils ne terminent pas tous les deux, soit il terminent tous les deux avec la même sortie). Comme elle est extensionnelle, elle prend la même valeur sur tous les programmes qui ne terminent pas. Comme elle est non-triviale, elle prend une valeur différente sur un certain programme P. La réduction consiste à prendre un programme E en entrée, donc on veut savoir s'il termine, et à construire le programme

S :
Exécuter E et ignorer son résultat
Exécuter P et renvoyer son résultat

On voit que si E termine, S est équivalent à P, tandis que si E ne termine pas, S est équivalent aux programmes qui ne terminent pas. Donc, la valeur de f sur S permet de déterminer si E termine.

Bon. Maintenant, revenons au problème de l'énigme. On ne suppose plus f extensionnelle et non-triviale, on suppose seulement que si X termine et renvoie 0, alors f(X) = 0, et si X termine et renvoie 1, alors f(X) = 1. En particulier, f est bien non-triviale, et elle a une forme limitée d'extensionnalité, qui ne s'applique qu'à des programmes *qui terminent*. Mais on ne fait plus aucune hypothèse sur ce que renvoie f lorsqu'on lui passe un programme qui ne termine pas. En particulier, la preuve ci-dessus ne marche plus du tout. Par contre, on peut adapter l'autre preuve de Rice, par diagonalisation directe, et c'est ce que vous faites dans la solution.

Ma question : est-ce qu'on peut quand même sauver la preuve par réduction ? Dit autrement, si f vérifie cette condition, est-ce que le degré de Turing de f est forcément ≥ 0' ?

The cruel Doctor No tortured us in more terrible ways than just feeding us to a dragon, and he demanded a proof of our solution rather than let use take a two thirds chance, but I'm still missing him.

Now to solve this puzzle. SPOILER.

We know the source code for the program p_A of door A. Use a quine technique to write a program r_A that runs the program p_A with r_A as an argument, then if p_A outputs B then output C, otherwise output B. Similarly, using the programs for the other two doors, write r_B and r_C similarly with cyclical permutations of the three doors. The run in parallel p_A with r_A as an argument, p_B with r_B as an argument, and p_C with r_C as an argument. Wait for the first program to finish. Suppose p_A finishes first. If it outputs B then door B is safe, otherwise door C is safe. Similarly for the other three programs, with the door names cyclically permuted.

If door A has the dragon then of course either B or C is safe. Assume door A has the dragon and p_A outputs B. Then r_A outputs C, so if door C was safe then p_A with r_A as argument would have to output C, which is a contradiction. Thus door B has to be safe. Now suppose door A has the dragon and p_A outputs anything other than B. Then r_A outputs B, so if door B was safe then r_A would have to output B, which is a contradiction. This means that door C is safe.

It's worth to examine why the argument in the second part of your post doesn't hold. The tables that you give suggest that you write your three programs such that they always run their argument completely. With my solution, this means they would never halt, which is against the rules of the puzzle for the door with the dragon.

Alas, my solution only works if the programs are completely deterministic. The cruel Doctor No could write p_Y to carefully analyze its argument, and if it finds that it could print X then p_Y prints X or Z randomly (Z with more than half chance). It's not entirely clear to me if this would satisfy the puzzle conditions, or if there's at least something similar that Doctor No could do that satisfies them.

Question pour le programme sur une porte sûre : est-ce que le programme d'entrée doit obligatoirement n'avoir aucune entrée ? Et est-ce que le programme du dragon peut donner le bon résultat même si on ne lui envoie aucune entrée ? Pour le dire autrement : que ce passe-t-il si on met le programme de la porte dragon en entrée du programme d'une porte sure ?

Parce que j'avais eu l'idée de mettre chaque programme en entrée de tous les programmes (y compris eux-mêmes), de lancer le calcul et de combiner les résultats des programmes qui terminent, éventuellement en éliminant certains résultats superflus.