diff options
| -rw-r--r-- | exercices-inf110.tex | 72 |
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} + % % |