From 1f9742c720b9c895410785764bfc1c8bcbb59b00 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 31 Jan 2017 17:04:53 +0100 Subject: Add an exercise on computability. --- controle-20170207.tex | 131 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 131 insertions(+) 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} + + % % -- cgit v1.2.3