summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-01-16 23:55:19 (GMT)
committerDavid A. Madore <david+git@madore.org>2019-01-23 12:47:10 (GMT)
commitdde7a775ea3a9c358cb25e74c3f87a977e91df9d (patch)
tree6516a1aac1307e9ec81be90c3369f98f08aafc1b
parentb79f37267c7b256cdbd19ba5564e11c1d166973f (diff)
downloadinf105-dde7a775ea3a9c358cb25e74c3f87a977e91df9d.zip
inf105-dde7a775ea3a9c358cb25e74c3f87a977e91df9d.tar.gz
inf105-dde7a775ea3a9c358cb25e74c3f87a977e91df9d.tar.bz2
A very silly exercise on computability.
-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.
+
%
%
%