From 4e8470a836b06bdef26c59d11385781ae53e6cee Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 11 Jan 2024 18:23:53 +0100 Subject: Dragon riddle. --- exercices-inf110.tex | 109 ++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 108 insertions(+), 1 deletion(-) 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 @@ -3002,6 +3002,113 @@ sémantique des ouverts) elle ne peut pas être démontrable. \end{corrige} +% +% +% + +\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} + + % % % -- cgit v1.2.3