Answers to exercise about computability.

1 files changed, 23 insertions, 0 deletions

diff --git a/controle-20190205.tex b/controle-20190205.tex
index 41ce6d2..166bb33 100644
--- a/controle-20190205.tex
+++ b/controle-20190205.tex
@@ -392,8 +392,31 @@ fini quand on l'exécute sur l'entrée $x$.
 
 (1) Montrer que $H'$ est semi-décidable.
 
+\begin{corrige}
+Considérons l'algorithme suivant : donné en entrée un triplet
+$(e_1,e_2,x)$, on exécute en parallèle, en fournissant à chacun
+l'entrée $x$, les programmes (codés par) $e_1$ et $e_2$ (au moyen
+d'une machine universelle), et en s'arrêtant immédiatement si l'un des
+deux s'arrête, et on renvoie alors « vrai ».  Manifestement, cet
+algorithme termine (en renvoyant « vrai ») si et seulement si
+$(e_1,e_2,x) \in H'$, ce qui montre que $H'$ est semi-décidable.
+\end{corrige}
+
 (2) Montrer que $H'$ n'est pas décidable.
 
+\begin{corrige}
+Supposons par l'absurde qu'il existe un algorithme $T$ qui
+décide $H'$.  Soit $e'$ (le code d')un programme quelconque qui
+effectue une boucle infinie (quelle que soit son entrée) : comme $e'$
+ne termine jamais, un triplet $(e,e',x)$ appartient à $H'$ si et
+seulement si $(e,x)$ appartient à $H$.  Considérons maintenant
+l'algorithme suivant : donné en entrée un couple $(e,x)$, on applique
+l'algorithme $T$ supposé exister pour décider si $(e,e',x) \in H'$ ;
+comme on vient de l'expliquer, ceci équivaut à $(e,x) \in H$.  On a
+donc fabriqué un algorithme qui décide $H$, ce qui est impossible,
+d'où la contradiction annoncée.
+\end{corrige}
+
 %
 %
 %