More about primitive recursive functions, and Kleene's recursion theorem.

1 files changed, 265 insertions, 12 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 76543df..c1ef885 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -27,6 +27,8 @@
 %
 \newcommand{\itempoint}{\strut\hbox{\color{beamerstructure}\donotcoloroutermaths$\blacktriangleright$}\nobreak\hskip.5em plus.5em\relax}
 \renewcommand{\thefootnote}{\textdagger}
+\newcommand{\dbllangle}{\mathopen{\langle\!\langle}}
+\newcommand{\dblrangle}{\mathclose{\rangle\!\rangle}}
 %
 %
 %
@@ -309,10 +311,10 @@ définit une bijection calculable $\mathbb{N}^2 \to \mathbb{N}$.
 
 \itempoint Codage des listes finies : par exemple,
 \[
-\langle\!\langle a_0,\ldots,a_{k-1}\rangle\!\rangle
+\dbllangle a_0,\ldots,a_{k-1}\dblrangle
 := \langle a_0, \langle a_1, \langle\cdots,\langle a_{k-1},0\rangle+1\cdots\rangle+1\rangle+1
 \]
-définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \to \mathbb{N}$.
+définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \to \mathbb{N}$ {\footnotesize (avec $\dbllangle\dblrangle := 0$)}.
 
 \bigskip
 
@@ -360,7 +362,13 @@ une fonction $D \to \mathbb{N}$ définie sur une partie $D \subseteq
 
 \itempoint Convention : $f(n) = g(m)$ signifie « $f(n)\downarrow$ ssi
 $g(m)\downarrow$, et $f(n) = g(m)$ si $f(n)\downarrow$ ».  (Certains
-préfèrent $f(n) \simeq g(m)$ pour ça.)
+préfèrent écrire $f(n) \simeq g(m)$ pour ça.)
+
+\medskip
+
+\itempoint Convention : si $g_i(\underline{x})\uparrow$ pour un $i$,
+on convient que
+$h(g_1(\underline{x}),\ldots,g_k(\underline{x}))\uparrow$.
 
 \medskip
 
@@ -373,7 +381,7 @@ préfèrent $f(n) \simeq g(m)$ pour ça.)
 \frametitle{Terminologie à venir (avant-goût)}
 
 \itempoint Une fonction partielle $f\colon \mathbb{N} \dasharrow
-\mathbb{N}$ est dite \textbf{calculable} (partielle) lorsqu'il existe
+\mathbb{N}$ est dite \textbf{calculable partielle} lorsqu'il existe
 un algorithme qui prend $n$ en entrée et :
 \begin{itemize}
 \item termine (en temps fini) et renvoie $f(n)$ lorsque $f(n)\downarrow$,
