Decidable and semi-decidable sets.

1 files changed, 233 insertions, 1 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 211f842..93d2a11 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -1334,6 +1334,7 @@ $\Rightarrow$ Ceci montre l'existence de $u$.
 \end{frame}
 %
 \begin{frame}
+\label{normal-form-theorem}
 \frametitle{Théorème de la forme normale}
 
 On a montré un peu plus que l'universalité : on peut exécuter
@@ -1557,6 +1558,7 @@ Cette question est-elle \alert{algorithmique} ?
 \end{frame}
 %
 \begin{frame}
+\label{undecidability-halting-problem}
 \frametitle{L'indécidabilité du problème de l'arrêt}
 
 \itempoint\textbf{Théorème} (Turing) : il n'existe pas de fonction
@@ -1598,6 +1600,7 @@ contraire, ce qui conduit à un paradoxe.
 \end{frame}
 %
 \begin{frame}
+\label{undecidability-halting-problem-redux}
 \frametitle{L'indécidabilité du problème de l'arrêt : redite}
 
 {\footnotesize Notons $\varphi$ pour $\varphi^{(1)}$.\par}
@@ -2069,7 +2072,236 @@ partielle $\mathbb{N}^k \dasharrow \mathbb{N}$ :
 \item « calculablement énumérable »,
 \item « récursivement énumérable ».
 \end{itemize}
