diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 161 |
1 files changed, 160 insertions, 1 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 8eaa54e..6eaf10d 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -2553,7 +2553,7 @@ Exemples : \end{frame} % \begin{frame} -\frametitle{Le théorème de Rice : preuve} +\frametitle{Le théorème de Rice : preuve par théorème de récursion} {\footnotesize $\textbf{PR}^{(1)} = \{f \colon \mathbb{N}\dasharrow\mathbb{N} : f\text{~calculable}\}$\par} @@ -2596,6 +2596,165 @@ $\Phi(e) = f$ donc $e \in \Phi^{-1}(F)$, une contradiction.\qed \end{frame} % +\begin{frame} +\frametitle{Réductions : introduction} + +\itempoint Situation typique : on veut montrer qu'une question $D$ +(« problème de décision », souvent déjà semi-décidable) est +indécidable. Ceci se fait typiquement en \alert{réduisant le problème + de l'arrêt} à $D$, c'est-à-dire : + +\bigskip + +\textcolor{teal}{« Supposons par l'absurde que $D$ soit décidable, + c'est-à-dire que j'ai un algorithme qui répond à la question $D$ + (comprendre : “$n\in D$ ?”).} + +\smallskip + +\textcolor{teal}{Je montre qu'\alert{en utilisant cet algorithme} je + peux résoudre le problème de l'arrêt.} + +\smallskip + +\textcolor{teal}{Ceci est une contradiction (car le problème de + l'arrêt est indécidable),} + +\textcolor{teal}{donc $D$ est indécidable. »} + +\bigskip + +\itempoint Les notions de réduction formalisent cet argument : +intuitivement, + +\centerline{« $A$ se réduit à $B$ »} + +\centerline{$\Longleftrightarrow$} + +\centerline{« si $B$ est décidable alors $A$ est décidable »} + +\centerline{(mais constructivement)} + +\end{frame} +% +\begin{frame} +\frametitle{Le théorème de Rice : preuve par réduction (1/2)} + +{\footnotesize $\textbf{PR}^{(1)} = \{f \colon + \mathbb{N}\dasharrow\mathbb{N} : f\text{~calculable}\}$\par} + +\smallskip + +\itempoint\textbf{Théorème} (Rice) : si $F \subseteq +\textbf{PR}^{(1)}$ est tel que $F \neq \varnothing$ et $F \neq +\textbf{PR}^{(1)}$, alors $\Phi^{-1}(F) := \{e \in \mathbb{N} : +\varphi^{(1)}_e \in F\}$ \emph{n'est pas décidable}. + +\bigskip + +\underline{Preuve :} Soit $F \subseteq \textbf{PR}^{(1)}$ avec $F \neq +\varnothing$ et $F \neq \textbf{PR}^{(1)}$. Quitte à remplacer $F$ +par $\complement F$, o.p.s. ${\uparrow} \not\in F$ où $\uparrow$ est +la fonction nulle part définie. Soit $f\in F$ où $f = +\varphi^{(1)}_a$. + +\smallskip + +Pour $(e,x) \in \mathbb{N}^2$, considérons l'algorithme suivant, +prenant en entrée $m \in \mathbb{N}$ : +\begin{itemize} +\item simuler $\varphi^{(1)}_e(x)$ avec la machine universelle, puis, + si l'exécution termine, +\item calculer $f(m) = \varphi^{(1)}_a(m)$ et (si l'exécution termine) + renvoyer sa valeur. +\end{itemize} + +\smallskip + +Soit $b(e,x)$ le code de l'algorithme qu'on vient de décrire : +\centerline{$\varphi^{(1)}_{b(e,x)} = f$ si $\varphi^{(1)}_e(x)\downarrow$ +\quad et\quad +$\varphi^{(1)}_{b(e,x)} = {\uparrow}$ si $\varphi^{(1)}_e(x)\uparrow$} +notamment $\varphi^{(1)}_{b(e,x)} \in F$ ssi $\varphi^{(1)}_e(x)\downarrow$ +\textcolor{brown}{($\leftarrow$ c'est là la réduction)}.\hfill …/… + +\end{frame} +% +\begin{frame} +\frametitle{Le théorème de Rice : preuve par réduction (2/2)} + +{\footnotesize $\textbf{PR}^{(1)} = \{f \colon + \mathbb{N}\dasharrow\mathbb{N} : f\text{~calculable}\}$ ; on a + supposé $F \subseteq \textbf{PR}^{(1)}$ avec ${\uparrow}\not\in F$ + et $f \in F$\par} + +\smallskip + +On a construit (transp. précédent) un $b(e,x)$, avec $b \colon +\mathbb{N}^2 \to \mathbb{N}$ calculable (même p.r.) tel que +$\varphi^{(1)}_{b(e,x)} \in F$ ssi $\varphi^{(1)}_e(x)\downarrow$, +c'est-à-dire +\[ +b(e,x) \in \Phi^{-1}(F) \;\Longleftrightarrow\; (e,x) \in \mathscr{H} +\] +où $\mathscr{H} := \{(e,x)\in\mathbb{N}^2 : \varphi_e(x)\downarrow\}$ +est le problème de l'arrêt. + +\medskip + +Si $\Phi^{-1}(F)$ était décidable, alors $\mathscr{H}$ le serait aussi, par +l'algorithme : +\begin{itemize} +\item donnés $e,x$, calculer $b(e,x)$, décider si $b(e,x) \in \Phi^{-1}(F)$, +\item si oui, répondre « oui », sinon répondre « non ». +\end{itemize} + +\smallskip + +Or $\mathscr{H}$ n'est pas décidable, donc $\Phi^{-1}(F)$ non plus.\qed + +\bigskip + +On dit qu'on a \alert{réduit le problème de l'arrêt} à $\Phi^{-1}(F)$ +(\alert{via} la fonction $b$). + +\end{frame} +% +\begin{frame} +\frametitle{Réduction « many-to-one »} + +\textbf{Définition :} Si $A,B\subseteq\mathbb{N}$, on note $A +\mathrel{\leq_\mathrm{m}} B$ lorsqu'il existe $\rho \colon \mathbb{N} +\to \mathbb{N}$ \emph{calculable totale} telle que +\[ +\rho(m) \in B \;\Longleftrightarrow\; m \in A +\] +{\footnotesize (c'est-à-dire $A = \rho^{-1}(B)$)}. + +\bigskip + +\textcolor{blue}{\textbf{Intuitivement :}} si j'ai un gadget qui +répond à la question “$n \in B$ ?”, je peux répondre à la question “$m +\in A$ ?” en transformant $m$ en $\rho(n)$ et en utilisant le gadget. + +\bigskip + +\textbf{Clairement}, si $A \mathrel{\leq_\mathrm{m}} B$ avec $B$ +décidable, alors $A$ est décidable. \emph{Notamment}, si $\mathscr{H} +\mathrel{\leq_\mathrm{m}} D$ alors $D$ \emph{n'est pas} décidable. + +\bigskip + +{\footnotesize La relation $\mathrel{\leq_\mathrm{m}}$ est réflexive + et transitive (c'est un « préordre ») ; la relation + $\mathrel{\equiv_\mathrm{m}}$ définie par $A + \mathrel{\equiv_\mathrm{m}} B$ ssi $A \mathrel{\leq_\mathrm{m}} B$ + et $B \mathrel{\leq_\mathrm{m}} A$ est une relation d'équivalence, + les classes pour laquelle s'appellent « degrés many-to-one » et sont + partiellement ordonnés par $\mathrel{\leq_\mathrm{m}}$.\par} + +\end{frame} +% \section{Le \texorpdfstring{$\lambda$}{lambda}-calcul non typé} \begin{frame} \frametitle{Le $\lambda$-calcul : aperçu} |