summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20190205.tex28
1 files changed, 28 insertions, 0 deletions
diff --git a/controle-20190205.tex b/controle-20190205.tex
index 8accd7f..39f5c07 100644
--- a/controle-20190205.tex
+++ b/controle-20190205.tex
@@ -366,6 +366,34 @@ On pouvait aussi donner, entre autres choses :
(obtenue en éliminant les états $1$ et $2$ avant $\bot$).
\end{corrige}
+
+%
+%
+%
+
+\exercice
+
+On rappelle la définition du problème de l'arrêt : c'est l'ensemble
+$H$ des couples\footnote{Pour être rigoureux, on a fixé un codage
+ permettant de représenter les programmes $e$, les entrées $x$ à ces
+ programmes, et les couples $(e,x)$, comme des éléments
+ de $\mathbb{N}$ (ou bien de $\Sigma^*$ sur un alphabet
+ $\Sigma\neq\varnothing$ arbitraire). Il n'est pas nécessaire de
+ faire apparaître ce codage dans la description des algorithmes
+ proposés, qui peut rester informelle.} $(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 a vu en
+cours que $H$ était semi-décidable mais non décidable.
+
+On considère l'ensemble $H'$ des triplets $(e_1,e_2,x)$ tels que
+$(e_1,x) \in H$ \emph{ou bien} $(e_2,x) \in H$ (ou les deux).
+Autrement dit, au moins l'un des programmes $e_i$ termine en temps
+fini quand on l'exécute sur l'entrée $x$.
+
+(1) Montrer que $H'$ est semi-décidable.
+
+(2) Montrer que $H'$ n'est pas décidable.
+
%
%
%