Write answers to third exercise.

1 files changed, 37 insertions, 0 deletions

diff --git a/controle-20210618.tex b/controle-20210618.tex
index 7cea2b2..585b9c1 100644
--- a/controle-20210618.tex
+++ b/controle-20210618.tex
@@ -527,6 +527,18 @@ algébrique\footnote{Ce fait est démontré dans le poly, dans la section
   redémontrer.}.  Est-il rationnel ?  Est-il décidable ?  Est-il
 semi-décidable ?  On justifiera soigneusement les réponses.
 
+\begin{corrige}
+Le langage proposé n'est pas rationnel car il n'est pas algébrique.
+
+Il est décidable car il est évident qu'on peut algorithmiquement
+vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci
+correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable
+par automate fini) puis vérifier qu'il a autant de $a$ que de $b$ que
+de $c$.
+
+Étant décidable, il est notamment semi-décidable.
+\end{corrige}
+
 \smallskip
 
 (2) On rappelle la définition du problème de l'arrêt : c'est
@@ -548,6 +560,31 @@ le programme $e_2$, lui, ne termine pas sur cette même entrée.
 L'ensemble $J$ est-il décidable ?  Semi-décidable ?  On justifiera
 soigneusement.
 
+\begin{corrige}
+L'ensemble $J$ n'est pas semi-décidable.  En effet, supposons par
+l'absurde qu'on dispose d'un algorithme $T$ qui semi-décide $J$ (où
+« semi-décider » un ensemble $Z$ signifie : terminer en renvoyant $1$
+(=vrai) si l'entrée $z$ fournie appartient à $Z$, et ne pas terminer
+sinon).  Fixons une fois pour toutes $f$ (le code d')un programme qui,
+donnée une entrée $x$, termine immédiatement (en ignorant $x$).  Alors
+trivialement $(f,x) \in H$ quel que soit $x$ ; donc, par définition
+de $J$, on a $(f,e,x) \in J$ si et seulement si $(e,h) \not \in H$.
+On dispose alors d'un algorithme $T'$ qui semi-décide le
+complémentaire de $H$, défini de la manière suivante : donnés $(e,x)$,
+on applique l'algorithme $T$ (qu'on a supposé exister) au triplet
+$(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in J$), on
+renvoie $1$ (sinon, bien sûr, on ne termine jamais) ; par
+construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si
+$(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne
+termine pas ; ceci signifie justement que $T'$ semi-décide le
+complémentaire de $H$.  Or le complémentaire de $H$ n'est pas
+semi-décidable (car si le complémentaire de $H$ était semi-décidable,
+on aurait à la fois $H$ et son complémentaire semi-décidables, donc
+$H$ serait décidable, et on sait qu'il ne l'est pas).  C'est une
+contradiction : $J$ n'est donc pas semi-décidable.  \textit{A
+  fortiori}, $J$ n'est pas décidable.
+\end{corrige}
+
 
 %
 %