diff options
| -rw-r--r-- | exercices-inf110.tex | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/exercices-inf110.tex b/exercices-inf110.tex index 2f00df0..0539356 100644 --- a/exercices-inf110.tex +++ b/exercices-inf110.tex @@ -1294,6 +1294,46 @@ rappelle que l'intention d'un programme (son code) n'est pas la même chose que l'extension (ce qu'il calcule). \end{corrige} +% + +\exercice\ (${\star}$)\par\nobreak + +Soit $h\colon \mathbb{N} \dasharrow \mathbb{N}$ une fonction partielle +calculable. Montrer qu'il existe une fonction primitive récursive $H$ +qui à $e \in \mathbb{N}$ associe un $e'$ tel que $\varphi_{e'} = +h\circ \varphi_e$ (c'est-à-dire que $\varphi_{e'}(n) = +h(\varphi_e(n))$, à condition que $m := \varphi_e(n)$ soit défini et +que $h(m)$ le soit). On rédigera très soigneusement. + +\begin{corrige} +\emph{Première approche possible :} En se rappelant la manière dont on +a numéroté les fonctions générales récursives, $e' = \dbllangle 3, 1, +d, e\dblrangle$ convient, où $d$ est un code de $h$ (c'est-à-dire $h = +\varphi_{d}$), or la fonction $e \mapsto \dbllangle 3, 1, d, +e\dblrangle$ est primitive récursive. + +\emph{Deuxième approche possible :} On considère l'algorithme qui, +donné $e$ et $n$, calcule d'abord $\varphi_e(n)$ (ceci est faisable +grâce à l'existence d'un interpréteur universel), puis lui applique +$h$ (ceci est faisable car $h$ est calculable), et renvoie le +résultat. Ceci calcule la fonction $(e,n) \mapsto h(\varphi_e(n))$, +qui est donc calculable : appelons $p$ un code de celle-ci comme +fonction générale récursive. Par le théorème s-m-n (et en notant +comme dans le cours $s_{1,1}$ la fonction de substitution d'une +variable dans un programme de deux variables) on a +$\varphi_{s_{1,1}(p,e)}(n) = \varphi_p(e,n) = h(\varphi_e(n)) = +(h\circ\varphi_e)(n)$, donc la fonction $H \colon n \mapsto +s_{1,1}(p,e)$ convient, et elle est bien primitive récursive. + +\emph{Remarque :} La première approche a l'avantage de fonctionner +encore pour les fonctions primitives récursives (i.e., si $h$ est +supposée primitive récursive et qu'on remplace $\varphi_e$ par la +numérotation correspondante $\psi_e$ des fonctions primitives +récursives. Elle a l'inconvénient de dépendre des détails du codage +des fonctions générales récursives. La seconde approche montre que +cette dépendance est illusoire. +\end{corrige} + % % |