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