Write answers to third exercise.

1 files changed, 68 insertions, 10 deletions

diff --git a/controle-20180206.tex b/controle-20180206.tex
index be3a599..bfc0fa7 100644
--- a/controle-20180206.tex
+++ b/controle-20180206.tex
@@ -506,13 +506,28 @@ qui, prenant en entrée un élément $x$ de $\mathbb{N}$ :
   imposé si $x\not\in L\cup M$).
 \end{itemize}
 
-(2) Expliquer pourquoi deux langages $L,M$ disjoints sont
-calculablement séparables si et seulement si il existe deux langages
-$E,F$ \emph{décidables disjoints} tels que $L \subseteq E$ et $M
-\subseteq F$.
+\begin{corrige}
+Si $E$ est décidable tel que $L \subseteq E$ et $M \subseteq
+(\mathbb{N}\setminus E)$, alors un algorithme qui décide $E$
+(c'est-à-dire, quand on lui fournit l'entrée $x$, répond « vrai » si
+$x\in E$, et « faux » si $x \not\in E$) répond bien aux critères
+demandés.  Réciproquement, donné un algorithme qui répond aux critères
+demandés, si $E$ est l'ensemble des $x$ sur lesquels il répond
+« vrai », alors $E$ est bien décidable (on peut toujours modifier
+l'algorithme si nécessaire pour qu'il ne réponde que « vrai » ou
+« faux »), et on a $L \subseteq E$ et $M \subseteq
+(\mathbb{N}\setminus E)$.
+\end{corrige}
+
+(2) Expliquer pourquoi deux langages \emph{décidables} disjoints sont
+toujours calculablement séparables.
 
-(3) Deux langages décidables disjoints peuvent-ils être calculablement
-inséparables ?
+\begin{corrige}
+Si $L,M$ sont décidables disjoints, on peut poser $E = L$, qui est
+décidable et vérifie à la fois $L \subseteq E$ (trivialement) et $M
+\subseteq (\mathbb{N}\setminus E)$ (c'est une reformulation du fait
+que $M$ est disjoint de $E=L$).
+\end{corrige}
 
 On cherche maintenant à montrer qu'il existe deux langages $L,M$
 \emph{semi-décidables} disjoints et calculablement inséparables.
@@ -532,18 +547,61 @@ deux éléments distincts quelconques de $\mathbb{N}$ : si on a souhaité
 remplacer $\mathbb{N}$ par $\Sigma^*$, on peut prendre deux mots
 distincts quelconques, par exemple $a$ et $aa$.)
 
-(4) Pourquoi $L$ et $M$ sont-ils disjoints ?
+(3) Pourquoi $L$ et $M$ sont-ils disjoints ?
 
-(5) Pourquoi $L$ et $M$ sont-ils semi-décidables ?
+\begin{corrige}
+Comme $L$ est l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) =
+1$ et $M$ l'ensemble des couples $(e,x)$ tels que $\varphi_e(x) = 2$,
+aucun couple ne peut appartenir aux deux, c'est-à-dire qu'ils sont
+disjoints.
+\end{corrige}
 
-(6) En calquant la démonstration du théorème de Turing sur
+(4) Pourquoi $L$ et $M$ sont-ils semi-décidables ?
+
+\begin{corrige}
+Pour semi-décider si un couple $(e,x)$ appartient à $L$, il suffit de
+lancer l'exécution du programme $e$ sur l'entrée $x$ et, si elle
+termine en retournant $1$, renvoyer « vrai », tandis que si elle
+termine en renvoyant n'importe quelle autre valeur, faire une boucle
+infinie (bien sûr, si le programme $e$ ne termine jamais sur
+l'entrée $x$, on ne termine pas non plus).  Ceci montre que $L$ est
+semi-décidable.  Le même raisonnement s'appliquer pour $M$.
+\end{corrige}
+
+(5) En imitant la démonstration du théorème de Turing sur
 l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun
 algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours
 en temps fini et répond « vrai » si $(e,x)\in L$ et « faux » si $(e,x)
 \in M$ (indication : si un tel algorithme existait, on pourrait s'en
 servir pour faire le contraire de ce qu'il prédit).
 
-(7) Conclure.
+\begin{corrige}
+Montrons par l'absurde qu'il n'existe aucun algorithme $T$ comme
+annoncé.  Définissons un nouvel algorithme $T'$ qui, donné un
+entier $e$, effectue les calculs suivants : (1º) interroger
+l'algorithme $T$ (supposé exister !) en lui fournissant le couple
+$(e,e)$ comme entrée, et ensuite (2º) s'il répond vrai, renvoyer la
+valeur $2$, tandis que s'il répond n'importe quoi d'autre, renvoyer la
+valeur $1$.  L'algorithme $T'$ qui vient d'être décrit aurait un
+certain numéro, disons, $p$, et la description de l'algorithme fait
+qu'il termine toujours, que la valeur $\varphi_p(e)$ qu'il renvoie
+vaut toujours soit $1$ soit $2$, et qu'elle vaut $2$ si $(e,e) \in L$
+(c'est-à-dire si $\varphi_e(e) = 1$) et $1$ si $(e,e) \in M$
+(c'est-à-dire si $\varphi_e(e) = 2$).  En particulier, en prenant
+$e=p$, on voit que $\varphi_p(p)$ doit valoir $1$ ou $2$, doit valoir
+$2$ si $\varphi_p(p) = 1$ et $1$ si $\varphi_p(p) = 2$, ce qui est une
+contradiction.
+\end{corrige}
+
+(6) Conclure.
+
+\begin{corrige}
+La question (5) montre (compte tenu de la question (1)) que $L$ et $M$
+ne sont pas calculablement séparables, i.e.., sont calculablement
+inséparables, tandis que (4) et (5) montrent que $L$ et $M$ sont
+disjoints et semi-décidables.  On a donc bien montré l'existence de
+langages semi-décidables disjoints et calculablement inséparables.
+\end{corrige}