General recursive functions: numbering, computation trees, universality, normal form.

1 files changed, 238 insertions, 2 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 8f1c3e6..d693a3d 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -327,7 +327,7 @@ entiers.
 
 \bigskip
 
-\itempoint\alert{Ne pas utiliser dans la vraie vie} (hors calculabilité) !
+\itempoint\textcolor{orange}{Ne pas utiliser dans la vraie vie} (hors calculabilité) !
 
 \end{frame}
 %
@@ -918,6 +918,12 @@ lever ces limitations.  On va \alert{autoriser les boucles infinies}.
 non-terminaisons, donc on doit passer par des \alert{fonctions
   partielles}.
 
+\bigskip
+
+{\footnotesize\textbf{N.B.} Terminologie confuse : fonctions
+  « générales récursives » ? juste « récursives » ? « récursives
+  partielles » ?  « calculables » ? « calculables partielles » ?\par}
+
 \end{frame}
 %
 \begin{frame}
@@ -949,6 +955,7 @@ Concrètement, penser à $\mu g$ comme la fonction
 \end{frame}
 %
 \begin{frame}
+\label{general-recursive-definition}
 \frametitle{Fonctions générales récursives : définition}
 
 \itempoint $\textbf{R}$ est la plus petite classe de fonctions
@@ -974,9 +981,238 @@ f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z)
 \]
 \item est stable par l'opérateur $\mu$ : si $g\colon \mathbb{N}^{k+1}
   \dasharrow \mathbb{N}$ est récursive, alors $\mu g\colon
