1 files changed, 38 insertions, 3 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex
index 7054af5..90fda16 100644
--- a/controle-20170330.tex
+++ b/controle-20170330.tex
@@ -482,8 +482,18 @@ 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.
+(2) Montrer que $H'$ n'est pas décidable : pour cela, on pourra,
+\emph{au choix} :
+\begin{itemize}
+\item montrer directement que $H'$ n'est pas décidable, en imitant la
+  démonstration du cours que $H$ n'est pas décidable (on pourra
+  essayer de construire un programme qui contredit la prédiction faite
+  par $H'$ sur son comportement), \emph{ou bien}
+\item montrer que si $H'$ était décidable, $H$ le serait aussi, ce qui
+  constitue une contradiction (donné un programme $e$, on pourra
+  modifier celui-ci en un programme $e'$ de manière à rendre utile la
+  prédiction faite par $H'$ sur son comportement).
+\end{itemize}
 
 \begin{corrige}
 (1) Le fait que $H'$ soit semi-décidable se montre de la même manière
@@ -498,7 +508,32 @@ montrer que s'il l'était, $H$ le serait aussi.
 
 \smallbreak
 
-(2) Supposons par l'absurde que $H'$ soit décidable (c'est-à-dire,
+(2) Donnons deux solutions, correspondant aux deux approches suggérées
+par l'énoncé.
+
+\emph{Première approche} (montrer directement que $H'$ n'est pas
+décidable) :
+
+Si $H'$ était décidable, on pourrait définir un algorithme qui, donné
+un programme $e$, effectue les calculs suivants : (1º) utiliser un
+algorithme décidant $H'$ (on a supposé qu'il en existe un) pour
+savoir, algorithmiquement en temps fini, si le programme $e$ termine
+et renvoie $42$ quand on lui passe son propre numéro $e$ en entrée, et
+(2º) si oui, terminer en renvoyant la valeur $43$ (disons), et si non,
+terminer en renvoyant $42$.  L'algorithme qui vient d'être décrit
+correspond à un certain programme, disons, $p$, et la description de
+l'algorithme fait que, quelque soit $e$, la valeur renvoyée par $p$
+sur $e$ vaut $43$ si celle renvoyée par $e$ sur $e$ vaut $42$, et vaut
+$42$ sinon (y compris si $e$ ne termine pas sur l'entrée $e$).  En
+particulier, en prenant $e=p$, on voit que la valeur renvoyée par $p$
+sur $p$ vaut $42$ si et seulement si elle ne vaut pas $42$, ce qui est
+une contradiction.  C'est donc que $H'$ n'était, en fait, pas
+décidable.
+
+\emph{Seconde approche} (ramener l'indécidabilité de $H'$ à celle
+de $H$) :
+
+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$