diff options
| -rw-r--r-- | controle-20190205.tex | 23 |
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} + % % % |