diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 234 |
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} % |