diff options
Diffstat (limited to 'transp-inf110-01-calc.tex')
| -rw-r--r-- | transp-inf110-01-calc.tex | 88 |
1 files changed, 88 insertions, 0 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 4935b36..8eaa54e 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -1510,6 +1510,7 @@ Ceci justifie d'omettre parfois abusivement l'arité \end{frame} % \begin{frame} +\label{kleene-recursion-theorem} \frametitle{Le théorème de récursion de Kleene (version générale récursive)} Exactement comme la version p.r. : @@ -2508,6 +2509,93 @@ Les ensembles \textbf{semi-décidables} sont stables par : \end{frame} % +\begin{frame} +\frametitle{Le théorème de Rice : énoncé} + +Soit $\textbf{PR}^{(1)}$ l'ensemble des fonctions partielles +$\mathbb{N} \dasharrow \mathbb{N}$ calculables (= générales +récursives), et $\Phi \colon e \mapsto \varphi^{(1)}_e$ qui définit +une surjection $\mathbb{N} \to \textbf{PR}^{(1)}$. + +\medskip + +{\footnotesize Si $e$ est l'« intention » (l'algorithme, le + programme), alors $\Phi(e)$ est l'« extension » (la fonction, i.e., + son graphe) définie par $e$.\par} + +\bigskip + +\itempoint\textbf{Théorème} (Rice) : si $F \subseteq +\textbf{PR}^{(1)}$ est un ensemble de fonctions partielles tel que +$\Phi^{-1}(F) := \{e \in \mathbb{N} : \varphi^{(1)}_e \in F\}$ est +\emph{décidable}, alors $F = \varnothing$ ou $F = \textbf{PR}^{(1)}$. + +\bigskip + +\textcolor{blue}{\textbf{Moralité :}} \alert{aucune propriété + non-triviale} de la fonction $\varphi^{(1)}_e$ calculée par un +programme \alert{n'est décidable} en regardant le programme $e$. + +\bigskip + +Exemples : +\begin{itemize} +\item $\{e \in \mathbb{N} : \varphi^{(1)}_e(0){\downarrow}\}$ n'est + pas décidable ($\Rightarrow$ Rice \alert{généralise} + l'indécidabilité du pb. de l'arrêt). +\item $\{e \in \mathbb{N} : \varphi^{(1)}_e \text{~totale}\}$ n'est + pas décidable. +\item $\{e \in \mathbb{N} : \forall + n.\,(\varphi^{(1)}_e(n){\downarrow} \,\Rightarrow\, + \varphi^{(1)}_e(n) = 0)\}$ n'est pas décidable. +\end{itemize} + +\end{frame} +% +\begin{frame} +\frametitle{Le théorème de Rice : preuve} + +{\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 un ensemble de fonctions partielles tel que +$\Phi^{-1}(F) := \{e \in \mathbb{N} : \varphi^{(1)}_e \in F\}$ est +\emph{décidable}, alors $F = \varnothing$ ou $F = \textbf{PR}^{(1)}$. + +\bigskip + +{\footnotesize La preuve est très analogue à celle de l'indécidabilité + du problème de l'arrêt.\par} + +\smallskip + +\underline{Preuve :} Supposons par l'absurde $F$ décidable avec $F +\neq \varnothing$ et $F \neq \textbf{PR}^{(1)}$. Soient $f \in F$ et +$g \not\in F$. Soit +\[ +h(e,x) := \left\{ +\begin{array}{ll} +f(x)&\text{~si~}e\not\in \Phi^{-1}(F)\\ +g(x)&\text{~si~}e\in \Phi^{-1}(F)\\ +\end{array} +\right. +\] +Alors $h \colon \mathbb{N}^2 \dasharrow \mathbb{N}$ est calculable par +hypothèse (on peut décider si $e\in \Phi^{-1}(F)$). Par le théorème +de récursion de Kleene (transp. \ref{kleene-recursion-theorem}), il +existe $e$ tel que +\[\Phi(e) := \varphi^{(1)}_e(x) = h(e,x)\] + +Si $e \in \Phi^{-1}(F)$ alors $h(e,x) = g(x)$ pour tout $x$, donc +$\Phi(e) = g$ donc $e \not\in \Phi^{-1}(F)$, une contradiction. Si $e +\not\in \Phi^{-1}(F)$ alors $h(e,x) = f(x)$ pour tout $x$, donc +$\Phi(e) = f$ donc $e \in \Phi^{-1}(F)$, une contradiction.\qed + +\end{frame} +% \section{Le \texorpdfstring{$\lambda$}{lambda}-calcul non typé} \begin{frame} \frametitle{Le $\lambda$-calcul : aperçu} |