An exercise on Kleene's recursion theorem with a slight "paradox".

1 files changed, 55 insertions, 0 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index f979796..388fec4 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -1238,6 +1238,61 @@ s'appliquer encore quand on échange $X$ et $Y$, ce qui contredit le
 fait qu'il renvoie toujours le bon choix.)
 \end{corrige}
 
+%
+
+\exercice\ (${\star}{\star}{\star}$)\par\nobreak
+
+\textbf{(1)} Montrer qu'il existe un programme $p$ tel que
+$\varphi_p(q) = \varphi_q(q)$ pour tout $q$ et que $\varphi_p(p) = 42$
+(autrement dit, quand on lui fournit en entrée un autre programme $q$,
+le programme $p$ exécute $q$ sur $q$, mais par ailleurs $p$ exécuté
+sur lui-même doit renvoyer $42$).  On expliquera soigneusement
+l'utilisation du théorème de récursion de Kleene ici.
+
+\textbf{(2)} On construit $p'$ de façon analogue à la question
+précédente, mais en remplaçant $42$ par $1729$.  Que donne le résultat
+de $p$ exécuté sur $p'$ ?  Et de $p'$ exécuté sur $p$ ?  Que dire des
+fonctions partielles $\varphi_p$ et $\varphi_{p'}$ ?
+
+\begin{corrige}
+\textbf{(1)} Le programme $p$ fonctionne ainsi : il teste si le
+programme $q$ qu'on lui a passé en entrée est $p$ lui-même (cette
+autoréférence est permise par l'astuce de Quine) et, si oui,
+renvoie $42$, sinon, il invoque la fonction universelle $(e,i) \mapsto
+\varphi_e(i)$ pour calculer $\varphi_q(q)$.
+
+De façon plus soigneuse et formelle : soit $h(p,q)$ valant $42$ si
+$q=p$ et $\varphi_q(q)$ sinon ; cette fonction partielle $h \colon
+\mathbb{N}^2 \dasharrow \mathbb{N}$ est manifestement récursive (étant
+calculée par l'algorithme : « comparer les deux arguments, renvoyer
+$42$ s'ils sont égaux, et sinon invoquer la fonction universelle sur
+le second argument deux fois »).  Par le théorème de récursion de
+Kleene, il existe $p$ tel que $\varphi_p(q) = h(p,q)$ : on a donc bien
+$\varphi_p(p) = 42$ et $\varphi_p(q) = \varphi_q(q)$ pour tout
+autre $q$ (mais pour $q=p$ cette relation est triviale donc elle vaut
+encore).
+
+\textbf{(2)} Le programme $p$ exécuté sur $p'$ renvoie $\varphi_p(p')
+= \varphi_{p'}(p') = 1729$ (la première égalité découlant de la
+définition de $p$ et la seconde de celle de $p'$).  Symétriquement, le
+programme $p'$ exécuté sur $p$ renvoie $\varphi_{p'}(p) = \varphi_p(p)
+= 42$ (la première égalité découlant de la définition de $p'$ et la
+seconde de celle de $p$).
+
+Les fonctions partielles $e \mapsto \varphi_p(e)$ et $e \mapsto
+\varphi_{p'}(e)$ sont \emph{égales} puisque toutes les deux coïncident
+avec $e \mapsto \varphi_e(e)$ en tout point d'après la définition de
+$p$ et $p'$.
+
+\emph{Remarque :} Ce qui rend cet exercice légèrement « paradoxal »,
+c'est qu'on a construit deux programmes $p,p'$ qui calculent la
+\emph{même} fonction (comme on vient de l'expliquer), et pourtant, $p$
+appelé sur lui-même renvoie $42$ tandis que $p'$ appelé sur lui-même
+renvoie $1729$.  Ce n'est pourtant pas si mystérieux quand on se
+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}
+
 
 %
 %