From 3df9f8d0e89d361255a87a21e8e5426b5d3637b8 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Sat, 12 Jul 2025 17:56:54 +0200 Subject: An easy computability exercise. --- exercices-inf110.tex | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) 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} + % % -- cgit v1.2.3