Primitive recursive functions.

1 files changed, 197 insertions, 0 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index bd41cfb..9db3669 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -362,6 +362,203 @@ une fonction $D \to \mathbb{N}$ définie sur une partie $D \subseteq
 $g(m)\downarrow$, et $f(n) = g(m)$ si $f(n)\downarrow$ ».  (Certains
 préfèrent $f(n) \simeq g(m)$ pour ça.)
 
+\medskip
+
+\itempoint Terminologie : une fonction $f\colon \mathbb{N} \to
+\mathbb{N}$ est dite \textbf{totale}.
+
+\end{frame}
+%
+\section{Fonctions primitives récursives}
+\begin{frame}
+\frametitle{Fonctions primitives récursives : définition}
+
+{\footnotesize« primitive\alert{ment} récursives » ?\par}
+
+\bigskip
+
+\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 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ù :
+\[
+\begin{aligned}
+f(\underline{x},0) &= g(\underline{x})\\
+f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z)
+\end{aligned}
+\]
+\end{itemize}
+
+\medskip
+
+{\footnotesize Les fonctions p.r. sont automatiq\textsuperscript{t}
+  totales, mais il sera utile de garder la définition avec
+  $\dasharrow$.\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions primitives récursives : exemples}
+
+\itempoint $f\colon (x,z) \mapsto x+z$ est p.r. :
+\[
+\begin{aligned}
+f(x,0) &= x\\
+f(x,z+1) &= f(x,z)+1
+\end{aligned}
+\]
+{\footnotesize où $x \mapsto x$ et $(x,y,z) \mapsto y+1$ sont p.r.\par}
+
+\medskip
+
+\itempoint $f\colon (x,z) \mapsto x\cdot z$ est p.r. :
+\[
+\begin{aligned}
+f(x,0) &= 0\\
+f(x,z+1) &= f(x,z)+x
+\end{aligned}
+\]
+
+\medskip
+
+\itempoint $f\colon (x,z) \mapsto x^z$ est p.r.
+
+\bigskip
+
+\itempoint $f\colon (x,y,0) \mapsto x, \; (x,y,z) \mapsto y\text{~si~}z\geq 1$ est p.r. :
+\[
+\begin{aligned}
+f(x,y,0) &= x\\
+f(x,y,z+1) &= y
+\end{aligned}
+\]
+
+\medskip
+
+\itempoint $(u,v) \mapsto \max(u-v,0)$ est p.r. (exercice !)
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions primitives récursives : programmation}
+
+Les fonctions p.r. sont celles définies par un \textbf{langage de
+  programmation à boucles bornées}, c'est-à-dire que :
+\begin{itemize}
+\item les variables sont des entiers naturels (illimités !),
+\item les manipulations de base sont permises (constantes,
+  affectations, test d'égalité, conditionnelles),
+\item les opérations arithmétiques basiques sont disponibles,
+\item on peut faire des appels de fonctions \alert{sans récursion},
+\item on ne peut faire que des boucles \alert{de nombre borné
+  \textit{a priori}} d'itérations.
+\end{itemize}
+
+\medskip
+
+Les programmes dans un tel langage \textbf{terminent forcément par
+  construction}.
+
+\bigskip
+
+\textbf{N.B.} $(m,n) \mapsto \langle m,n\rangle := m +
+\frac{1}{2}(m+n)(m+n+1)$ et $\langle m,n\rangle \mapsto m$ et $\langle
+m,n\rangle \mapsto n$ sont p.r.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions primitives récursives : puissance}
+
+En anticipant sur la notion de machine de Turing :
+
+\medskip
+
+\itempoint La fonction $(M,C) \mapsto C'$ qui à une machine de Turing
+$M$ et une configuration (= ruban+état) $C$ de $M$ associe la
+configuration atteinte après $1$ étape d'exécution, \textbf{est p.r.}
+
+\medskip
+
+\itempoint Conséquence : la fonction $(n,M,C) \mapsto C^{(n)}$ qui à
+$n\in\mathbb{N}$ et une machine de Turing $M$ et une configuration $C$
+de $M$ associe la configuration atteinte après $n$ étapes d'exécution,
+\textbf{est p.r.}
+
+{\footnotesize (Par récursion primitive sur le point précédent.)}
+
+\medskip
+
+\itempoint Conséquence : une fonction calculable en complexité
+p.r. par une machine de Turing est elle-même p.r.
+
+\smallskip
+
+{\footnotesize (Calculer une borne p.r. sur le nombre d'étapes, puis
+  appliquer le point précédent.)}
+
+\medskip
+
+\itempoint Réciproquement : une p.r. est calculable en complexité p.r.
+
+\medskip
+
+\itempoint Moralité : p.r. $\Leftrightarrow$ de complexité p.r.
+
+\smallskip
+
+{\footnotesize Notamment $\textbf{EXPTIME} \subseteq \textbf{PR}$.\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions primitives récursives : limitations}
+
+{\footnotesize La classe $\textbf{PR}$ est « à cheval » entre la
+  calculabilité et la complexité.\par}
+
+\bigskip
+
+Rappel : la \textbf{fonction d'Ackermann} (pour $m=2$) définie par :
+\[
+\begin{aligned}
+A(2,n,0) &= 2+n \\
+A(2,1,k+1) &= 2 \\
+A(2,n+1,k+1) &= A(2,\,A(2,n,k+1),\,k)
+\end{aligned}
+\]
+devrait être calculable.  Mais cette définition \alert{n'est pas une
+  récursion primitive} (pourquoi ?).
+
+\bigskip
+
+\itempoint On peut montrer que : si $f \colon \mathbb{N}^k \to
+\mathbb{N}$ est p.r., il existe $r$ tel que
+\[
+f(x_1,\ldots,x_k) \leq A(2,\, (x_1+\cdots+x_k+2),\, r)
+\]
+
+\medskip
+
+\itempoint Notamment, $r \mapsto A(2, 2, r)$ \textbf{n'est pas p.r.}
+
+\medskip
+
+Pourtant, \alert{elle est bien définie par un algorithme} clair (et
+terminant clairement).
+
 \end{frame}
 %
 \end{document}