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