diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 235 |
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} |