Allez, en cadeau de Noël, un deuxième billet à deux jours d'intervalle, ce qui est devenu très rare sur ce blog : je vous propose une devinette dont je posterai la solution ultérieurement. Je la trouve très jolie et surprenante et je pense qu'elle aurait beaucoup plu à Raymond Smullyan.
Méta : Elle m'est venue en réfléchissant à des questions de maths (autour de la réalisabilité propositionnelle). La formulation est de moi, mais c'est en fait une réécriture d'un théorème (de Plisko, je donnerai la référence précise en même temps que la solution) dont j'ai lu l'énoncé et que j'ai reformulé comme une énigme pour y réfléchir parce que je ne voulais pas lire la preuve mais la retrouver moi-même. J'ai eu énormément de mal à la résoudre, donc je pense qu'elle est vraiment dure (d'un autre côté, je n'étais pas sûr d'avoir trouver la bonne formulation, donc je réfléchissais à la fois à la question et à la réponse), mais quand je l'ai présentée sur Twitter, au moins une personne a trouvé la solution, donc elle n'est certainement pas insoluble. Même si elle a un rapport distant avec mon très long billet tout récent sur Curry-Howard (et je compte écrire une autre entrée qui fait référence aux deux, et qui explique l'intérêt mathématique de cette énigme), il n'est pas nécessaire, ni même spécialement utile, d'avoir lu ce billet (ni aucun autre) pour réfléchir à cette énigme. En revanche, il est certainement pertinent d'avoir des notions de calculabilité pour espérer y arriver (même si je vais présenter l'énoncé pour qu'il soit compréhensible sans ça). J'éditerai ce billet d'ici quelques jours pour présenter la réponse ainsi que quelques commentaires : pour l'instant je me contente de l'énoncé de l'énigme, suivi de quelques commentaires.
L'énigme
Vous êtes un aventurier dans un donjon. Devant vous se trouvent trois portes, identiques à part leur étiquette : A, B et C. Derrière une de ces portes se trouve un dragon, qui vous dévorera si vous ouvrez la porte, mais vous ne savez pas laquelle. Votre but est d'ouvrir une des portes « sûres », c'est-à-dire sans dragon (et qui conduisent à la sortie et, soyons généreux, à un trésor pour vous récompenser d'avoir résolu l'énigme). Peu importe quelle porte sûre vous ouvrez, la seule chose qui importe est de ne pas ouvrir la porte au dragon.
Pour vous aider à trouver une porte sûre, il y a un indice apposé sur chaque porte. Mais comme ceci est un donjon très moderne, pas ces trucs poussiéreux des magiciens d'il y a quelques siècles, chaque indice prend la forme d'un programme informatique. Ça tombe bien, vous avez un ordinateur capable de faire tourner ces programmes (ou pour en examiner le contenu si vous le voulez).
L'idée générale est que le programme apposé sur chaque porte devrait, quand vous l'exécutez, vous indiquer une des deux autres portes qui soit sûre. Mais ce n'est pas si simple ! Car le programme demande quelque chose en entrée, et ne fonctionnera correctement que si on lui a fourni le bon quelque chose. Et ce quelque chose est aussi un programme (qui, lui, ne prend rien en entrée).
Les règles précises sont les suivantes :
Le programme apposé sur la porte au dragon, quoi qu'on lui passe en entrée, va terminer quoi qu'il arrive et produire comme résultat l'étiquette d'une des deux autres portes. (Comme il n'y a qu'un dragon, les deux autres portes sont sûres, donc ce sera de toute façon une porte sûre. Son choix peut dépendre de ce que vous avez donné en entrée, mais il doit produire un résultat dans tous les cas, même si le programme qu'on lui a fourni en entrée n'a pas de sens ou ne termine pas ou quoi que ce soit du genre.)
Le programme apposé sur une porte « sûre » va terminer et produire comme résultat l'étiquette de l'autre porte sûre (il n'y en a qu'une autre), mais à condition qu'on lui ait fourni comme entrée un autre programme qui lui-même (exécuté sans entrée) produit comme résultat l'étiquette de l'autre porte sûre. Si cette condition n'est pas remplie, le comportement du programme n'est pas précisé (il pourrait ne pas terminer, produire une mauvaise porte, ou afficher 42 ou n'importe quoi d'autre ; mais il ne va pas vous tuer, quand même : c'est un programme, pas un dragon, et votre ordinateur peut le faire tourner sans risque).
Je redis ça pour être bien sûr d'avoir été clair. Appelons X la porte au dragon, et Y,Z les deux autres portes. Appelons pX,pY,pZ les programmes apposés aux portes X,Y,Z respectivement, et q un programme qu'on décide de passer en entrée à un de pX,pY,pZ. Les garanties sont : d'abord, concernant la porte au dragon, pX(q) termine quoi que soit q et produit comme résultat soit Y soit Z ; ensuite, concernant les deux autres portes : si q termine et produit Z comme résultat alors pY(q) termine et produit lui aussi Z comme résultat, et de même, si q termine et produit Y comme résultat alors pZ(q) termine et produit Y comme résultat.
Vous avez bien sûr le droit de lancer les programmes plusieurs fois (séquentiellement ou en parallèle) avec des entrées différentes. Vous avez le droit de créer vos propres programmes (par exemple écrire un programme qui produit toujours la sortie B, et fournir ça au programme de la porte C est légitime ; ou même faire un programme qui exécute le programme de la porte C sur le programme qui produit toujours B en sortie, et fournir ça au programme de la porte A : tout ça est légitime). Vous avez aussi tout le temps nécessaire, mais il faut quand même arriver à un résultat de façon certaine au bout d'un temps fini (donc on a le droit d'attendre longtemps la sortie d'un programme, mais s'il ne termine jamais c'est un échec).
En fait, votre réponse sera elle-même algorithmique. C'est-à-dire que techniquement, ce que je demande c'est d'écrire un programme qui prend en entrée les programmes pX,pY,pZ apposés aux trois portes et qui, quelle que soit la porte au dragon et quels que soient pX,pY,pZ vérifiant les contraintes, termine et produit en sortie l'étiquette d'une porte qui n'a pas de dragon.
Voilà, c'est un peu long, mais j'espère que c'est parfaitement clair. S'il y a quelque chose qui ne l'est pas, dites-le moi en commentaire et j'essaierai de préciser les règles.
Résumé : Il y a une seule porte avec un dragon et on ne sait pas laquelle, les deux autres sont sûres et le but est de trouver une porte sûre. Chaque porte a un programme apposé comme indice. Ce programme termine et produit comme résultat l'étiquette d'une des deux autres portes qui soit sûre ; mais, s'agissant du programme apposé sur une porte sûre, ceci n'est garanti que sous condition qu'on lui passe comme entrée un programme (sans entrée) qui lui-même termine et produise comme résultat l'étiquette de l'autre autre porte qui soit sûre.
Comment vous tirez-vous (de façon certaine) de cette fâcheuse situation ?
Pourquoi elle semble insoluble
J'ai fini l'énoncé de l'énigme et on peut s'arrêter de lire là si on veut y réfléchir ; mais je vais quand même faire un commentaire qui, sans vraiment constituer un indice, attire l'attention sur ce qui est difficile dans cette énigme.
Ce qui rend le problème paradoxal, et en apparence insoluble, donc, c'est qu'aucun indice n'apporte d'information : le programme sur la porte du dragon va produire l'étiquette d'une des deux autres portes, mais comme de toute façon les deux autres portes sont sûres ceci n'apporte rien, et le programme sur une porte sûre va produire l'étiquette de l'autre porte sûre seulement à condition qu'on lui fournisse un programme qui fait exactement ça, donc il pourrait tout simplement en recopier la sortie.
Et de fait, si au lieu d'avoir affaire à des programmes on avait
affaire à des boîtes noires, le problème serait
insoluble. Imaginons par exemple qu'on parle de bêtes
tableaux : l'entrée (q) des tableaux est un tableau à zéro
entrée, c'est-à-dire une seule case, c'est
juste A, B ou C (ou éventuellement
autre chose qui ne vérifie pas les contraintes), et le tableau
(p) sur chaque porte est donc un tableau à une entrée
(A, B ou C, éventuellement autre
chose
) qui produit une sortie (A, B
ou C, éventuellement autre chose
) avec les
contraintes que j'ai dites. Or toutes les contraintes sont
satisfaites si chaque tableau associe à l'étiquette d'une autre porte
cette étiquette elle-même, et à n'importe quoi d'autre l'étiquette de
la porte cycliquement après elle… bon, ma phrase est incompréhensible,
mais je veux dire :
| Tableau porte A | |
|---|---|
| Entrée (q) | Sortie (pA(q)) |
| A | B |
| B | B |
| C | C |
| (autre) | B |
| Tableau porte B | |
|---|---|
| Entrée (q) | Sortie (pB(q)) |
| A | A |
| B | C |
| C | C |
| (autre) | C |
| Tableau porte C | |
|---|---|
| Entrée (q) | Sortie (pC(q)) |
| A | A |
| B | B |
| C | A |
| (autre) | A |
Ces tableaux vérifient mes contraintes (chaque tableau produit
comme résultat l'étiquette d'une des deux autres portes qui soit
sûre ; mais, s'agissant du programme apposé sur une porte
sûre, ceci n'est garanti que sous condition qu'on lui passe comme
entrée l'étiquette de l'autre autre porte qui soit sûre
), et ils
apportent exactement zéro information sur le dragon puisque tout ça
est complètement symétrique entre A, B
et C (et de fait, je n'ai pris aucune décision sur
l'emplacement du dragon en écrivant ça, il pourrait être n'importe
où). Donc si on comprend mon énigme sous cette forme, ce qu'on aura
naturellement tendance à faire en lisant l'énoncé, elle est
insoluble.
Et pourtant, elle a une solution ! Où est la magie ?
Une indication
[Section ajoutée .]
En guise d'indication, et avant de donner la réponse, voici un problème plus simple, a priori indépendant, mais qui aide à résoudre le précédent :
Considérons un choix entre seulement deux options (disons par
exemple U et V). L'un de ces choix sera appelé
le bon
choix et l'autre le mauvais
, mais on ne sait pas
lequel est lequel. On dispose pour nous aider à faire le choix d'un
programme (p) dont l'exécution va terminer et produire
comme résultat le bon choix, mais à condition qu'on lui ait
fourni comme entrée un autre programme (q) qui lui-même
(exécuté sans entrée) produit comme résultat le bon choix.
Que peut-on fournir comme entrée q à p pour
être sûr que p ne renverra pas le mauvais choix (il peut ne
jamais rien renvoyer, ou même renvoyer un truc qui n'a rien à voir
comme 42
, mais on veut être sûr que p ne renverra
pas le mauvais choix) ?
(On peut éventuellement chercher aussi à se convaincre qu'on ne peut pas faire mieux : il n'y a aucun moyen, à partir des données dont on dispose ici, de déterminer à coup sûr le bon choix ; donc tout ce qu'on demande c'est de trouver une façon d'exécuter p pour qu'il ne renvoie pas le mauvais choix. Ensuite, on cherchera un moyen d'utiliser ce principe pour résoudre l'énigme de départ.)
La réponse
[Section ajoutée .]
La réponse à l'indication
Je commence par donner la réponse à l'indication ci-dessus : donc, on dispose pour nous aider à faire le choix entre deux options d'un programme (p) dont l'exécution va terminer et produire le bon choix comme résultat, mais à condition qu'on lui ait fourni comme entrée un autre programme (q) qui lui-même (exécuté sans entrée) produit comme résultat le bon choix. Sur quelle entrée q lancer le programme p pour être sûr qu'il ne fera pas le mauvais choix ?
La réponse est très simple : on va définir q comme le programme qui lance le programme p sur le programme q lui-même (je vais expliquer ce point ci-dessous) et qui ensuite change le résultat si c'est une des deux options (i.e., échange U et V). Ainsi, par définition, la sortie de q est la sortie de p(q) (si ce dernier termine) avec U et V échangés.
Dans ces conditions, il est impossible que p(q) renvoie le mauvais choix : car si p(q) renvoie le mauvais choix, alors q renvoie le bon (puisqu'il échange les deux options), donc p(q) renvoie le bon choix par l'hypothèse qui a été faite sur p — une contradiction. Ceci résout l'énigme proposée en indication.
Sauf qu'il faut que j'explique comment je peux faire un programme q qui fait référence à lui-même dans sa définition. Ça tombe bien, j'ai écrit tout une page sur cette question (l'écriture de « quines ») il y a des décennies. Le fondement théorique est le théorème de récursion de Kleene, mais on n'a pas besoin de regarder ça. Je peux expliquer la chose en disant que le programme q est le suivant :
Soit r le programme qui prend en entrée un programme s (lequel attend une entrée qui sera elle-même un programme attendant une entrée), lance le programme p sur le programme s(s) (c'est-à-dire s lancé avec lui-même comme argument), et qui ensuite change le résultat si c'est une des deux options (i.e., échange U et V).
Alors q est le programme r(r).
Cette définition n'est pas auto-référente. Et en la déroulant, on voit que q fait bien ce que j'ai dit : il lance le programme p sur le programme q, et ensuite change le résultat si c'est une des deux options (i.e., échange U et V).
Encore une fois, si cette explication a semblé trop rapide, je renvoie à cette page sur les quines pour une explication détaillée. Mais la morale de l'histoire c'est qu'il est tout à fait légitime de définir un programme qui fait appel à lui-même dans sa définition (certains langages de programmation l'autorisent même explicitement, mais la construction ci-dessus montre qu'on peut le faire même si ce n'est pas explicitement prévu).
Bref, ceci résout la question de l'indication. Maintenant reste à résoudre celle de l'énigme de départ.
La réponse à l'énigme
Pour résoudre l'ensemble de l'énigme, on va faire pareil que pour l'indication, avec chacune des trois portes, et faire tourner tout ça en parallèle.
Plus exactement :
On définit qA comme le programme qui lance le programme pA sur le programme qA lui-même et qui ensuite change le résultat si c'est une des deux autres portes (i.e., échange B et C). Ainsi, par définition, la sortie de qA est la sortie de pA(qA) (si ce dernier termine) avec B et C échangés.
Et on fait de même pour les deux autres portes. C'est-à-dire que qB lance pB sur qB lui-même et qui ensuite échange C et A, tandis que qC lance pC sur qC lui-même et qui ensuite échange A et B.
La manière dont un programme fait référence à lui-même dans sa définition a été expliquée ci-dessus et ne pose pas de problème.
Au bout du compte, on lance en parallèle pA sur qA, pB sur qB et pC sur qC, et on attend que l'un d'entre eux termine en renvoyant l'étiquette d'une des deux autres portes. Ceci se produira forcément parce que le programme de la porte du dragon est garanti toujours terminer, quelle que soit l'entrée qu'on lui passe, et renvoyer l'étiquette d'une des deux autres portes. Il se peut qu'un autre programme termine, mais ce n'est pas grave : il ne renverra jamais l'étiquette de la porte du dragon.
En effet, appelons X la porte au dragon, et Y,Z les deux autres portes. Le programme pX lancé sur n'importe quoi est garanti renvoyer Y ou Z. Le programme pY est garanti renvoyer Z à condition que son entrée renvoie Z ; si pY(qY) renvoyait X, alors qY renverrait Z (puisqu'il échange les options Z et X), donc pY(qY) renverrait Z par l'hypothèse qui a été faite sur pY — une contradiction ; bref, pY(qY) ne peut pas renvoyer X (il peut renvoyer Z ou tout autre chose, y compris ne jamais terminer, mais en tout cas pas renvoyer X). De façon exactement symétrique, pZ(qZ) ne peut pas renvoyer X. Donc au final on a lancé trois programmes en parallèle : l'un renverra Y ou Z, et les deux autres ne peuvent pas renvoyer X. Il suffit donc d'attendre le premier qui termine et renvoie l'une des trois étiquettes X,Y,Z, et ce sera forcément Y ou Z, c'est-à-dire une porte sûre.
Ajout/suite
() : cette
entrée ultérieure (et
spécifiquement ce
passage) révèle le rapport que l'énigme posée dans le présent
billet a avec la formule
((¬¬A⇔(¬B∧¬C)) ∧
(¬¬B⇔(¬C∧¬A)) ∧
(¬¬C⇔(¬A∧¬B))
∧
((¬A⇒(¬B∨¬C)) ⇒
(¬B∨¬C)) ∧
((¬B⇒(¬C∨¬A)) ⇒
(¬C∨¬A)) ∧
((¬C⇒(¬A∨¬B)) ⇒
(¬A∨¬B))) ⇒ (¬A ∨ ¬B ∨
¬C) et ce qu'elle nous apprend sur elle.