-  \mathbb{N}^k \dasharrow \mathbb{N}$ est récursive.
+  \mathbb{N}^k \dasharrow \mathbb{N}$ est récursive
+  (\alert{$\leftarrow$ nouveau !}).
+\end{itemize}
+
+\medskip
+
+Cette fois le langage \alert{permet les boucles non bornées} !
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions générales récursives : numérotation}
+
+On définit $\varphi_e^{(k)}\colon \mathbb{N}^k \dasharrow \mathbb{N}$ par
+induction suivant la déf\textsuperscript{n} de $\mathbf{R}$
+(cf. transp. \ref{general-recursive-definition}) :
+\begin{itemize}
+\item si $e = \dbllangle 0, k, i\dblrangle$ alors
+  $\varphi_e^{(k)}(x_1\ldots,x_k) = x_i$ (projections) ;
+\item si $e = \dbllangle 1, k, c\dblrangle$ alors
+  $\varphi_e^{(k)}(x_1\ldots,x_k) = c$ (constantes) ;
+\item si $e = \dbllangle 2\dblrangle$ alors
+  $\varphi_e^{(k)}(x) = x+1$ (successeur) ;
+\item si $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et $g_i
+  := \varphi_{c_i}^{(k)}$ et $h := \varphi_d^{(\ell)}$, alors
+  $\varphi_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 :=
+  \varphi_c^{(k)}$ et $h := \varphi_d^{(k+2)}$, alors (récursion primitive)
+\[
+\begin{aligned}
+\varphi_e^{(k+1)}(\underline{x},0) &= g(\underline{x})\\
+\varphi_e^{(k+1)}(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z)
+\end{aligned}
+\]
+\item si $e = \dbllangle 5, k, c\dblrangle$ et $g :=
+  \varphi_c^{(k+1)}$, alors $\varphi_e^{(k)} = \mu g$.
+\end{itemize}
+(Autres cas non définis, i.e., donnent $\uparrow$.)
+
+\bigskip
+
+\itempoint Alors $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est
+récursive \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \varphi_e^{(k)})$.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions générales récursives : universalité}
+
+Cette fois, \alert{il existe bien} une fonction récursive universelle,
+c'est-à-dire :
+
+\smallskip
+
+\itempoint $(e,\underline{x}) \mapsto \varphi_e^{(k)}(\underline{x})$
+est récursive : $\exists u_k \in
+\mathbb{N}.\,(\varphi_{u_k}^{(k+1)}(e, \underline{x}) =
+\varphi_e^{(k)}(\underline{x}))$.
+
+{\footnotesize Variante : $\exists u.\,(\varphi_{u}^{(1)}(\dbllangle
+  e, \underline{x}\dblrangle) = \varphi_e^{(k)}(\underline{x}))$ en
+  codant programme $e$ et arguments $\underline{x}$ en un entier.\par}
+
+\bigskip
+
+Qu'est-ce que ça nous dit ?
+
+\medskip
+
+\itempoint\textcolor{blue}{Mathématiquement}, que $\varphi^{(k)}$ est
+elle-même récursive en tous ses arguments, y compris l'indice de
+numérotation.
+
+\medskip
+
+\itempoint\textcolor{blue}{Informatiquement}, qu'il existe un
+\alert{interpréteur} $u$ du langage général récursif dans le langage
+général récursif.
+
+\medskip
+
+\itempoint\textcolor{blue}{Philosophiquement}, que la notion
+d'« exécuter un algorithme » est \alert{elle-même algorithmique}.
+
+\bigskip
+
+\textcolor{brown}{Mais comment le prouver ?}  On va esquisser une
+méthode par \textbf{arbres de calcul}.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Arbres de calcul pour les fonctions récursives}
+
+Un \textbf{arbre de calcul} de $\varphi_e^{(k)}(\underline{x})$ de
+résultat $y$ est un arbre (fini, enraciné, ordonné, étiqueté par des
+entiers naturels) qui « atteste » que $\varphi_e^{(k)}(\underline{x})
+= y$ en détaillant les étapes du calcul.
+
+\medskip
+
+\begin{itemize}
+\item La racine est étiquetée « $\varphi_e^{(k)}(\underline{x}) = y$ »
+  ou plutôt « $\dbllangle e, \dbllangle \underline{x}\dblrangle,
+  y\dblrangle$ ».
+\item Le sous-arbre porté par chaque fils de la racine est lui-même un
+  arbre de calcul pour une sous-expression utilisée dans le calcul de
+  $f(\underline{x}) = y$.
+\item Pour les cas projection, constante, successeur, il n'y a pas de
+  fils.
+\item Pour la composition
+  $h(g_1(\underline{x}),\ldots,g_\ell(\underline{x}))$, les fils
+  portent des arbres de calcul attestant
+  $g_1(\underline{x})=v_1,\ldots,g_\ell(\underline{x})=v_\ell$ et
+  $h(\underline{v})=y$.
+\item Pour la récursion primitive $f(\underline{x},z)$, on a soit un
+  seul fils arbre de calcul attestant $g(\underline{x})=y$ lorsque
+  $z=0$ soit deux fils arbres de calcul attestant
+  $f(\underline{x},z')=v$ et $h(\underline{x},v,z')=y$ lorsque
+  $z=z'+1$.
+\item Pour $f = \mu g$, on a des fils attestant
+  $g(0,\underline{x})=v_0,\ldots,g(y,\underline{x})=v_y$.
+\end{itemize}
+
+\medskip
+
+On a $\varphi_e^{(k)}(\underline{x}) = y$ \alert{ssi} il en existe un
+arbre de calcul qui l'atteste.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Arbres de calcul : formalisation}
+
+Formellement :
+
+{\footnotesize
+\begin{itemize}
+\item la racine est étiquetée $\dbllangle e, \dbllangle
+  \underline{x}\dblrangle, y\dblrangle$,
+\item soit $e$ est $\dbllangle 0, k, i\dblrangle$ ou $\dbllangle 1, k,
+  c\dblrangle$ ou $\dbllangle 2\dblrangle$, elle n'a pas de
+  fils, et $y$ vaut resp\textsuperscript{t} $x_i$, $c$ ou $x+1$,
+\item soit $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et
+  les fils portent des arbres de calculs attestant
+  $\varphi_{c_1}^{(k)}(\underline{x})=v_1$, ...,
+  $\varphi_{c_\ell}^{(k)}(\underline{x})=v_\ell$ et
+  $\varphi_d^{(\ell)}(\underline{v})=y$.
+\item soit $e = \dbllangle 4, k', d, c\dblrangle$ où $k'=k-1$ et
+\begin{itemize}\footnotesize
+\item soit $x_k = 0$ et l'unique fils porte arbre de calcul attestant
+  $\varphi_{c}^{(k')}(x_1,\ldots,x_{k'})=y$,
+\item soit $x_k = z+1$ et les deus fils portent arbres de calcul
+  attestant $\varphi_{e}^{(k'+1)}(x_1,\ldots,x_{k'},z)=v$ et
+  $\varphi_{d}^{(k'+2)}(x_1,\ldots,x_{k'},v,z)=y$.
+\end{itemize}
+\item soit $e = \dbllangle 5, k, c\dblrangle$ et les fils portent des
+  arbres de calcul attestant $\varphi_{c}^{(k+1)}(0,x_1,\ldots,x_k)=v_0$,
+  ..., $\varphi_{c}^{(k+1)}(y,x_1,\ldots,x_k)=v_y$ où $v_y=0$ et
+  $v_0,\ldots,v_{y-1} > 0$.
+\end{itemize}
+\par}
+
+On encode l'arbre $\mathscr{T}$ par l'entier
+$\operatorname{code}(\mathscr{T}) := \dbllangle n,
+\operatorname{code}(\mathscr{T}_1), \ldots,
+\operatorname{code}(\mathscr{T}_s)\dblrangle$ où $n$ est l'étiquette
+de la racine et $\mathscr{T}_1,\ldots,\mathscr{T}_s$ les codes des
+sous-arbres portés par les fils de celle-ci.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Arbres de calcul $\Rightarrow$ universalité}
+
+Les points-clés :
+\begin{itemize}
+\item On a $\varphi_e^{(k)}(\underline{x}) = y$ \alert{ssi} il existe
+  un arbre de calcul $\mathscr{T}$ l'attestant.
+\item Vérifier si $\mathscr{T}$ est un arbre de calcul valable est
+  \alert{primitif récursif} en $\operatorname{code}(\mathscr{T})$.
+  (On peut vérifier les règles à chaque nœud avec des boucles
+  bornées.)
+\item De même, extraire $e,\underline{x},y$ de $\mathscr{T}$ est
+  primitif récursif.
 \end{itemize}
 
