Simple exercise illustrating the s-m-n theorem for programmatic composition.

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}
+
 
 %
 %