diff options
| -rw-r--r-- | controle-20210618.tex | 37 |
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} + % % |