-{\footnotesize (La raison du « énumérable » sera expliquée après.)\par}
+{\footnotesize (La raison du mot « énumérable » sera expliquée après.)\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Décidable = semi-décidable de complémentaire semi-décidable}
+
+\itempoint Si $A \subseteq \mathbb{N}^k$ est décidable, alors son
+complémentaire $\complement A := \mathbb{N}^k \setminus A$ l'est
+aussi.
+
+{\footnotesize \underline{Preuve :} échanger $0$ et $1$ dans la
+  réponse. \qedsymbol\par}
+
+\medskip
+
+\itempoint Si $A$ est décidable, alors $A$ est semi-décidable.
+
+{\footnotesize \underline{Preuve :} si réponse $0$, faire une boucle
+  infinie. \qedsymbol\par}
+
+\medskip
+
+\itempoint Donc : si $A$ est décidable, alors $A$ et $\complement A$
+sont semi-décidables.
+
+\bigskip
+
+\itempoint La réciproque est également valable : si $A$ et
+$\complement A$ sont semi-décidables alors $A$ est décidable.
+
+\medskip
+
+\textcolor{blue}{Idée :} lancer « en parallèle » un algorithme qui
+semi-décide $A$ et un qui semi-décide $\complement A$ ; l'un des deux
+finira par donner la réponse voulue.
+
+\medskip
+
+\textcolor{brown}{Mais que signifie « lancer en parallèle » ici ?}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Lancement en parallèle}
+
+On suppose que :
+\begin{itemize}
+\item $\varphi_{e_1}(\underline{x})\downarrow$ ssi $\underline{x} \in A$
+\item $\varphi_{e_2}(\underline{x})\downarrow$ ssi $\underline{x} \not\in A$
+\end{itemize}
+Comment décider si $\underline{x} \in A$ en terminant à coup sûr ?
+
+\bigskip
+
+Grâce au \alert{th. de la forme normale}
+(transp. \ref{normal-form-theorem}) : il y a un prédicat $T$ p.r. tel
+que
+\begin{itemize}
+\item $\varphi_{e_1}(\underline{x})\downarrow$ ssi $\exists
+  n\in\mathbb{N}.\; T(n,e_1,\dbllangle\underline{x}\dblrangle)$
+\item $\varphi_{e_2}(\underline{x})\downarrow$ ssi $\exists
+  n\in\mathbb{N}.\; T(n,e_2,\dbllangle\underline{x}\dblrangle)$
+\end{itemize}
+On a alors $\exists n\in\mathbb{N}.\;
+(T(n,e_1,\dbllangle\underline{x}\dblrangle) \text{~ou~}
+T(n,e_2,\dbllangle\underline{x}\dblrangle))$ à coup sûr.
+
+\bigskip
+
+Algorithme (terminant à coup sûr) :
+\begin{itemize}
+\item parcourir $n=0,1,2,3,4,\ldots$ (boucle non bornée),
+\item pour chacun, tester si
+  $T(n,e_1,\dbllangle\underline{x}\dblrangle)$ et si
+  $T(n,e_2,\dbllangle\underline{x}\dblrangle)$,
+\item si le premier vaut, renvoyer « oui, $\underline{x}\in A$ », si
+  le second vaut, renvoyer « non, $\underline{x}\not\in A$ » (sinon,
+  continuer la boucle).
+\end{itemize}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Lancement en parallèle (variante machines de Turing)}
+
+On suppose que :
+\begin{itemize}
+\item la machine $M_1$ s'arrête sur $\underline{x}$ ssi $\underline{x}
+  \in A$
+\item la machine $M_2$ s'arrête sur $\underline{x}$ ssi $\underline{x}
+  \not\in A$
+\end{itemize}
+Comment décider si $\underline{x} \in A$ en s'arrêtant à coup sûr ?
+
+\bigskip
+
+On va simuler $M_1$ et $M_2$ pour $n$ étapes jusqu'à ce que l'une
+d'elles s'arrête.
+
+\bigskip
+
+Algorithme (terminant à coup sûr) :
+\begin{itemize}
+\item parcourir $n=0,1,2,3,4,\ldots$ (boucle non bornée),
+\item pour chacun, tester si l'exécution de $M_1$ s'arrête sur
+  $\underline{x}$ en $\leq n$ étapes et si l'exécution de $M_2$
+  s'arrête sur $\underline{x}$ en $\leq n$ étapes,
+\item si le premier vaut, renvoyer « oui, $\underline{x}\in A$ », si
+  le second vaut, renvoyer « non, $\underline{x}\not\in A$ » (sinon,
+  continuer la boucle).
+\end{itemize}
+
+\bigskip
+
+{\footnotesize C'est \alert{exactement la même chose} que dans le
+  transp. précédent, avec un nombre d'étapes d'exécution $n$ au lieu
+  d'un arbre de calcul (détail sans importance).\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Problème de l'arrêt}
+
+Le \textbf{problème de l'arrêt} est :
+\[
+\mathscr{H} := \{(e,x)\in\mathbb{N}^2 : \varphi_e(x)\downarrow\}
+\]
+
+\smallskip
+
+\itempoint Il \alert{n'est pas décidable}
+(transp. \ref{undecidability-halting-problem}).
+
+\smallskip
+
+\itempoint Il \alert{est} semi-décidable (par universalité : donné
+$(e,x)$, on peut exécuter $\varphi_e(x)$, et, s'il termine, renvoyer
+« oui »).
+
+\smallskip
+
+\itempoint Donc $\complement\mathscr{H}$ n'est pas semi-décidable.
+
+\bigskip
+
+{\footnotesize
+
+\itempoint Toutes sortes de variantes possibles, p.ex. :
+\begin{itemize}
+\item $\{e\in \mathbb{N} : \varphi_e(e)\downarrow$ n'est pas décidable
+  (preuve dans transp. \ref{undecidability-halting-problem-redux})
+\item $\{e\in \mathbb{N} : \varphi_e(0)\downarrow$ n'est pas décidable
+  (théorème s-m-n : $\varphi_e(x) = \varphi_{s(e,x)}(0)$ avec $s$ p.r.)
+\end{itemize}
+
+\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Image d'un ensemble décidable}
+
+\itempoint Si $A \subseteq \mathbb{N}$ est décidable et $f \colon
+\mathbb{N} \to \mathbb{N}$ (totale) calculable, alors l'image
+\[
+f(A) := \{f(i) : i\in A\}
+\]
+est semi-décidable.
+
+\smallskip
+
+{\footnotesize \underline{Preuve :} donné $m\in\mathbb{N}$, pour
+  semi-décider si $m \in f(A)$, parcourir $i=0,1,2,3\ldots$, et pour
+  chacun, décider si $i\in A$ et, si oui, calculer $f(i)$ et comparer
+  à $m$.  Si $i\in A$ et $f(i)=m$, renvoyer « oui » ; sinon, continuer
+  la boucle.\qed\par}
+
+\bigskip
+
+\itempoint Réciproquement, si $B \subseteq \mathbb{N}$ est
+semi-décidable, il existe $A \subseteq \mathbb{N}$ décidable et $f
+\colon \mathbb{N} \to \mathbb{N}$ (totale) calculable tels que $B =
+f(A)$.
+
+\smallskip
+
+{\footnotesize \underline{Preuve :} soit $e$ tel que $B = \{m :
+  \varphi_e(m)\downarrow\}$ ; soit $A$ l'ensemble des $\langle
+  n,m\rangle$ tels que $T(n,e,\dbllangle m\dblrangle)$ : alors $A$ est
+  décidable et son image par $\langle n,m\rangle \mapsto m$
+  est $B$.\qed\par}
+
+{\footnotesize \underline{Redite :} soit $M$ une machine de Turing qui
+  s'arrête sur $m$ ssi $m \in B$ ; soit $A$ l'ensemble des $\langle
+  n,m\rangle$ tels que $M$ s'arrête sur $m$ en $\leq n$ étapes : alors
+  $A$ est décidable et son image par $\langle n,m\rangle \mapsto m$
+  est $B$.\qed\par}
+
+\bigskip
+
+\itempoint Variante : $A \subseteq \mathbb{N}$ \emph{non vide} est
+semi-décidable ssi il existe $f\colon \mathbb{N} \to \mathbb{N}$
+totale calculable telle que $f(\mathbb{N}) = A$.
+\textcolor{teal}{D'où le terme « calculablement énumérable ».}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Stabilités par opérations booléennes}
+
+Les ensembles \textbf{décidables} sont stables par :
+\begin{itemize}
+\item réunions finies,
+\item intersections finies,
+\item complémentaire,
+\item \alert{mais pas par} projection $\mathbb{N}^k \to
+  \mathbb{N}^{k'}$ (où $k'\leq k$ ; cf. transp. précédent).
+\end{itemize}
+
+\bigskip
+
+Les ensembles \textbf{semi-décidables} sont stables par :
+\begin{itemize}
+\item réunions finies (par lancement en parallèle !),
+\item intersections finies,
+\item projection $\mathbb{N}^k \to \mathbb{N}^{k'}$ (où $k'\leq k$ ;
+  cf. transp. précédent),
+\item \alert{mais pas par complémentaire}.
+\end{itemize}
 
 \end{frame}
 %