summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2021-06-17 21:29:21 +0200
committerDavid A. Madore <david+git@madore.org>2021-06-17 21:29:21 +0200
commit2cb1aa7d99b77a8f45615231ab44572db3002b7a (patch)
treef7a63cf0e45f38905e96125ff04f4610b4a988e5
parent141ac53dbf4bc94ed0ee7d3494cc9f4b5cf8d6a1 (diff)
downloadinf105-2cb1aa7d99b77a8f45615231ab44572db3002b7a.tar.gz
inf105-2cb1aa7d99b77a8f45615231ab44572db3002b7a.tar.bz2
inf105-2cb1aa7d99b77a8f45615231ab44572db3002b7a.zip
Write answers to third exercise.
-rw-r--r--controle-20210618.tex37
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}
+
%
%