Dragon riddle.

1 files changed, 108 insertions, 1 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index aa1b1b5..9e32802 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -1168,7 +1168,7 @@ inséparables.
 
 %
 
-\exercice\ (${\star}{\star}{\star}$)\par\nobreak
+\exercice\label{exercise-good-bad-choice-lemma}\ (${\star}{\star}{\star}$)\par\nobreak
 
 Dans cet exercice, on suppose qu'on doit faire un choix entre deux
 options qu'on appelera « $X$ » et « $Y$ ».  L'un de ces choix est le
@@ -3005,4 +3005,111 @@ sémantique des ouverts) elle ne peut pas être démontrable.
 %
 %
 %
+
+\section{Divers}
+
+\exercice\ (${\star}{\star}{\star}{\star}{\star}$)\par\nobreak
+
+Vous êtes dans un donjon.  Devant vous se trouvent trois portes,
+étiquetées $A,B,C$.  Derrière l'une de ces trois portes, mais vous ne
+savez pas laquelle, se trouve un dragon, qui vous dévorera si vous
+l'ouvrez ; les deux autres portes, qu'on appellera « sûres » dans la
+suite mènent à la sortie du donjon (avec un trésor à la clé).  Votre
+but est d'ouvrir une porte sûre (peu importe laquelle).
+
+Sur chaque porte est affiché un programme ($p_A,p_B,p_C$) qui
+constitue un indice pour trouver une porte sûre.  Plus précisément, le
+programme affiché sur chaque porte prend une entrée $q$ et va,
+\emph{sous certaines conditions} terminer et renvoyer l'étiquette
+d'une des deux autres portes qui soit sûre.  Plus exactement, si on
+suppose que $X$ est l'étiquette de la porte avec le dragon :
+\begin{itemize}
+\item Le programme $p_X$ qui est affiché sur la porte au dragon va
+  \emph{toujours} terminer (quelle que soit l'entrée $q$ qu'on lui a
+  passée) et renvoyer l'étiquette d'une des deux autres portes $Y,Z$
+  (qui sont toutes les deux sûres puisqu'il n'y a qu'un seul dragon) :
+  $\varphi_{p_X}(q) {\downarrow} \in \{Y,Z\}$ quel que soit $q$ (mais
+  noter que le résultat peut dépendre de $q$).
+\item Le programme $p_Y$ qui est affiché sur une porte sûre $Y$ va
+  terminer et renvoyer l'étiquette de l'autre porte sûre $Z$, mais
+  \emph{à condition} qu'on lui ait passé comme argument un programme
+  $q$ (sans argument) qui fasse exactement ça (i.e., à condition que
+  $q$ lui-même termine et renvoie $Z$) : si
+  $\varphi_{q}(0){\downarrow} = Z$ alors\footnote{Le $0$ est mis pour
+  une absence d'argument.}  $\varphi_{p_Y}(q) {\downarrow} = Z$ (dans
+  tout autre cas, on n'a aucune garantie sur $\varphi_{p_Y}(q)$ : il
+  pourrait ne pas terminer, renvoyer une étiquette fausse, ou renvoyer
+  complètement autre chose).
+\end{itemize}
+
+Comment pouvez-vous utiliser ces indications pour ouvrir (de façon
+certaine, et même algorithmique d'après $p_A,p_B,p_C$) une porte
+sûre ?
+
+(\emph{Indication :} on pourra utiliser
+l'exercice \ref{exercise-good-bad-choice-lemma}(1).)
+
+Question subsidiaire (indépendante) : montrer que l'énigme ci-dessus
+serait insoluble si au lieu d'avoir des \emph{programmes} affichés sur
+les portes on avait des tableaux de valeurs (tableaux donnant un
+résultat « $A$ », « $B$ », « $C$ » ou n'importe quoi en fonction d'une
+entrée « $A$ », « $B$ » ou « $C$ ») avec les mêmes contraintes (i.e. :
+le tableau sur la porte du dragon donne l'étiquette d'une des deux
+autres portes quelle que soit l'entrée, et le tableau sur une porte
+sûre donne l'étiquette de l'autre porte sûre si l'entrée est justement
+l'étiquette de l'autre porte sûre).
+
+\begin{corrige}
+Traitons d'abord la question subsidiaire.  Si les tableaux sont les
+suivants :
+\[
+\begin{array}{c@{\hskip 2em}c@{\hskip 2em}c}
+p_A[A] = B & p_A[B] = B & p_A[C] = C\\
+p_B[A] = A & p_B[B] = C & p_B[C] = C\\
+p_C[A] = A & p_C[B] = B & p_C[C] = A\\
+\end{array}
+\]
+alors chacun des tableaux vérifie les deux contraintes (il renvoie
+toujours l'étiquette d'une des deux autres portes, et si on le
+consulte sur l'étiquette d'une des deux autres portes, il renvoie
+celle-ci) ; or ces tableaux sont complètement symétriques (ils sont
+invariants par les permutations cycliques de $A,B,C$) donc ils ne
+peuvent pas permettre de déduire l'information de l'emplacement du
+dragon qui pourrait être derrière n'importe quelle porte.
+
+Il s'agit donc de faire quelque chose avec les programmes qu'on ne
+peut pas faire avec de simples tableaux.  Ceci suggère d'utiliser le
+théorème de récursion de Kleene.
+
+En s'inspirant de l'exercice \ref{exercise-good-bad-choice-lemma}(1),
+si $Z$ est une des trois portes et $X,Y$ les deux autres, on va
+définir le programme $q_Z$ suivant : il invoque le programme $p_Z$ sur
+$q_Z$ lui-même et ensuite, si $p_Z$ termine et renvoie $X$ ou $Y$, il
+échange $X$ et $Y$ (autrement dit, si $p_Z$ appelé sur $q_Z$ renvoie
+$X$, alors il renvoie $Y$, et si $p_Z$ appelé sur $q_Z$ renvoie $Y$,
+alors il renvoie $X$), tandis que dans tout autre cas il fait une
+boucle infinie.  La construction de ce $q_Z$, et notamment le fait que
+$q_Z$ fasse appel à lui-même dans sa définition, est justifiée par
+l'astuce de Quine.  Si $Z$ est la porte au dragon, alors, d'après les
+garanties qu'on a reçues, $p_Z$ invoqué sur $q_Z$ va forcément
+terminer et renvoyer une des étiquettes $X,Y$ (les deux sont sûres).
+Si $Z$ est une porte sûre, mettons pour fixer les idées que $X$ soit
+la porte au dragon : alors $p_Z$ invoqué sur $q_Z$ ne peut pas
+renvoyer $X$, car si tel était le cas, $q_Z$ renverrait $Y$ (puisqu'il
+échange les deux réponses $X,Y$), et par les garanties qu'on a reçues,
+$p_Z$ invoqué sur $q_Z$ doit renvoyer $Y$, contradiction.
+
+Maintenant, on lance en parallèle $p_A$ sur $q_A$, $p_B$ sur $q_B$, et
+$p_C$ sur $q_C$. D'après ce qui a été dit au paragraphe précédent,
+aucun des trois ne peut renvoyer l'étiquette de la porte du dragon, et
+l'un des trois (celui de la porte du dragon) devra finir par renvoyer
+l'étiquette d'une porte sûre.  Il suffit donc d'attendre que l'un des
+trois termine et renvoie une étiquette dans $\{A,B,C\}$, et, quand ça
+se produit, ouvrir la porte en question.
+\end{corrige}
+
+
+%
+%
+%
 \end{document}