From dde7a775ea3a9c358cb25e74c3f87a977e91df9d Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 17 Jan 2019 00:55:19 +0100
Subject: A very silly exercise on computability.

---
 controle-20190205.tex | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

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.
+
 %
 %
 %
-- 
cgit v1.2.3