Comments on Une autre énigme de calculabilité

Avec plus de personnages, c'est peut-être plus clair ?

Le cruel docteur No, pour changer un peu des mathématiciens, a capturé un informaticien. Il lui pose une question à résoudre pour sauver sa peau. Mais comme c'est un informaticien, il ne lui demande pas simplement de donner une solution abstraite, mais une solution algorithmique. La question prend un paramètre, qui est un entier naturel n, et elle a pour réponse « oui » ou « non » en fonction de n. L'informaticien doit fournir un programme prenant n en entrée, qui doit terminer et renvoyer la réponse.

Le docteur No communique la question à l'informaticien. Alors, l'informaticien se met à pleurer amèrement sur son sort, car il constate que la question est algorithmiquement insoluble.

Ses cris lui attirent la pitié d'un serviteur du Docteur No, qui obtient pour lui le droit à obtenir une indication. L'informaticien aura le droit de la choisir, et elle pourra dépendre de n. Mais comme le docteur No est pervers, et qu'il ne faudrait pas que l'informaticien puisse simplement demander la solution comme indication, cette indication sera donnée d'une manière spéciale. Le programme de l'informaticien recevra en entrée non seulement l'entier n, mais aussi le code d'un programme P. Le docteur No garantit que si la réponse à la question sur n est « oui », alors P termine et renvoie l'indication souhaitée (qui dépend de n). Mais si la réponse est « non », alors il n'y a aucune garantie : P peut ne pas terminer, ou bien terminer et donner une fausse indication choisie par le docteur No pour tromper le programme de l'informaticien.

Alors, l'informaticien pousse un cri de joie : il se rend compte qu'il peut s'en sortir !

Quelle pouvait être la question du docteur No, et comment l'informaticien a-t-il pu choisir son indication ?

Wait, I can see the loophole! This time the cruel Doctor No did not definitively promise to kill me avec ses tortures particulièrement raffinées if q accepts a number n for which d is false. He is clearly trying to impress and recruit me.

I'll generate a private key encryption keypair, define h(n) to sign n with my private key if d(n) but 0 otherwise. Then q just has to verify that signature using my public key. If Doctor No managers to generate a fake hint h for an n where d is false such that q accepts, then either he really has the supercomputer that he's boasting with (an insanely fast Turing-machine is enough), or he has some secret breakthrough in cryptanalysis. If that happens then he managed to impress me with an actually useful contribution, so I join him and help him take over the world using this supercomputer or cryptanalytic attack.