+\bigskip
+
+D'où l'algorithme « universel » pour calculer
+$\varphi_e^{(k)}(\underline{x})$ en fonction de $e,\underline{x}$ :
+\begin{itemize}
+\item parcourir $n=0,1,2,3,4,\ldots$,
+\item pour chacun, tester s'il code un arbre de calcul valable de
+  $\varphi_e^{(k)}(\underline{x})$,
+\item si oui, terminer et renvoyer le $y$ contenu.
+\end{itemize}
+
+La boucle non-bornée est précisément ce que permet $\mu$.  Tout le
+reste est p.r.
+
+$\Rightarrow$ Ceci montre l'existence de $u$.
+
+\bigskip
+
+\textcolor{orange}{Ne pas coder un interpréteur comme ça dans la vraie vie !}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Théorème de la forme normale}
+
+On a montré un peu plus que l'universalité : on peut exécuter
+n'importe quel algorithme avec une \alert{unique boucle non bornée}.
+Plus exactement :
+
+\bigskip
+
+\itempoint\textbf{Théorème de la forme normale} (Kleene) : il existe
+un prédicat p.r. $T$ sur $\mathbb{N}^3$ et une fonction p.r. $U \colon
+\mathbb{N} \to \mathbb{N}$ tels que :
+\[
+\varphi_e^{(k)}(x_1,\ldots,x_k)
+= U(\mu T(e,\dbllangle x_1,\ldots,x_k\dblrangle))
+\]
+
+Précisément, $T(n, e,\dbllangle x_1,\ldots,x_k\dblrangle)$ teste si
+$n$ est le code d'un arbre de calcul valable de
+$\varphi_e^{(k)}(\underline{x})$, et $U$ extrait le résultat de cet
+arbre.
+
 \end{frame}
 %
 \end{document}