@@ -414,28 +422,64 @@ est calculable (répondre « oui » ou « ... » selon que $n\in A$ ou $n\no
 %
 \section{Fonctions primitives récursives}
 \begin{frame}
-\frametitle{Fonctions primitives récursives : définition}
+\frametitle{Fonctions primitives récursives : aperçu}
+
+\itempoint Avant de définir les fonctions générales récursives
+($\cong$ calculables), on va commencer par les \textbf{primitives
+  récursives}, plus restreintes.
 
 {\footnotesize« primitive\alert{ment} récursives » ?\par}
 
 \bigskip
 
+\itempoint Historiquement antérieures à la calculabilité de
+Church-Turing.
+
+\bigskip
+
+\itempoint Pédagogiquement utile comme « échauffement ».
+
+\bigskip
+
+\itempoint À cheval entre calculabilité (\textbf{PR} est une petite
+classe de calculabilité) et complexité (c'est une grosse classe de
+complexité).
+
+\bigskip
+
+\itempoint Correspond à des programmes à \textbf{boucles bornées a
+  priori}.
+
+\bigskip
+
+\itempoint Énormément d'algorithmes usuels sont p.r.
+
+\bigskip
+
+\itempoint Mais p.ex. la fonction d'Ackermann n'est pas p.r.
+
+\end{frame}
+%
+\begin{frame}
+\label{primitive-recursive-definition}
+\frametitle{Fonctions primitives récursives : définition}
+
 \itempoint $\textbf{PR}$ est la plus petite classe de fonctions
 $\mathbb{N}^k \dasharrow \mathbb{N}$ (en fait $\mathbb{N}^k \to
 \mathbb{N}$), pour $k$ variable qui :
 \begin{itemize}
 \item contient les projections $\underline{x} := (x_1,\ldots,x_k)
   \mapsto x_i$ ;
-\item contient les constantes $x \mapsto c$ ;
+\item contient les constantes $\underline{x} \mapsto c$ ;
 \item contient la fonction successeur $x \mapsto x+1$ ;
 \item est stable par composition : si $g_1,\ldots,g_\ell\colon
   \mathbb{N}^k \dasharrow \mathbb{N}$ et $h\colon \mathbb{N}^\ell
   \dasharrow \mathbb{N}$ sont p.r. alors $\underline{x} \mapsto
   h(g_1(\underline{x}),\ldots, g_\ell(\underline{x}))$ est p.r. ;
-\item est stable par récursion : si $g\colon \mathbb{N}^k \dasharrow
-  \mathbb{N}$ et $h\colon \mathbb{N}^{k+2} \dasharrow \mathbb{N}$ sont
-  p.r., alors $f\colon \mathbb{N}^{k+1} \dasharrow \mathbb{N}$ est
-  p.r., où :
+\item est stable par récursion primitive : si $g\colon \mathbb{N}^k
+  \dasharrow \mathbb{N}$ et $h\colon \mathbb{N}^{k+2} \dasharrow
+  \mathbb{N}$ sont p.r., alors $f\colon \mathbb{N}^{k+1} \dasharrow
+  \mathbb{N}$ est p.r., où :
 \[
 \begin{aligned}
 f(\underline{x},0) &= g(\underline{x})\\
@@ -447,7 +491,7 @@ f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z)
 \medskip
 
 {\footnotesize Les fonctions p.r. sont automatiq\textsuperscript{t}
-  totales, mais il sera utile de garder la définition avec
+  totales, mais il est commode de garder la définition avec
   $\dasharrow$.\par}
 
 \end{frame}
@@ -491,6 +535,7 @@ f(x,y,z+1) &= y
 \medskip
 
 \itempoint $(u,v) \mapsto \max(u-v,0)$ est p.r. (exercice !)
+ou même $u\% v$.
 
 \end{frame}
 %
@@ -523,7 +568,7 @@ m,n\rangle \mapsto n$ sont p.r.
 \end{frame}
 %
 \begin{frame}
-\frametitle{Fonctions primitives récursives : puissance}
+\frametitle{Fonctions primitives récursives : lien avec la complexité}
 
 En anticipant sur la notion de machine de Turing :
 
@@ -604,4 +649,212 @@ terminant clairement).
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Fonctions primitives récursives : numérotation}
+
+On définit $\psi_e^{(k)}\colon \mathbb{N}^k \dasharrow \mathbb{N}$ par
+induction suivant la déf\textsuperscript{n} de $\mathbf{PR}$
+(cf. transp. \ref{primitive-recursive-definition}) :
+\begin{itemize}
+\item si $e = \dbllangle 0, k, i\dblrangle$ alors
+  $\psi_e^{(k)}(x_1\ldots,x_k) = x_i$ (projections) ;
+\item si $e = \dbllangle 1, k, c\dblrangle$ alors
+  $\psi_e^{(k)}(x_1\ldots,x_k) = c$ (constantes) ;
+\item si $e = \dbllangle 2\dblrangle$ alors
+  $\psi_e^{(k)}(x) = x+1$ (successeur) ;
+\item si $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et $g_i
+  := \psi_{c_i}^{(k)}$ et $h := \psi_d^{(\ell)}$, alors
+  $\psi_e^{(k)} \colon \underline{x} \mapsto
+  h(g_1(\underline{x}),\ldots, g_\ell(\underline{x}))$ (composition) ;
+\item si $e = \dbllangle 4, k, d, c\dblrangle$ et $g :=
+  \psi_c^{(k)}$ et $h := \psi_d^{(k+2)}$, alors (récursion primitive)
+\[
+\begin{aligned}
+\psi_e^{(k+1)}(\underline{x},0) &= g(\underline{x})\\
+\psi_e^{(k+1)}(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z)
+\end{aligned}
+\]
+\end{itemize}
+(Autres cas non définis, i.e., donnent $\uparrow$.)
+
+\bigskip
+
+\itempoint Alors $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est
+p.r. \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \psi_e^{(k)})$.
+
+{\tiny P.ex., $e = \dbllangle 4,1,\dbllangle 3,3,\dbllangle
+  2\dblrangle,\dbllangle 0,3,2\dblrangle\dblrangle,\dbllangle
+  0,1,1\dblrangle\dblrangle$ définit $\psi^{(2)}_e(x,z) = x+z$ sauf
+  erreur (probable) de ma part.\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Manipulation de programmes (version p.r.)}
+
+\itempoint Penser à $e$ dans $\psi_e^{(k)}$ comme un programme écrit
+en « langage p.r. ».
+
+\medskip
+
+\itempoint La fonction $\psi_e^{(k)}\colon \mathbb{N}^k \dasharrow
+\mathbb{N}$ « interprète » le programme $e$.
+
+\medskip
+
+\centerline{*}
+
+\bigskip
+
+La numérotation (transp. précédent) rend p.r. beaucoup de
+manipulations usuelles de programmes (composition, récursion, etc.).
+Notamment :
+
+\medskip
+
+\itempoint\textbf{Théorème s-m-n} (Kleene) : il existe $s_{m,n} \colon
+\mathbb{N}^{m+1} \to \mathbb{N}$ p.r. telle que
+\[
+\psi^{(n)}_{s_{m,n}(e,x_1,\ldots,x_m)}(y_1,\ldots,y_n) =
+\psi^{(m+n)}_e(x_1,\ldots,x_m,\,y_1,\ldots,y_n)
+\]
+
+{\footnotesize\underline{Preuve :} $s_{m,n}(e,\underline{x}) =
+  \dbllangle 3, n, e, \dbllangle 1, n, x_1\dblrangle, \ldots,
+  \dbllangle 1, n, x_m\dblrangle, \; \dbllangle 0, n, 1\dblrangle,
+  \ldots, \dbllangle 0, n, n\dblrangle \dblrangle$ avec nos
+  conventions (composition de fonctions constantes et de
+  projections).\qed\par}
+
+\medskip
+
+\emph{En clair :} $s_{m,n}$ prend un programme $e$ qui prend $m+n$
+arguments en entrée et « fixe » la valeur des $m$ premiers arguments à
+$x_1,\ldots,x_m$, les $n$ arguments suivants ($y_1,\ldots,y_n$) étant
+gardés variables.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Digression : l'astuce de Quine (intuition)}
+
+{\footnotesize Le nom de Willard Van Orman Quine (1908–2000) a été
+  associé à cette astuce par Douglas Hofstadter.  En fait, l'astuce
+  est plutôt due à Cantor, Turing ou Kleene.\par}
+
+\smallskip
+
+\textcolor{teal}{Les mots suivants suivis des mêmes mots entre
+  guillemets forment une phrase intéressante : « les mots suivants
+  suivis des mêmes mots entre guillemets forment une phrase
+  intéressante ».}
+
+\bigskip
+
+Pseudocode :
+
+\smallskip
+
+{\footnotesize\texttt{%
+str="somefunc(code) \{ /*...*/ \}\textbackslash nsomefunc(\textbackslash"str=\textbackslash"+quote(str)+str);\textbackslash n";\\
+somefunc(code) \{ /*...*/ \}\\
+somefunc("str="+quote(str)+str);
+}\par}
+
+\smallskip
+
+$\Rightarrow$ La fonction \texttt{somefunc} (arbitraire) est appelée
+avec le code source du programme tout entier.
+
+\medskip
+
+{\footnotesize\textbf{Exercice :} utiliser cette astuce pour écrire un
+  programme écrivant son propre code source.\par}
+
+\bigskip
+
+\textbf{Moralité :} \alert{on peut toujours donner aux programmes
+  accès à leur code source}, même si ce n'est pas prévu par le
+langage.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Le théorème de récursion de Kleene (version p.r.)}
+
+Version formelle de l'astuce de Quine
+
+{\footnotesize (aussi appelé « théorème du point fixe » de Kleene)\par}
+
+\smallskip
+
+\itempoint\textbf{Théorème} (Kleene) : si $h \colon \mathbb{N}^{k+1}
+\dasharrow \mathbb{N}$ est p.r., il existe $e$ tel que
+\[
+\psi^{(k)}_e(\underline{x}) = h(e,\underline{x})
+\]
+Plus précisément, il existe $b \colon \mathbb{N}^2 \to \mathbb{N}$
+p.r. telle que
+\[
+\psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x})
+\text{~si~}e := b(k,d)
+\]
+
+\bigskip
+
+\underline{Preuve :} soit $s := s_{m,1}$ donné par le théorème s-m-n.
+La fonction $(t,\underline{x}) \mapsto h(s(t,t),\underline{x})$ est
+p.r., disons $= \psi_c^{(k+1)}(\underline{x})$.  Alors
+\[
+\psi_{s(c,c)}^{(k)}(\underline{x})
+= \psi_{c}^{(k+1)}(c, \underline{x})
+= h(s(c,c),\underline{x})
+\]
+donc $e := s(c,c)$ convient.  Les fonctions $d \mapsto c \mapsto e$
+sont p.r.\qed
+
+\bigskip
+
+\textbf{Moralité :} \alert{on peut donner aux programmes accès à leur
+  propre numéro} (= « code source »), cela ne change rien.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions primitives récursives : pas d'universalité}
+
+\itempoint\textbf{Théorème :} il n'existe pas de fonction
+p.r. $u\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $u(e,x) =
+\psi^{(1)}_e(x)$ si $\psi^{(1)}_e(x)\downarrow$.
+
+\bigskip
+
+\underline{Preuve :} par l'absurde : si un tel $u$ existe, alors
+$(e,x) \mapsto u(e,x)+1$ est p.r.  Par le théorème de récursion de
+Kleene, il existe $e$ tel que $\psi^{(1)}_e(x) = u(e,x) + 1$, ce qui
+contredit $u(e,x) = \psi^{(1)}_e(x)$.\qed
+
+\medskip
+
+\centerline{*}
+
+\medskip
+
+\textbf{Moralité :} \alert{un interpréteur du langage p.r. ne peut pas
+  être p.r.} (preuve : on peut interpréter l'interpréteur
+s'interprétant lui-même, en ajoutant un au résultat, ce qui donne un
+paradoxe ; c'est un argument diagonal de Cantor).
+
+\bigskip
+
+\itempoint Cet argument dépend du théorème s-m-n et du fait que les
+fonctions p.r. sont \alert{totales}.  Pour définir une théorie
+satisfaisante de la calculabilité, on va sacrifier la totalité pour
+sauver le théorème s-m-n.
+
+{\footnotesize Cette même preuve donnera alors la preuve de
+  l'indécidabilité du problème de l'arrêt.\par}
+
+\end{frame}
+%
 \end{document}