An exercise that will be used as a lemma for a later exercise.

1 files changed, 72 insertions, 0 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index f483a19..f979796 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -1166,6 +1166,78 @@ l'existence d'ensembles semi-décidables disjoints et calculablement
 inséparables.
 \end{corrige}
 
+%
+
+\exercice\ (${\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
+« bon » choix et l'autre est le « mauvais » choix, mais on ignore
+lequel est lequel.
+
+On dispose d'un programme $p$ ayant la propriété garantie suivante :
+si on fournit en entrée à $p$ un programme $q$ (ne prendant, lui,
+aucune entrée) qui termine et renvoie le bon choix, alors $p$ lui
+aussi termine et renvoie le bon choix.  (En revanche, si $q$ fait
+autre chose que renvoyer le bon choix, que ce soit parce qu'il ne
+termine pas, parce qu'il renvoie le mauvais choix, ou qu'il renvoie
+autre chose que $X$ ou $Y$, alors $p$ appelé sur $q$ peut faire
+n'importe quoi, y compris ne pas terminer, renvoyer le mauvais choix,
+ou renvoyer autre chose que $X$ ou $Y$.)
+
+\textbf{(1)} Expliquer comment construire un programme $q$ tel que $p$
+appelé sur l'entrée $q$ \emph{ne peut pas renvoyer le mauvais choix}
+(il se peut qu'il ne termine pas, ou qu'il renvoie autre chose que
+$X$ ou $Y$, mais il ne peut pas terminer et renvoyer la mauvais
+choix).
+
+(\emph{Indication :} utiliser l'astuce de Quine, c'est-à-dire le
+théorème de récursion de Kleene, en s'inspirant d'une démonstration de
+l'indécidabilité du problème de l'arrêt ou du théorème de Rice.)
+
+\textbf{(2)} Expliquer pourquoi il n'y a pas moyen, avec le $p$ qu'on
+nous a fourni, mais sans connaître le bon choix, de faire un programme
+qui termine à coup sûr et renvoie le bon choix.
+
+(\emph{Indication :} raisonner par symétrie en proposant un $p$ qui
+marchera quel que soit le bon choix.)
+
+\begin{corrige}
+\textbf{(1)} On construit le programme $q$ suivant : il invoque le
+programme $p$ sur $q$ lui-même et ensuite, si $p$ termine et renvoie
+$X$ ou $Y$, il échange $X$ et $Y$ (autrement dit, si $p$ appelé sur
+$q$ renvoie $X$, alors il renvoie $Y$, et si $p$ appelé sur $q$
+renvoie $Y$, alors il renvoie $X$), tandis que dans tout autre cas il
+fait une boucle infinie.  La construction de ce $q$, et notamment le
+fait que $q$ fasse appel à lui-même dans sa définition, est justifiée
+par l'astuce de Quine (formellement : si on note $\varphi_p(q)$ le
+résultat du programme $p$ invoqué sur $q$, on appelle $h$ la fonction
+qui à $q$ associe $X$ si $\varphi_p(q) = Y$ et $Y$ si $\varphi_p(q) =
+X$ et $\uparrow$ dans tout autre cas, alors $h$ est calculable, donc
+par le théorème de récursion de Kleene, il existe $q$ tel que le
+résultat $\varphi_q(0)$ de $q$ soit $h(q)$).
+
+Alors le résultat de $p$ invoqué sur $q$ ne peut pas être le mauvais
+choix, car si c'était le mauvais choix, $q$ tout seul renverrait le
+bon choix (par construction de $q$), donc $p$ invoqué sur $q$
+renverrait le bon choix (par la garantie fournie sur $p$), ce qui est
+une contradiction.
+
+\textbf{(2)} Considérons le programme $p$ qui prend en entrée un
+programme $q$, l'exécute (sans argument) et renvoie son résultat.
+Cette opération est bien algorithmique d'après l'existence d'une
+machine universelle.  Or le programme ainsi défini répond à la
+garantie exigée de $p$ : si $q$ termine en renvoyant le bon choix,
+alors $p$ appelé avec $q$ en argument termine aussi en renvoyant le
+bon choix.  Comme ce programme ne dépend pas de l'identité du bon
+choix (qui peut encore être $X$ ou $Y$), il ne permet pas de trancher
+entre les deux : il est donc impossible de s'en servir pour faire un
+programme qui termine à coup sûr et renvoie le bon choix.  (Plus
+exactement, si on avait un tel moyen de faire, ce moyen devrait
+s'appliquer encore quand on échange $X$ et $Y$, ce qui contredit le
+fait qu'il renvoie toujours le bon choix.)
+\end{corrige}
+
 
 %
 %