summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-01-18 22:24:33 (GMT)
committerDavid A. Madore <david+git@madore.org>2019-01-23 12:47:10 (GMT)
commit759fe9dbf1a3a59929b3f4762938c46a6d7ab2ab (patch)
tree12a9c697e5b596d8b33f500af9ed0103779043ae
parent6293ae6685fb45a014e52efc131352ba05c2c546 (diff)
downloadinf105-759fe9dbf1a3a59929b3f4762938c46a6d7ab2ab.zip
inf105-759fe9dbf1a3a59929b3f4762938c46a6d7ab2ab.tar.gz
inf105-759fe9dbf1a3a59929b3f4762938c46a6d7ab2ab.tar.bz2
Answers to exercise about computability.
-rw-r--r--controle-20190205.tex23
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}
+
%
%
%