diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 331 |
1 files changed, 322 insertions, 9 deletions
diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index d693a3d..a10d571 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -420,6 +420,34 @@ est calculable (répondre « oui » ou « ... » selon que $n\in A$ ou $n\no \end{frame} % +\begin{frame} +\frametitle{Point terminologique : « récursif »} + +Le mot « récursif » et ses cognats (« récursion », « récursivité ») a +plusieurs sens \alert{apparentés mais non identiques} : +\begin{itemize} +\item « récursif » = « défini par récurrence » (Dedekind 1888) + $\rightarrow$ fonctions primitives récursives, générales + récursives (cf. après) ; +\item « récursif » = « calculable » (par glissement à cause de la + définition de la calculabilité par les fonctions générales + récursives) ; +\item « récursif » = « faisant appel à lui-même dans sa définition » + (appels récursifs, récursivité en informatique). +\end{itemize} + +\bigskip + +On va définir les fonctions « \textbf{primitives récursives} » +(1\textsuperscript{er} sens) et « \textbf{(générales) récursives} » +(1\textsuperscript{er} et aussi 2\textsuperscript{e} sens) ci-après. + +\medskip + +Pour le 3\textsuperscript{e} sens, on dira « appels récursifs ». + +\end{frame} +% \section{Fonctions primitives récursives} \begin{frame} \frametitle{Fonctions primitives récursives : aperçu} @@ -549,7 +577,7 @@ Les fonctions p.r. sont celles définies par un \textbf{langage de \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 peut faire des appels de fonctions \alert{sans appels récursifs}, \item on ne peut faire que des boucles \alert{de nombre borné \textit{a priori}} d'itérations. \end{itemize} @@ -715,6 +743,7 @@ Notamment : \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 \[ +(\forall e,\underline{x},\underline{y})\quad \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) \] @@ -764,7 +793,7 @@ somefunc("str="+quote(str)+str); \smallskip $\Rightarrow$ La fonction \texttt{somefunc} (arbitraire) est appelée -avec le code source du programme tout entier. +avec le code source du programme \alert{tout entier}. \medskip @@ -784,19 +813,17 @@ langage. 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}) +(\forall\underline{x})\quad \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}) +(\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x}) \text{~si~}e := b(k,d) \] @@ -821,7 +848,8 @@ sont p.r.\qed \end{frame} % \begin{frame} -\frametitle{Fonctions primitives récursives : pas d'universalité} +\label{primitive-recursive-no-universality} +\frametitle{Fonctions primitives récursives : absence 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) = @@ -858,7 +886,7 @@ sauver le théorème s-m-n. \end{frame} % \begin{frame} -\frametitle{Fonctions primitives récursives : pas d'universalité (variante)} +\frametitle{Fonctions primitives récursives : absence d'universalité (variante)} Rappel : la \textbf{fonction d'Ackermann} est définie par : \[ @@ -912,6 +940,11 @@ couvrent pas la notion générale d'algorithme : \itempoint On veut modifier la définition des fonctions p.r. pour lever ces limitations. On va \alert{autoriser les boucles infinies}. +$\rightarrow$ Fonctions \textbf{générales récursives} ou simplement +\textbf{récursives}. + +Ce seront aussi nos fonctions \textbf{calculables} ! + \bigskip \itempoint En ce faisant, on obtient forcément des cas de @@ -920,7 +953,7 @@ non-terminaisons, donc on doit passer par des \alert{fonctions \bigskip -{\footnotesize\textbf{N.B.} Terminologie confuse : fonctions +{\footnotesize\textbf{N.B.} Terminologie fluctuante : fonctions « générales récursives » ? juste « récursives » ? « récursives partielles » ? « calculables » ? « calculables partielles » ?\par} @@ -1213,6 +1246,286 @@ $n$ est le code d'un arbre de calcul valable de $\varphi_e^{(k)}(\underline{x})$, et $U$ extrait le résultat de cet arbre. +\medskip + +\centerline{*} + +\medskip + +Exemple d'application : \textbf{lancement en parallèle} : +\[ +U(\mu(T(e_1,\dbllangle\underline{x}\dblrangle)\text{~ou~}T(e_2,\dbllangle\underline{x}\dblrangle))) +\] +définit (de façon p.r. en $e_1,e_2$) un $e$ tel que +\[ +\varphi_e(\underline{x}){\downarrow} \;\Longleftrightarrow\; +\varphi_{e_1}(\underline{x}){\downarrow}\text{~ou~} +\varphi_{e_2}(\underline{x}){\downarrow} +\] + +\end{frame} +% +\begin{frame} +\frametitle{Théorème s-m-n (version générale récursive)} + +Exactement comme la version p.r. : + +\smallskip + +\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 +\[ +(\forall e,\underline{x},\underline{y})\quad +\varphi^{(n)}_{s_{m,n}(e,x_1,\ldots,x_m)}(y_1,\ldots,y_n) = +\varphi^{(m+n)}_e(x_1,\ldots,x_m,\,y_1,\ldots,y_n) +\] + +\bigskip + +Noter que $s_{m,n}$ est \alert{p.r.} même si on s'intéresse ici aux +fonctions générales récursives. + +\medskip + +Les manipulations de programmes sont typiquement p.r. (même si les +programmes manipulés sont des fonctions générales récursives). + +\end{frame} +% +\begin{frame} +\frametitle{Le théorème de récursion de Kleene (version générale récursive)} + +Exactement comme la version p.r. : + +\smallskip + +\itempoint\textbf{Théorème} (Kleene) : si $h \colon \mathbb{N}^{k+1} +\dasharrow \mathbb{N}$ est récursive, il existe $e$ tel que +\[ +(\forall\underline{x})\quad \varphi^{(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 +\[ +(\forall\underline{x})\quad \varphi^{(k)}_e(\underline{x}) = \varphi^{(k+1)}_d(e,\underline{x}) +\text{~si~}e := b(k,d) +\] + +\bigskip + +\underline{Même 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 $= +\varphi_c^{(k+1)}(\underline{x})$. Alors +\[ +\varphi_{s(c,c)}^{(k)}(\underline{x}) += \varphi_{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{Le théorème du point fixe de Kleene-Rogers} + +Reformulation du théorème de récursion utilisant l'universalité : + +\smallskip + +\itempoint\textbf{Théorème} (Kleene-Rogers) : si $F \colon \mathbb{N} +\to \mathbb{N}$ est récursive \emph{totale} et $k\in\mathbb{N}$, il +existe $e$ tel que +\[ +\varphi_e^{(k)} = \varphi_{F(e)}^{(k)} +\] + +\bigskip + +\underline{Preuve :} $h\colon (e,\underline{x}) \mapsto +\varphi_{F(e)}^{(k)}(\underline{x})$ est récursive car $e \mapsto +F(e)$ l'est et que $(e',\underline{x}) \mapsto +\varphi_{e'}^{(k)}(\underline{x})$ l'est (universalité). Par le +théorème de récursion, il existe $e$ tel que +$\varphi^{(k)}_e(\underline{x}) = h(e,\underline{x}) = +\varphi_{F(e)}^{(k)}(\underline{x})$.\qed + +\end{frame} +% +\begin{frame} +\frametitle{Récursion !} + +Le langage des fonctions générales récursives, +\textcolor{orange}{malgré le nom} ne permet pas les définitions par +appels récursifs. + +\smallskip + +{\footnotesize Uniquement des opérations élémentaires, appels de + fonctions précédemment définies, boucles.\par} + +\bigskip + +Comment permettre quand même les appels récursifs ? + +\smallskip + +\alert{Par le théorème de récursion de Kleene !} (ou théorème du point fixe) : + +\begin{itemize} +\item je veux définir (comme fonction générale récursive) une fonction + $f$ dont la définition fait appel à $f$ elle-même : +\item par le théorème de récursion de Kleene (« astuce de Quine »), je + peux supposer que $f$ a accès à son propre numéro (« code source »), +\item je convertis chaque appel à $f$ depuis $f$ en un appel à la + fonction universelle (interpréteur) sur le numéro de $f$. +\end{itemize} + +\bigskip + +\textcolor{orange}{Ne pas implémenter la récursion comme ça dans la vraie vie !} + +\end{frame} +% +\begin{frame} +\frametitle{\textit{Kids, don't try this at home !}} + +Pseudocode : + +\smallskip + +{\footnotesize\texttt{% +fibonacci(n) \{\\ +str = "self = \textbackslash"fibonacci(n) \{\textbackslash \textbackslash nstr = \textbackslash" + quote(str) + str;\textbackslash n\textbackslash\\ +if (n==0 || n==1) return n;\textbackslash n\textbackslash\\ +return interpret(self, n-1) + interpret(self, n-2);\textbackslash n\textbackslash\\ +\}";\\ +self = "fibonacci(n) \{\textbackslash nstr = " + quote(str) + str;\\ +if (n==0 || n==1) return n;\\ +return interpret(self, n-1) + interpret(self, n-2);\\ +\} +}\par} + +\medskip + +\centerline{*} + +\medskip + +\textbf{Défi :} trouver explicitement un $e$ tel que $\varphi^{(3)}_e$ +soit la fonction d'Ackermann. + +\end{frame} +% +\begin{frame} +\frametitle{Le problème de l'arrêt} + +{\footnotesize Le terme « problème de l'arrêt » prendra plus de sens + pour les machines de Turing.\par} + +\medskip + +\itempoint\textbf{Problème :} donné un programme $e$ (mettons d'arité +$k=1$) et une entrée $x$ à ce programme, comment savoir si $e$ termine +(c'est-à-dire $\varphi^{(1)}_e(x)\downarrow$) ou non +($\varphi^{(1)}_e(x)\uparrow$) ? + +\medskip + +Cette question est-elle \alert{algorithmique} ? + +\bigskip + +\textbf{Réponse} de Turing : \alert{non}. + +\end{frame} +% +\begin{frame} +\frametitle{L'indécidabilité du problème de l'arrêt} + +\itempoint\textbf{Théorème} (Turing) : il n'existe pas de fonction +récursive $h\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $h(e,x) = 1$ +si $\varphi^{(1)}_e(x)\downarrow$ et $h(e,x) = 0$ si +$\varphi^{(1)}_e(x)\uparrow$. + +\bigskip + +\underline{Preuve :} par l'absurde : si un tel $h$ existe, alors la +fonction +\[ +v\colon (e,x) \mapsto \left\{ +\begin{array}{ll} +42&\text{~si~}h(e,x) = 0\\ +\uparrow&\text{~si~}h(e,x) = 1\\ +\end{array} +\right. +\] +est générale récursive (tester is $h(e,x)=0$, si oui renvoyer $42$, +sinon faire une boucle infinie, p.ex. $\mu(x\mapsto 1)$). + +Par le théorème de récursion de Kleene, il existe $e$ tel que +$\varphi^{(1)}_e(x) = v(e,x)$. + +Si $\varphi^{(1)}_e(x)\downarrow$ alors $h(e,x) = 1$ donc +$v(e,x)\uparrow$ donc $\varphi^{(1)}_e(x)\uparrow$, une contradiction. +Si $\varphi^{(1)}_e(x)\uparrow$ alors $h(e,x) = 0$ donc +$v(e,x)\downarrow$ donc $\varphi^{(1)}_e(x)\downarrow$, une +contradiction.\qed + +\bigskip + +\itempoint Intuition de la preuve : supposons que j'aie un moyen +algorithmique $h$ pour savoir si un algorithme termine ou pas, je peux +lui demander ce que « je » vais faire (astuce de Quine), et faire le +contraire, ce qui conduit à un paradoxe. + +\end{frame} +% +\begin{frame} +\frametitle{L'indécidabilité du problème de l'arrêt : redite} + +{\footnotesize Notons $\varphi$ pour $\varphi^{(1)}$.\par} + +\smallskip + +\itempoint\textbf{Théorème} (Turing) : il n'existe pas de fonction +récursive $h\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $h(e,x) = 1$ +si $\varphi_e(x)\downarrow$ et $h(e,x) = 0$ si $\varphi_e(x)\uparrow$. + +\bigskip + +\underline{Preuve} (incluant celle du théorème de récursion) : +considérons la fonction $v\colon \mathbb{N} \dasharrow \mathbb{N}$ qui +à $e$ associe $42$ si $h(e,e)=0$ et $\uparrow$ (non définie) si +$h(e,e)=1$. + +Supposons par l'absurde $h$ est calculable : alors cette fonction +(partielle) $v$ est calculable, disons $v = \varphi_c$. + +Si $\varphi_c(c)\downarrow$ alors $h(c,c)=1$ donc $v(c)\uparrow$, +c'est-à-dire $\varphi_c(c)\uparrow$, une contradiction. Si +$\varphi_c(c)\uparrow$ alors $h(c,c)=0$ donc $v(c)\downarrow$, +c'est-à-dire $\varphi_c(c)\downarrow$, une contradiction.\qed + +\bigskip + +C'est un \alert{argument diagonal} : on utilise $h$ pour construire +une fonction qui diffère en tout point de la diagonale $c \mapsto +\varphi_c(c)$, donc elle ne peut pas être une $\varphi_c$. + +\medskip + +Pour les fonctions p.r. (terminent toujours !), le même argument +diagonal donnait l'inexistence d'un programme universel +(transp. \ref{primitive-recursive-no-universality}). + \end{frame} % \end{document} |