An easy computability exercise.HEADmaster

1 files changed, 30 insertions, 0 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index af9a1a7..f8aa3e5 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -1334,6 +1334,36 @@ des fonctions générales récursives.  La seconde approche montre que
 cette dépendance est illusoire.
 \end{corrige}
 
+%
+
+\exercice\ (${\star}$)\par\nobreak
+
+Soit $e \in \mathbb{N}$.  Montrer qu'il existe une fonction primitive
+récursive $j \colon \mathbb{N} \to \mathbb{N}$ telle que
+$\varphi_{j(n)}(k) = \varphi_e(n)$ pour tous $n,k \in \mathbb{N}$.  On
+rédigera très soigneusement.
+
+\begin{corrige}
+\emph{Première rédaction possible :} En se rappelant la manière dont
+on a numéroté les fonctions générales récursives, $j(n) = \dbllangle
+3, 1, e, \dbllangle 1, 1, n \dblrangle\dblrangle$ convient (car
+$\varphi_{\dbllangle 1, 1, n \dblrangle}(k) = n$ et
+$\varphi_{\dbllangle 3, 1, e, c \dblrangle}(k) =
+\varphi_e(\varphi_c(k))$), or la fonction $n \mapsto \dbllangle 3, 1,
+e, \dbllangle 1, 1, n \dblrangle\dblrangle$ est primitive récursive.
+
+\emph{Deuxième rédaction possible :} On considère l'algorithme qui,
+donné $n$ et $k$, ignore $k$ et calcule $\varphi_e(n)$ (ce qui est
+certainement possible car $\varphi_e$ est, par définition,
+calculable).  Ceci montre que la fonction $(n,k) \mapsto \varphi_e(n)$
+est 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,n)}(k) =
+\varphi_p(n,k) = \varphi_e(n)$, donc la fonction $j \colon n \mapsto
+s_{1,1}(p,n)$ convient, et elle est bien primitive récursive.
+\end{corrige}
+
 
 %
 %