diff options
Diffstat (limited to 'transp-inf110-01-calc.tex')
| -rw-r--r-- | transp-inf110-01-calc.tex | 277 |
1 files changed, 265 insertions, 12 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 76543df..c1ef885 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -27,6 +27,8 @@ % \newcommand{\itempoint}{\strut\hbox{\color{beamerstructure}\donotcoloroutermaths$\blacktriangleright$}\nobreak\hskip.5em plus.5em\relax} \renewcommand{\thefootnote}{\textdagger} +\newcommand{\dbllangle}{\mathopen{\langle\!\langle}} +\newcommand{\dblrangle}{\mathclose{\rangle\!\rangle}} % % % @@ -309,10 +311,10 @@ définit une bijection calculable $\mathbb{N}^2 \to \mathbb{N}$. \itempoint Codage des listes finies : par exemple, \[ -\langle\!\langle a_0,\ldots,a_{k-1}\rangle\!\rangle +\dbllangle a_0,\ldots,a_{k-1}\dblrangle := \langle a_0, \langle a_1, \langle\cdots,\langle a_{k-1},0\rangle+1\cdots\rangle+1\rangle+1 \] -définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \to \mathbb{N}$. +définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \to \mathbb{N}$ {\footnotesize (avec $\dbllangle\dblrangle := 0$)}. \bigskip @@ -360,7 +362,13 @@ une fonction $D \to \mathbb{N}$ définie sur une partie $D \subseteq \itempoint Convention : $f(n) = g(m)$ signifie « $f(n)\downarrow$ ssi $g(m)\downarrow$, et $f(n) = g(m)$ si $f(n)\downarrow$ ». (Certains -préfèrent $f(n) \simeq g(m)$ pour ça.) +préfèrent écrire $f(n) \simeq g(m)$ pour ça.) + +\medskip + +\itempoint Convention : si $g_i(\underline{x})\uparrow$ pour un $i$, +on convient que +$h(g_1(\underline{x}),\ldots,g_k(\underline{x}))\uparrow$. \medskip @@ -373,7 +381,7 @@ préfèrent $f(n) \simeq g(m)$ pour ça.) \frametitle{Terminologie à venir (avant-goût)} \itempoint Une fonction partielle $f\colon \mathbb{N} \dasharrow -\mathbb{N}$ est dite \textbf{calculable} (partielle) lorsqu'il existe +\mathbb{N}$ est dite \textbf{calculable partielle} lorsqu'il existe un algorithme qui prend $n$ en entrée et : \begin{itemize} \item termine (en temps fini) et renvoie $f(n)$ lorsque $f(n)\downarrow$, @@ -414,28 +422,64 @@ est calculable (répondre « oui » ou « ... » selon que $n\in A$ ou $n\no % \section{Fonctions primitives récursives} \begin{frame} -\frametitle{Fonctions primitives récursives : définition} +\frametitle{Fonctions primitives récursives : aperçu} + +\itempoint Avant de définir les fonctions générales récursives +($\cong$ calculables), on va commencer par les \textbf{primitives + récursives}, plus restreintes. {\footnotesize« primitive\alert{ment} récursives » ?\par} \bigskip +\itempoint Historiquement antérieures à la calculabilité de +Church-Turing. + +\bigskip + +\itempoint Pédagogiquement utile comme « échauffement ». + +\bigskip + +\itempoint À cheval entre calculabilité (\textbf{PR} est une petite +classe de calculabilité) et complexité (c'est une grosse classe de +complexité). + +\bigskip + +\itempoint Correspond à des programmes à \textbf{boucles bornées a + priori}. + +\bigskip + +\itempoint Énormément d'algorithmes usuels sont p.r. + +\bigskip + +\itempoint Mais p.ex. la fonction d'Ackermann n'est pas p.r. + +\end{frame} +% +\begin{frame} +\label{primitive-recursive-definition} +\frametitle{Fonctions primitives récursives : définition} + \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 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 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ù : +\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 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})\\ @@ -447,7 +491,7 @@ f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z) \medskip {\footnotesize Les fonctions p.r. sont automatiq\textsuperscript{t} - totales, mais il sera utile de garder la définition avec + totales, mais il est commode de garder la définition avec $\dasharrow$.\par} \end{frame} @@ -491,6 +535,7 @@ f(x,y,z+1) &= y \medskip \itempoint $(u,v) \mapsto \max(u-v,0)$ est p.r. (exercice !) +ou même $u\% v$. \end{frame} % @@ -523,7 +568,7 @@ m,n\rangle \mapsto n$ sont p.r. \end{frame} % \begin{frame} -\frametitle{Fonctions primitives récursives : puissance} +\frametitle{Fonctions primitives récursives : lien avec la complexité} En anticipant sur la notion de machine de Turing : @@ -604,4 +649,212 @@ terminant clairement). \end{frame} % +\begin{frame} +\frametitle{Fonctions primitives récursives : numérotation} + +On définit $\psi_e^{(k)}\colon \mathbb{N}^k \dasharrow \mathbb{N}$ par +induction suivant la déf\textsuperscript{n} de $\mathbf{PR}$ +(cf. transp. \ref{primitive-recursive-definition}) : +\begin{itemize} +\item si $e = \dbllangle 0, k, i\dblrangle$ alors + $\psi_e^{(k)}(x_1\ldots,x_k) = x_i$ (projections) ; +\item si $e = \dbllangle 1, k, c\dblrangle$ alors + $\psi_e^{(k)}(x_1\ldots,x_k) = c$ (constantes) ; +\item si $e = \dbllangle 2\dblrangle$ alors + $\psi_e^{(k)}(x) = x+1$ (successeur) ; +\item si $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et $g_i + := \psi_{c_i}^{(k)}$ et $h := \psi_d^{(\ell)}$, alors + $\psi_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 := + \psi_c^{(k)}$ et $h := \psi_d^{(k+2)}$, alors (récursion primitive) +\[ +\begin{aligned} +\psi_e^{(k+1)}(\underline{x},0) &= g(\underline{x})\\ +\psi_e^{(k+1)}(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z) +\end{aligned} +\] +\end{itemize} +(Autres cas non définis, i.e., donnent $\uparrow$.) + +\bigskip + +\itempoint Alors $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est +p.r. \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \psi_e^{(k)})$. + +{\tiny P.ex., $e = \dbllangle 4,1,\dbllangle 3,3,\dbllangle + 2\dblrangle,\dbllangle 0,3,2\dblrangle\dblrangle,\dbllangle + 0,1,1\dblrangle\dblrangle$ définit $\psi^{(2)}_e(x,z) = x+z$ sauf + erreur (probable) de ma part.\par} + +\end{frame} +% +\begin{frame} +\frametitle{Manipulation de programmes (version p.r.)} + +\itempoint Penser à $e$ dans $\psi_e^{(k)}$ comme un programme écrit +en « langage p.r. ». + +\medskip + +\itempoint La fonction $\psi_e^{(k)}\colon \mathbb{N}^k \dasharrow +\mathbb{N}$ « interprète » le programme $e$. + +\medskip + +\centerline{*} + +\bigskip + +La numérotation (transp. précédent) rend p.r. beaucoup de +manipulations usuelles de programmes (composition, récursion, etc.). +Notamment : + +\medskip + +\itempoint\textbf{Théorème s-m-n} (Kleene) : il existe $s_{m,n} \colon +\mathbb{N}^{m+1} \to \mathbb{N}$ p.r. telle que +\[ +\psi^{(n)}_{s_{m,n}(e,x_1,\ldots,x_m)}(y_1,\ldots,y_n) = +\psi^{(m+n)}_e(x_1,\ldots,x_m,\,y_1,\ldots,y_n) +\] + +{\footnotesize\underline{Preuve :} $s_{m,n}(e,\underline{x}) = + \dbllangle 3, n, e, \dbllangle 1, n, x_1\dblrangle, \ldots, + \dbllangle 1, n, x_m\dblrangle, \; \dbllangle 0, n, 1\dblrangle, + \ldots, \dbllangle 0, n, n\dblrangle \dblrangle$ avec nos + conventions (composition de fonctions constantes et de + projections).\qed\par} + +\medskip + +\emph{En clair :} $s_{m,n}$ prend un programme $e$ qui prend $m+n$ +arguments en entrée et « fixe » la valeur des $m$ premiers arguments à +$x_1,\ldots,x_m$, les $n$ arguments suivants ($y_1,\ldots,y_n$) étant +gardés variables. + +\end{frame} +% +\begin{frame} +\frametitle{Digression : l'astuce de Quine (intuition)} + +{\footnotesize Le nom de Willard Van Orman Quine (1908–2000) a été + associé à cette astuce par Douglas Hofstadter. En fait, l'astuce + est plutôt due à Cantor, Turing ou Kleene.\par} + +\smallskip + +\textcolor{teal}{Les mots suivants suivis des mêmes mots entre + guillemets forment une phrase intéressante : « les mots suivants + suivis des mêmes mots entre guillemets forment une phrase + intéressante ».} + +\bigskip + +Pseudocode : + +\smallskip + +{\footnotesize\texttt{% +str="somefunc(code) \{ /*...*/ \}\textbackslash nsomefunc(\textbackslash"str=\textbackslash"+quote(str)+str);\textbackslash n";\\ +somefunc(code) \{ /*...*/ \}\\ +somefunc("str="+quote(str)+str); +}\par} + +\smallskip + +$\Rightarrow$ La fonction \texttt{somefunc} (arbitraire) est appelée +avec le code source du programme tout entier. + +\medskip + +{\footnotesize\textbf{Exercice :} utiliser cette astuce pour écrire un + programme écrivant son propre code source.\par} + +\bigskip + +\textbf{Moralité :} \alert{on peut toujours donner aux programmes + accès à leur code source}, même si ce n'est pas prévu par le +langage. + +\end{frame} +% +\begin{frame} +\frametitle{Le théorème de récursion de Kleene (version p.r.)} + +Version formelle de l'astuce de Quine + +{\footnotesize (aussi appelé « théorème du point fixe » de Kleene)\par} + +\smallskip + +\itempoint\textbf{Théorème} (Kleene) : si $h \colon \mathbb{N}^{k+1} +\dasharrow \mathbb{N}$ est p.r., il existe $e$ tel que +\[ +\psi^{(k)}_e(\underline{x}) = h(e,\underline{x}) +\] +Plus précisément, il existe $b \colon \mathbb{N}^2 \to \mathbb{N}$ +p.r. telle que +\[ +\psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x}) +\text{~si~}e := b(k,d) +\] + +\bigskip + +\underline{Preuve :} soit $s := s_{m,1}$ donné par le théorème s-m-n. +La fonction $(t,\underline{x}) \mapsto h(s(t,t),\underline{x})$ est +p.r., disons $= \psi_c^{(k+1)}(\underline{x})$. Alors +\[ +\psi_{s(c,c)}^{(k)}(\underline{x}) += \psi_{c}^{(k+1)}(c, \underline{x}) += h(s(c,c),\underline{x}) +\] +donc $e := s(c,c)$ convient. Les fonctions $d \mapsto c \mapsto e$ +sont p.r.\qed + +\bigskip + +\textbf{Moralité :} \alert{on peut donner aux programmes accès à leur + propre numéro} (= « code source »), cela ne change rien. + +\end{frame} +% +\begin{frame} +\frametitle{Fonctions primitives récursives : pas d'universalité} + +\itempoint\textbf{Théorème :} il n'existe pas de fonction +p.r. $u\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $u(e,x) = +\psi^{(1)}_e(x)$ si $\psi^{(1)}_e(x)\downarrow$. + +\bigskip + +\underline{Preuve :} par l'absurde : si un tel $u$ existe, alors +$(e,x) \mapsto u(e,x)+1$ est p.r. Par le théorème de récursion de +Kleene, il existe $e$ tel que $\psi^{(1)}_e(x) = u(e,x) + 1$, ce qui +contredit $u(e,x) = \psi^{(1)}_e(x)$.\qed + +\medskip + +\centerline{*} + +\medskip + +\textbf{Moralité :} \alert{un interpréteur du langage p.r. ne peut pas + être p.r.} (preuve : on peut interpréter l'interpréteur +s'interprétant lui-même, en ajoutant un au résultat, ce qui donne un +paradoxe ; c'est un argument diagonal de Cantor). + +\bigskip + +\itempoint Cet argument dépend du théorème s-m-n et du fait que les +fonctions p.r. sont \alert{totales}. Pour définir une théorie +satisfaisante de la calculabilité, on va sacrifier la totalité pour +sauver le théorème s-m-n. + +{\footnotesize Cette même preuve donnera alors la preuve de + l'indécidabilité du problème de l'arrêt.\par} + +\end{frame} +% \end{document} |