Final exercise (computability).

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}
+
+
 
 %
 %