Rice's theorem.

Thanks, "jeanas" for the reminder that this is important.

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}