diff options
| -rw-r--r-- | controle-20170330.tex | 72 |
1 files changed, 69 insertions, 3 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex index 1c50166..db38fc7 100644 --- a/controle-20170330.tex +++ b/controle-20170330.tex @@ -34,6 +34,7 @@ % \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax} % % \DeclareFontFamily{U}{manual}{} @@ -107,12 +108,13 @@ L'usage des appareils électroniques est interdit. Durée : 1h30 -Barème \emph{indicatif} : +Barème \emph{indicatif} : $8$ points pour chacun des deux premiers +exercices, $4$ pour l'exercice 3. \ifcorrige -%Ce corrigé comporte 10 pages (page de garde incluse) +%Ce corrigé comporte 7 pages (page de garde incluse) \else -%Cet énoncé comporte 4 pages (page de garde incluse) +Cet énoncé comporte 3 pages (page de garde incluse) \fi \pagebreak @@ -455,6 +457,70 @@ semi-décidable ?&oui&oui&oui&oui&oui\\ \end{corrige} +% +% +% + +\exercice + +On rappelle que le \emph{problème de l'arrêt} $H$ est l'ensemble des +couples $(e,x)$ formés d'un programme (=algorithme) $e$ et d'une +entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$ +termine en temps fini (on peut éventuellement noter cela : +$\varphi_e(x)\downarrow$). On rappelle que le problème de l'arrêt $H$ +est semi-décidable mais non décidable (autrement dit, on ne peut pas +décider à l'avance en temps fini si un programme $e$ donné va terminer +sur une entrée $x$, mais on peut au moins vérifier que c'est le cas +quand ça l'est). + +On définit ici la variante $H'$ suivante du problème de l'arrêt : $H'$ +est l'ensemble des couples $(e,x)$ formés d'un programme $e$ et d'une +entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$ +termine en temps fini et renvoie la réponse $42$ (si on veut : +$\varphi_e(x) = 42$). Ainsi, on a $H' \subseteq H$ (ce fait est +destiner à éclaircir la définition de $H'$ mais n'est pas utile pour +la suite). + +(1) Montrer que $H'$ est semi-décidable. + +(2) Montrer que $H'$ n'est pas décidable (pour cela, on cherchera à +montrer que s'il l'était, $H$ le serait aussi). + +\begin{corrige} +(1) Le fait que $H'$ soit semi-décidable se montre de la même manière + que le fait que $H$ l'est : donnés un programme $e$ et une entrée + $x$, on lance l'exécution de $e$ sur l'entrée $x$ (au moyen, si on + veut être précis, d'une « machine universelle »), et si cette + exécution termine et renvoie la valeur $42$, on renvoie « vrai », + sinon on rentre dans une boucle infinie (ou on renvoie « faux », peu + importe) ; bien sûr, si l'exécution de $e$ sur $x$ ne termine pas, + l'algorithme qu'on vient de décrire ne terminera pas non plus. Au + final, on a bien décrit un algorithme qui semi-décide $H'$. + +\smallbreak + +(2) Supposons par l'absurde que $H'$ soit décidable (c'est-à-dire, +concrètement, qu'on dispose d'un moyen de savoir si un programme $e$, +quand on lui fournit une entrée $x$, termine en renvoyant la +valeur $42$) et montrons, pour arriver à une contradiction, que $H$ +l'est aussi. + +Donnés un programme $e$ et une entrée $x$, on peut construire +\emph{algorithmiquement} le programme $e'$ suivant : il effectue les +mêmes opérations que $e$, mais, à la fin, ignore le résultat calculé, +et renvoie toujours $42$. Ainsi, l'exécution de $e'$ sur l'entrée $x$ +termine et renvoie $42$ si et seulement si celle de $e$ sur cette même +entrée termine (et renvoie n'importe quoi) : si on veut, +$\varphi_{e'}(x)=42 \liff \varphi_e(x)\downarrow$. On peut alors +utiliser $H'$ — supposé décidable — pour décider si $e'$ termine (sur +l'entrée $x$) en renvoyant $42$ : comme ceci revient au même que de +savoir si $e$ termine (sur l'entrée $x$), ceci fournit un moyen pour +savoir si $e$ termine (sur l'entrée $x$). Autrement dit, on a résolu +algorithmiquement le problème de l'arrêt, ce qui est une +contradiction. C'est donc que $H'$ n'était, en fait, pas décidable. +\end{corrige} + + % % |