Add an exercise on computability.

1 files changed, 131 insertions, 0 deletions

diff --git a/controle-20170207.tex b/controle-20170207.tex
index ac9d9ca..81fea55 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -400,6 +400,137 @@ qui vérifie cette propriété suivi d'un suffixe quelconque.
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+Soit $\Sigma$ un alphabet (fini, non vide) fixé.  Les questions
+suivantes sont indépendantes.
+
+(1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe
+un algorithme $A_1$ qui, donnée une expression rationnelle $r$
+sur $\Sigma$, décide si le langage $L_r$ dénoté par $r$ est différent
+du langage $\Sigma^*$ de tous les mots sur $\Sigma$.  (Autrement dit,
+l'algorithme $A_1$ doit prendre en entrée une expression rationnelle
+$r$, terminer en temps fini, et répondre « vrai » s'il existe un mot
+$w\in\Sigma^*$ tel que $w\not\in L_r$ et « faux » si $L_r = \Sigma^*$.
+On ne demande pas que l'algorithme soit efficace.)
+
+(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, donnée une
+grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le
+langage $L_G$ engendré par $G$ est différent du langage $\Sigma^*$ de
+tous les mots.  (« Semi-décider » signifie que l'algorithme $A_2$ doit
+prendre en entrée une grammaire hors contexte $G$, terminer en temps
+fini en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que
+$w\not\in L_G$, et ne pas terminer — ou éventuellement terminer en
+répondant « faux » — si $L_G = \Sigma^*$.)  Indication : on peut
+tester tous les mots possibles.
+
+(3) Expliquer pourquoi il existe un tel algorithme $A_3$ : on lui
+fournit en entrée un algorithme $T$ qui décide un langage $L_T
+\subseteq \Sigma^*$ (c'est-à-dire que $T$ termine toujours en temps
+fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou
+« faux », et $L_T$ est le langage des mots sur lesquels il répond
+« vrai »), et l'algorithme $A_3$ doit semi-décider si $L_T$ est
+différent de $\Sigma^*$.  (C'est-à-dire que $A_3$ doit terminer en
+répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in
+L_T$, et ne pas terminer — ou éventuellement terminer en répondant
+« faux » — si $L_T = \Sigma^*$.)  Indication : la même approche permet
+de traiter les questions (2) et (3).
+
+(4) Expliquer pourquoi il n'existe pas d'algorithme $A_4$ qui, dans
+les mêmes conditions que $A_3$, décide (au lieu de seulement
+semi-décider) si $L_T$ est différent de $\Sigma^*$.  (C'est-à-dire que
+$A_4$ est censé terminer toujours, et répondre « vrai » s'il existe un
+mot $w\in\Sigma^*$ tel que $w\not\in L_T$, et « faux » si $L_T =
+\Sigma^*$.)  Indication : expliquer comment on pourrait utiliser un
+tel $A_4$ pour résoudre le problème de l'arrêt, en cherchant à
+fabriquer un $T$ qui rejette un mot précisément si un programme donné
+s'arrête.
+
+\begin{corrige}
+(1) Donnée une expression rationnelle $r$, on sait qu'on peut
+  algorithmiquement fabriquer un automate fini non-déterministe à
+  transitions spontanées qui reconnaît exactement le langage $L_r$
+  dénoté par $r$, et ensuite éliminer les transitions spontanées et
+  déterminiser l'automate pour obtenir un automate fini déterministe
+  complet reconnaissant $L_r$.  Sur un tel automate, savoir si $L_r
+  \neq \Sigma^*$ est trivial : dès lors qu'il existe un état $q$
+  non-final accessible, il existe un mot rejeté par l'automate (i.e.,
+  n'appartenant pas à $L_r$), à savoir le mot lu en suivant les
+  étiquettes d'un chemin quelconque de l'état initial $q_0$
+  jusqu'à $q$, et inversement, si tous les états sont finaux, il est
+  trivial que l'automate accepte tous les mots.  (On pouvait aussi
+  minimiser l'automate et le comparer à l'automate minimal trivial qui
+  reconnaît le langage $\Sigma^*$.)
+
+\smallbreak
+
+(2) On sait qu'il existe un algorithme qui, donnée une grammaire
+hors-contexte $G$ et un mot $w$, décide si $w \in L_G$.  Pour
+semi-décider s'il existe un $w$ tel que $w \not\in L_G$, il suffit de
+tester tous les mots possibles : plus exactement, on construit un
+algorithme $A_2$ qui effectue une boucle infinie sur tous les
+$w\in\Sigma^*$ (il est évidemment algorithmiquement faisable
+d'énumérer tous les mots sur $\Sigma$) et, pour chacun, teste si $w
+\in L_G$, et si ce n'est pas le cas, termine immédiatement en
+répondant « vrai » (on a trouvé un $w$ n'appartenant pas à $L_G$),
+tandis que si c'est le cas, l'algorithme $A_2$ ne terminera jamais.
+
+\smallbreak
+
+(3) On procède exactement comme en (2) : par hypothèse on dispose d'un
+algorithme $T$ qui, donné un mot $w$, décide si $w \in L_T$.  Pour
+semi-décider s'il existe un $w$ tel que $w \not\in L_T$, il suffit de
+tester tous les mots possibles : plus exactement, on construit un
+algorithme $A_3$ qui effectue une boucle infinie sur tous les
+$w\in\Sigma^*$ et, pour chacun, teste si $w \in L_T$ (en lançant
+l'algorithme $T$ qui, par hypothèse, termine toujours), et si ce n'est
+pas le cas, termine immédiatement en répondant « vrai » (on a trouvé
+un $w$ n'appartenant pas à $L_T$), tandis que si c'est le cas,
+l'algorithme $A_3$ ne terminera jamais.
+
+\smallbreak
+
+(4) Supposons par l'absurde qu'on dispose d'un algorithme $A_4$ comme
+on vient de dire, et montrons pour arriver à une contradiction qu'on
+peut s'en servir pour résoudre le problème de l'arrêt.  On se donne
+donc un algorithme $S$ et une entrée $x$ de $S$ et on cherche à savoir
+(en utilisant $A_4$) si $S$ termine sur l'entrée $x$.  Pour cela, on
+va construire un $T$ auquel appliquer $A_4$.
+
+Voici une solution possible : donné un mot $w \in \Sigma^*$, le
+programme $T$ ne considère que la longueur $|w|$ de $w$, et lance
+(=simule) l'exécution de $S$ sur l'entrée $x$ pour au plus $|w|$
+étapes : si l'exécution termine dans le temps imparti, alors $T$
+rejette le mot $w$, sinon, il l'accepte (dans tous les cas, $T$
+termine et répond « vrai » ou « faux », donc il est une entrée
+légitime à $A_4$).  Cette construction fait que $L_T$ rejette un mot
+précisément lorsque $S$ termine sur $x$ : si au contraire $S$ ne
+termine pas sur $x$, alors $L_T = \Sigma^*$.  L'utilisation de $A_4$
+sur $T$ permet donc de savoir algorithmiquement si $S$ termine
+sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt.
+
+Variante de la même idée : on appelle « trace d'exécution » de $S$ sur
+$x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur
+$x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état
+courant et le contenu du ruban à chaque étape), du début à l'arrêt.
+Une telle trace d'exécution existe donc précisément si $S$ termine
+sur $x$.  Or il est visiblement décidable de savoir si un mot $w$
+donné est une trace d'exécution (il suffit de vérifier qu'à chaque
+étape la machine a bien fait ce qu'elle devait faire).  On peut donc
+écrire un algorithme $T$ qui termine toujours et accepte précisément
+les mots qui \emph{ne sont pas} une trace d'exécution de $S$ sur $x$.
+Le fait que $L_T$ soit différent de $\Sigma^*$ signifie alors
+exactement qu'une trace d'exécution existe, donc que $S$ termine
+sur $x$.  Ainsi l'utilisation de $A_4$ permet de savoir
+algorithmiquement si $S$ termine sur $x$, ce qui contredit
+l'indécidabilité du problème de l'arrêt.
+\end{corrige}
+
+
 
 %
 %