From ef5fdfe2aacad1a66fe294640f2674f95bc36817 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 18 Oct 2023 12:30:35 +0200 Subject: General recursive functions: numbering, computation trees, universality, normal form. --- transp-inf110-01-calc.tex | 240 +++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 238 insertions(+), 2 deletions(-) diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex index 8f1c3e6..d693a3d 100644 --- a/transp-inf110-01-calc.tex +++ b/transp-inf110-01-calc.tex @@ -327,7 +327,7 @@ entiers. \bigskip -\itempoint\alert{Ne pas utiliser dans la vraie vie} (hors calculabilité) ! +\itempoint\textcolor{orange}{Ne pas utiliser dans la vraie vie} (hors calculabilité) ! \end{frame} % @@ -918,6 +918,12 @@ lever ces limitations. On va \alert{autoriser les boucles infinies}. non-terminaisons, donc on doit passer par des \alert{fonctions partielles}. +\bigskip + +{\footnotesize\textbf{N.B.} Terminologie confuse : fonctions + « générales récursives » ? juste « récursives » ? « récursives + partielles » ? « calculables » ? « calculables partielles » ?\par} + \end{frame} % \begin{frame} @@ -949,6 +955,7 @@ Concrètement, penser à $\mu g$ comme la fonction \end{frame} % \begin{frame} +\label{general-recursive-definition} \frametitle{Fonctions générales récursives : définition} \itempoint $\textbf{R}$ est la plus petite classe de fonctions @@ -974,9 +981,238 @@ f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z) \] \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. + \mathbb{N}^k \dasharrow \mathbb{N}$ est récursive + (\alert{$\leftarrow$ nouveau !}). +\end{itemize} + +\medskip + +Cette fois le langage \alert{permet les boucles non bornées} ! + +\end{frame} +% +\begin{frame} +\frametitle{Fonctions générales récursives : numérotation} + +On définit $\varphi_e^{(k)}\colon \mathbb{N}^k \dasharrow \mathbb{N}$ par +induction suivant la déf\textsuperscript{n} de $\mathbf{R}$ +(cf. transp. \ref{general-recursive-definition}) : +\begin{itemize} +\item si $e = \dbllangle 0, k, i\dblrangle$ alors + $\varphi_e^{(k)}(x_1\ldots,x_k) = x_i$ (projections) ; +\item si $e = \dbllangle 1, k, c\dblrangle$ alors + $\varphi_e^{(k)}(x_1\ldots,x_k) = c$ (constantes) ; +\item si $e = \dbllangle 2\dblrangle$ alors + $\varphi_e^{(k)}(x) = x+1$ (successeur) ; +\item si $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et $g_i + := \varphi_{c_i}^{(k)}$ et $h := \varphi_d^{(\ell)}$, alors + $\varphi_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 := + \varphi_c^{(k)}$ et $h := \varphi_d^{(k+2)}$, alors (récursion primitive) +\[ +\begin{aligned} +\varphi_e^{(k+1)}(\underline{x},0) &= g(\underline{x})\\ +\varphi_e^{(k+1)}(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z) +\end{aligned} +\] +\item si $e = \dbllangle 5, k, c\dblrangle$ et $g := + \varphi_c^{(k+1)}$, alors $\varphi_e^{(k)} = \mu g$. +\end{itemize} +(Autres cas non définis, i.e., donnent $\uparrow$.) + +\bigskip + +\itempoint Alors $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est +récursive \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \varphi_e^{(k)})$. + +\end{frame} +% +\begin{frame} +\frametitle{Fonctions générales récursives : universalité} + +Cette fois, \alert{il existe bien} une fonction récursive universelle, +c'est-à-dire : + +\smallskip + +\itempoint $(e,\underline{x}) \mapsto \varphi_e^{(k)}(\underline{x})$ +est récursive : $\exists u_k \in +\mathbb{N}.\,(\varphi_{u_k}^{(k+1)}(e, \underline{x}) = +\varphi_e^{(k)}(\underline{x}))$. + +{\footnotesize Variante : $\exists u.\,(\varphi_{u}^{(1)}(\dbllangle + e, \underline{x}\dblrangle) = \varphi_e^{(k)}(\underline{x}))$ en + codant programme $e$ et arguments $\underline{x}$ en un entier.\par} + +\bigskip + +Qu'est-ce que ça nous dit ? + +\medskip + +\itempoint\textcolor{blue}{Mathématiquement}, que $\varphi^{(k)}$ est +elle-même récursive en tous ses arguments, y compris l'indice de +numérotation. + +\medskip + +\itempoint\textcolor{blue}{Informatiquement}, qu'il existe un +\alert{interpréteur} $u$ du langage général récursif dans le langage +général récursif. + +\medskip + +\itempoint\textcolor{blue}{Philosophiquement}, que la notion +d'« exécuter un algorithme » est \alert{elle-même algorithmique}. + +\bigskip + +\textcolor{brown}{Mais comment le prouver ?} On va esquisser une +méthode par \textbf{arbres de calcul}. + +\end{frame} +% +\begin{frame} +\frametitle{Arbres de calcul pour les fonctions récursives} + +Un \textbf{arbre de calcul} de $\varphi_e^{(k)}(\underline{x})$ de +résultat $y$ est un arbre (fini, enraciné, ordonné, étiqueté par des +entiers naturels) qui « atteste » que $\varphi_e^{(k)}(\underline{x}) += y$ en détaillant les étapes du calcul. + +\medskip + +\begin{itemize} +\item La racine est étiquetée « $\varphi_e^{(k)}(\underline{x}) = y$ » + ou plutôt « $\dbllangle e, \dbllangle \underline{x}\dblrangle, + y\dblrangle$ ». +\item Le sous-arbre porté par chaque fils de la racine est lui-même un + arbre de calcul pour une sous-expression utilisée dans le calcul de + $f(\underline{x}) = y$. +\item Pour les cas projection, constante, successeur, il n'y a pas de + fils. +\item Pour la composition + $h(g_1(\underline{x}),\ldots,g_\ell(\underline{x}))$, les fils + portent des arbres de calcul attestant + $g_1(\underline{x})=v_1,\ldots,g_\ell(\underline{x})=v_\ell$ et + $h(\underline{v})=y$. +\item Pour la récursion primitive $f(\underline{x},z)$, on a soit un + seul fils arbre de calcul attestant $g(\underline{x})=y$ lorsque + $z=0$ soit deux fils arbres de calcul attestant + $f(\underline{x},z')=v$ et $h(\underline{x},v,z')=y$ lorsque + $z=z'+1$. +\item Pour $f = \mu g$, on a des fils attestant + $g(0,\underline{x})=v_0,\ldots,g(y,\underline{x})=v_y$. +\end{itemize} + +\medskip + +On a $\varphi_e^{(k)}(\underline{x}) = y$ \alert{ssi} il en existe un +arbre de calcul qui l'atteste. + +\end{frame} +% +\begin{frame} +\frametitle{Arbres de calcul : formalisation} + +Formellement : + +{\footnotesize +\begin{itemize} +\item la racine est étiquetée $\dbllangle e, \dbllangle + \underline{x}\dblrangle, y\dblrangle$, +\item soit $e$ est $\dbllangle 0, k, i\dblrangle$ ou $\dbllangle 1, k, + c\dblrangle$ ou $\dbllangle 2\dblrangle$, elle n'a pas de + fils, et $y$ vaut resp\textsuperscript{t} $x_i$, $c$ ou $x+1$, +\item soit $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et + les fils portent des arbres de calculs attestant + $\varphi_{c_1}^{(k)}(\underline{x})=v_1$, ..., + $\varphi_{c_\ell}^{(k)}(\underline{x})=v_\ell$ et + $\varphi_d^{(\ell)}(\underline{v})=y$. +\item soit $e = \dbllangle 4, k', d, c\dblrangle$ où $k'=k-1$ et +\begin{itemize}\footnotesize +\item soit $x_k = 0$ et l'unique fils porte arbre de calcul attestant + $\varphi_{c}^{(k')}(x_1,\ldots,x_{k'})=y$, +\item soit $x_k = z+1$ et les deus fils portent arbres de calcul + attestant $\varphi_{e}^{(k'+1)}(x_1,\ldots,x_{k'},z)=v$ et + $\varphi_{d}^{(k'+2)}(x_1,\ldots,x_{k'},v,z)=y$. +\end{itemize} +\item soit $e = \dbllangle 5, k, c\dblrangle$ et les fils portent des + arbres de calcul attestant $\varphi_{c}^{(k+1)}(0,x_1,\ldots,x_k)=v_0$, + ..., $\varphi_{c}^{(k+1)}(y,x_1,\ldots,x_k)=v_y$ où $v_y=0$ et + $v_0,\ldots,v_{y-1} > 0$. +\end{itemize} +\par} + +On encode l'arbre $\mathscr{T}$ par l'entier +$\operatorname{code}(\mathscr{T}) := \dbllangle n, +\operatorname{code}(\mathscr{T}_1), \ldots, +\operatorname{code}(\mathscr{T}_s)\dblrangle$ où $n$ est l'étiquette +de la racine et $\mathscr{T}_1,\ldots,\mathscr{T}_s$ les codes des +sous-arbres portés par les fils de celle-ci. + +\end{frame} +% +\begin{frame} +\frametitle{Arbres de calcul $\Rightarrow$ universalité} + +Les points-clés : +\begin{itemize} +\item On a $\varphi_e^{(k)}(\underline{x}) = y$ \alert{ssi} il existe + un arbre de calcul $\mathscr{T}$ l'attestant. +\item Vérifier si $\mathscr{T}$ est un arbre de calcul valable est + \alert{primitif récursif} en $\operatorname{code}(\mathscr{T})$. + (On peut vérifier les règles à chaque nœud avec des boucles + bornées.) +\item De même, extraire $e,\underline{x},y$ de $\mathscr{T}$ est + primitif récursif. \end{itemize} +\bigskip + +D'où l'algorithme « universel » pour calculer +$\varphi_e^{(k)}(\underline{x})$ en fonction de $e,\underline{x}$ : +\begin{itemize} +\item parcourir $n=0,1,2,3,4,\ldots$, +\item pour chacun, tester s'il code un arbre de calcul valable de + $\varphi_e^{(k)}(\underline{x})$, +\item si oui, terminer et renvoyer le $y$ contenu. +\end{itemize} + +La boucle non-bornée est précisément ce que permet $\mu$. Tout le +reste est p.r. + +$\Rightarrow$ Ceci montre l'existence de $u$. + +\bigskip + +\textcolor{orange}{Ne pas coder un interpréteur comme ça dans la vraie vie !} + +\end{frame} +% +\begin{frame} +\frametitle{Théorème de la forme normale} + +On a montré un peu plus que l'universalité : on peut exécuter +n'importe quel algorithme avec une \alert{unique boucle non bornée}. +Plus exactement : + +\bigskip + +\itempoint\textbf{Théorème de la forme normale} (Kleene) : il existe +un prédicat p.r. $T$ sur $\mathbb{N}^3$ et une fonction p.r. $U \colon +\mathbb{N} \to \mathbb{N}$ tels que : +\[ +\varphi_e^{(k)}(x_1,\ldots,x_k) += U(\mu T(e,\dbllangle x_1,\ldots,x_k\dblrangle)) +\] + +Précisément, $T(n, e,\dbllangle x_1,\ldots,x_k\dblrangle)$ teste si +$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. + \end{frame} % \end{document} -- cgit v1.2.3