General recursive function: introduction.

NB: The part about elimination of recursivity is flawed.  Will remove

1 files changed, 231 insertions, 4 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index c1ef885..9aeeb71 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -396,8 +396,8 @@ $\mathbb{N}\to\mathbb{N}$
 \[
 \mathbf{1}_A\colon n \mapsto \left\{
 \begin{array}{ll}
-1&\text{~si $n\in A$}\\
-0&\text{~si $n\not\in A$}\\
+1&\text{~si~}n\in A\\
+0&\text{~si~}n\not\in A\\
 \end{array}
 \right.
 \]
@@ -411,8 +411,8 @@ $\mathbb{N}\dasharrow\mathbb{N}$ (d'ensemble de définition $A$)
 \[
 n \mapsto \left\{
 \begin{array}{ll}
-1&\text{~si $n\in A$}\\
-\uparrow&\text{~si $n\not\in A$}\\
+1&\text{~si~}n\in A\\
+\uparrow&\text{~si~}n\not\in A\\
 \end{array}
 \right.
 \]
@@ -857,4 +857,231 @@ sauver le théorème s-m-n.
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Fonctions primitives récursives : pas d'universalité (variante)}
+
+Rappel : la \textbf{fonction d'Ackermann} est définie par :
+\[
+\begin{aligned}
+A(m,n,0) &= m+n \\
+A(m,1,k+1) &= m \\
+A(m,n+1,k+1) &= A(m,\,A(m,n,k+1),\,k)
+\end{aligned}
+\]
+
+\bigskip
+
+\itempoint Pour un $k$ \alert{fixé}, la fonction $(m,n) \mapsto
+A(m,n,k)$ est p.r. (par récurrence sur $k$, récursion primitive sur
+$A(m,n,k-1)$).
+
+\bigskip
+
+\itempoint Il existe même $k \mapsto a(k)$ p.r. telle que
+$\psi^{(2)}_{a(k)}(m,n) = A(m,n,k)$.
+
+\smallskip
+
+I.e., on peut calculer de façon p.r. en $k$ le code d'un programme
+p.r. qui calcule $(m,n) \mapsto A(m,n,k)$.
+
+\bigskip
+
+\itempoint Si (une extension de) $(e,n) \mapsto \psi^{(1)}_e(n)$ était
+p.r., on pourrait calculer $(n,k) \mapsto
+\psi^{(1)}_{s_{1,1}(a(k),2)}(n) = \psi^{(2)}_{a(k)}(2,n) = A(2,n,k)$,
+or elle n'est pas p.r.
+
+\end{frame}
+%
+\section{Fonctions générales récursives}
+\begin{frame}
+\frametitle{Fonctions générales récursives : aperçu}
+
+\itempoint On a vu que les fonctions p.r. sont \alert{limitées} et ne
+couvrent pas la notion générale d'algorithme :
+\begin{itemize}
+\item les algorithmes p.r. terminent toujours car
+\item le langage ne permet pas de boucles non bornées ;
+\item concrètement, il n'implémente pas la fonction d'Ackermann ;
+\item il ne peut pas s'interpréter lui-même.
+\end{itemize}
+
+\bigskip
+
+\itempoint On veut modifier la définition des fonctions p.r. pour
+lever ces limitations.  On va \alert{autoriser les boucles infinies}.
+
+\bigskip
+
+\itempoint En ce faisant, on obtient forcément des cas de
+non-terminaisons, donc on doit passer par des \alert{fonctions
+  partielles}.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{L'opérateur $\mu$ de Kleene}
+
+\textbf{Définition :} $\mu g(\underline{x})$ est le plus petit $z$ tel
+que $g(z,\underline{x}) = 0$ et $g(i,\underline{x})\downarrow$ pour
+$0\leq i<z$, s'il existe.
+
+\bigskip
+
+Autrement dit, $\mu g(\underline{x}) = z$ signifie
+\begin{itemize}
+\item $g(z,\underline{x}) = 0$,
+\item $g(i,\underline{x})>0$ (sous-entendant
+  $g(i,\underline{x})\downarrow$) pour tout $0\leq i<z$.
+\end{itemize}
+
+\bigskip
+
+Concrètement, penser à $\mu g$ comme la fonction
+
+\texttt{i=0;  while (true) \{ if (g(i,x)==0) \{ return i; \}  i++; \}}
+
+\bigskip
+
+\itempoint Ceci permet toute sorte de \alert{recherche non bornée}.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions générales récursives : définition}
+
+\itempoint $\textbf{R}$ est la plus petite classe de fonctions
+$\mathbb{N}^k \dasharrow \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 $\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 récursives alors $\underline{x} \mapsto
+  h(g_1(\underline{x}),\ldots, g_\ell(\underline{x}))$ est récursive ;
+\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 récursives, alors $f\colon \mathbb{N}^{k+1}
+  \dasharrow \mathbb{N}$ est récursive, où :
+\[
+\begin{aligned}
+f(\underline{x},0) &= g(\underline{x})\\
+f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z)
+\end{aligned}
+\]
+\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.
+\end{itemize}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Élimination de la récursivité}
+
+Considérons une définition récursive du type (ceci n'est qu'un exemple) :
+\[
+f(x) = \left\{
+\begin{array}{ll}
+g(x)&\text{~si~}t(x)=0\\
+h(x,f(v(x)))&\text{~si~}t(x)\neq 0\\
+\end{array}
+\right.
+\]
+à comprendre comme l'algorithme évident
+
+{\footnotesize\texttt{f(x) \{ if (t(x)==0) \{ return g(x); \} else \{
+    return h(x,f(v(x))); \} \}}\par}
+
+Comment voir que $f$ est générale récursive (si $t,g,h,v$ le sont) ?
+
+\bigskip
+
+\itempoint On définit une version avec un paramètre $N$ supplémentaire
+(« profondeur de pile d'appels », « quantité essence ») :
+\[
+\begin{aligned}
+\tilde f(0,x) &= 0\\
+\tilde f(N+1,x) &= \left\{
+\begin{array}{ll}
+g(x)&\text{~si~}t(x)=0\\
+h(x,\tilde f(N,v(x)))&\text{~si~}t(x)\neq 0\\
+\end{array}
+\right.\\
+\end{aligned}
+\]
+et une fonction indiquant s'il faut plus de profondeur
+\[
+\begin{aligned}
+w(0,x) &= 1\\
+w(N+1,x) &= \left\{
+\begin{array}{ll}
+0&\text{~si~}t(x)=0\text{,~ou~bien~}t(x)\neq 0\text{~et~}w(N,v(x))=0\\
+1&\text{~sinon}
+\end{array}
+\right.\\
+\end{aligned}
+\]
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Élimination de la récursivité (suite)}
+
+Plus général\textsuperscript{t}, on transforme une fonction récursive
+$f$ en $\tilde f$ avec un argument « profondeur » supplémentaire, avec
+$\tilde f(0,\ldots)$ arbitraire, et chaque appel de $\tilde
+f(N+1,\ldots)$ faisant faisant appel à $\tilde f(N,\ldots)$ dans la
+récursion.  Quant à $w(N+1,\ldots)$ il vaut $0$ si tous les appels à
+$\tilde f(N,\ldots)$ ont $w(N,\ldots)=0$, et $1$ sinon.
+
+\medskip
+
+Alors :
+\begin{itemize}
+\item $\tilde f$ et $w$ sont définis par récursion primitive,
+\item $f(\underline{x}) = \tilde f(\mu w(\underline{x}), \underline{x})$
+\end{itemize}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Élimination de la récursivité (exemple)}
+
+Exemple : la \textbf{fonction d'Ackermann} est définie par :
+{\footnotesize
+\[
+\begin{aligned}
+A(m,n,0) &= m+n \\
+A(m,1,k+1) &= m \\
+A(m,n+1,k+1) &= A(m,\,A(m,n,k+1),\,k)
+\end{aligned}
+\]
+\par}
+
+On transforme cette définition récursive en une définition par $\mu$ :
+
+{\footnotesize
+\[
+\begin{aligned}
+\tilde A(0,m,n,k) &= 0 \\
+\tilde A(N+1,m,n,0) &= m+n \\
+\tilde A(N+1,m,1,k+1) &= m \\
+\tilde A(N+1,m,n+1,k+1) &= \tilde A(N,m,\,\tilde A(N,m,n,k+1),\,k)\\
+w(0,m,n,k) &= 1 \\
+w(N+1,m,n,0) &= 0 \\
+w(N+1,m,1,k+1) &= 0 \\
+w(N+1,m,n+1,k+1) &= w(N,m,n,k+1) \;\vee\; w(N,m,\,\tilde A(N,m,n,k+1),\,k)\\
+A(m,n,k) &= \tilde A(\mu w(m,n,k), m,n,k)
+\end{aligned}
+\]
+\par}
+
+Ici $\tilde A$ et $w$ \alert{sont p.r.} et $A$ est générale récursive.
+
+\end{frame}
+%
 \end{document}