The recursion theorem for general recursive functions, and the Halting problem.

1 files changed, 322 insertions, 9 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index d693a3d..a10d571 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -420,6 +420,34 @@ est calculable (répondre « oui » ou « ... » selon que $n\in A$ ou $n\no
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Point terminologique : « récursif »}
+
+Le mot « récursif » et ses cognats (« récursion », « récursivité ») a
+plusieurs sens \alert{apparentés mais non identiques} :
+\begin{itemize}
+\item « récursif » = « défini par récurrence » (Dedekind 1888)
+  $\rightarrow$ fonctions primitives récursives, générales
+  récursives (cf. après) ;
+\item « récursif » = « calculable » (par glissement à cause de la
+  définition de la calculabilité par les fonctions générales
+  récursives) ;
+\item « récursif » = « faisant appel à lui-même dans sa définition »
+  (appels récursifs, récursivité en informatique).
+\end{itemize}
+
+\bigskip
+
+On va définir les fonctions « \textbf{primitives récursives} »
+(1\textsuperscript{er} sens) et « \textbf{(générales) récursives} »
+(1\textsuperscript{er} et aussi 2\textsuperscript{e} sens) ci-après.
+
+\medskip
+
+Pour le 3\textsuperscript{e} sens, on dira « appels récursifs ».
+
+\end{frame}
+%
 \section{Fonctions primitives récursives}
 \begin{frame}
 \frametitle{Fonctions primitives récursives : aperçu}
@@ -549,7 +577,7 @@ Les fonctions p.r. sont celles définies par un \textbf{langage de
 \item les manipulations de base sont permises (constantes,
   affectations, test d'égalité, conditionnelles),
 \item les opérations arithmétiques basiques sont disponibles,
-\item on peut faire des appels de fonctions \alert{sans récursion},
+\item on peut faire des appels de fonctions \alert{sans appels récursifs},
 \item on ne peut faire que des boucles \alert{de nombre borné
   \textit{a priori}} d'itérations.
 \end{itemize}
@@ -715,6 +743,7 @@ Notamment :
 \itempoint\textbf{Théorème s-m-n} (Kleene) : il existe $s_{m,n} \colon
 \mathbb{N}^{m+1} \to \mathbb{N}$ p.r. telle que
 \[
+(\forall e,\underline{x},\underline{y})\quad
 \psi^{(n)}_{s_{m,n}(e,x_1,\ldots,x_m)}(y_1,\ldots,y_n) =
 \psi^{(m+n)}_e(x_1,\ldots,x_m,\,y_1,\ldots,y_n)
 \]
@@ -764,7 +793,7 @@ somefunc("str="+quote(str)+str);
 \smallskip
 
 $\Rightarrow$ La fonction \texttt{somefunc} (arbitraire) est appelée
-avec le code source du programme tout entier.
+avec le code source du programme \alert{tout entier}.
 
 \medskip
 
@@ -784,19 +813,17 @@ langage.
 
 Version formelle de l'astuce de Quine
 
-{\footnotesize (aussi appelé « théorème du point fixe » de Kleene)\par}
-
 \smallskip
 
 \itempoint\textbf{Théorème} (Kleene) : si $h \colon \mathbb{N}^{k+1}
 \dasharrow \mathbb{N}$ est p.r., il existe $e$ tel que
 \[
-\psi^{(k)}_e(\underline{x}) = h(e,\underline{x})
+(\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = h(e,\underline{x})
 \]
 Plus précisément, il existe $b \colon \mathbb{N}^2 \to \mathbb{N}$
 p.r. telle que
 \[
-\psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x})
+(\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x})
 \text{~si~}e := b(k,d)
 \]
 
@@ -821,7 +848,8 @@ sont p.r.\qed
 \end{frame}
 %
 \begin{frame}
-\frametitle{Fonctions primitives récursives : pas d'universalité}
+\label{primitive-recursive-no-universality}
+\frametitle{Fonctions primitives récursives : absence d'universalité}
 
 \itempoint\textbf{Théorème :} il n'existe pas de fonction
 p.r. $u\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $u(e,x) =
@@ -858,7 +886,7 @@ sauver le théorème s-m-n.
 \end{frame}
 %
 \begin{frame}
-\frametitle{Fonctions primitives récursives : pas d'universalité (variante)}
+\frametitle{Fonctions primitives récursives : absence d'universalité (variante)}
 
 Rappel : la \textbf{fonction d'Ackermann} est définie par :
 \[
@@ -912,6 +940,11 @@ couvrent pas la notion générale d'algorithme :
 \itempoint On veut modifier la définition des fonctions p.r. pour
 lever ces limitations.  On va \alert{autoriser les boucles infinies}.
 
+$\rightarrow$ Fonctions \textbf{générales récursives} ou simplement
+\textbf{récursives}.
+
+Ce seront aussi nos fonctions \textbf{calculables} !
+
 \bigskip
 
 \itempoint En ce faisant, on obtient forcément des cas de
@@ -920,7 +953,7 @@ non-terminaisons, donc on doit passer par des \alert{fonctions
 
 \bigskip
 
-{\footnotesize\textbf{N.B.} Terminologie confuse : fonctions
+{\footnotesize\textbf{N.B.} Terminologie fluctuante : fonctions
   « générales récursives » ? juste « récursives » ? « récursives
   partielles » ?  « calculables » ? « calculables partielles » ?\par}
 
@@ -1213,6 +1246,286 @@ $n$ est le code d'un arbre de calcul valable de
 $\varphi_e^{(k)}(\underline{x})$, et $U$ extrait le résultat de cet
 arbre.
 
+\medskip
+
+\centerline{*}
+
+\medskip
+
+Exemple d'application : \textbf{lancement en parallèle} :
+\[
+U(\mu(T(e_1,\dbllangle\underline{x}\dblrangle)\text{~ou~}T(e_2,\dbllangle\underline{x}\dblrangle)))
+\]
+définit (de façon p.r. en $e_1,e_2$) un $e$ tel que
+\[
+\varphi_e(\underline{x}){\downarrow} \;\Longleftrightarrow\;
+\varphi_{e_1}(\underline{x}){\downarrow}\text{~ou~}
+\varphi_{e_2}(\underline{x}){\downarrow}
+\]
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Théorème s-m-n (version générale récursive)}
+
+Exactement comme la version p.r. :
+
+\smallskip
+
+\itempoint\textbf{Théorème s-m-n} (Kleene) : il existe $s_{m,n} \colon
+\mathbb{N}^{m+1} \to \mathbb{N}$ p.r. telle que
+\[
+(\forall e,\underline{x},\underline{y})\quad
+\varphi^{(n)}_{s_{m,n}(e,x_1,\ldots,x_m)}(y_1,\ldots,y_n) =
+\varphi^{(m+n)}_e(x_1,\ldots,x_m,\,y_1,\ldots,y_n)
+\]
+
+\bigskip
+
+Noter que $s_{m,n}$ est \alert{p.r.} même si on s'intéresse ici aux
+fonctions générales récursives.
+
+\medskip
+
+Les manipulations de programmes sont typiquement p.r. (même si les
+programmes manipulés sont des fonctions générales récursives).
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Le théorème de récursion de Kleene (version générale récursive)}
+
+Exactement comme la version p.r. :
+
+\smallskip
+
+\itempoint\textbf{Théorème} (Kleene) : si $h \colon \mathbb{N}^{k+1}
+\dasharrow \mathbb{N}$ est récursive, il existe $e$ tel que
+\[
+(\forall\underline{x})\quad \varphi^{(k)}_e(\underline{x}) =
+h(e,\underline{x})
+\]
+Plus précisément, il existe $b \colon \mathbb{N}^2 \to \mathbb{N}$
+p.r. telle que
+\[
+(\forall\underline{x})\quad \varphi^{(k)}_e(\underline{x}) = \varphi^{(k+1)}_d(e,\underline{x})
+\text{~si~}e := b(k,d)
+\]
+
+\bigskip
+
+\underline{Même preuve :} soit $s := s_{m,1}$ donné par le théorème
+s-m-n.  La fonction $(t,\underline{x}) \mapsto
+h(s(t,t),\underline{x})$ est p.r., disons $=
+\varphi_c^{(k+1)}(\underline{x})$.  Alors
+\[
+\varphi_{s(c,c)}^{(k)}(\underline{x})
+= \varphi_{c}^{(k+1)}(c, \underline{x})
+= h(s(c,c),\underline{x})
+\]
+donc $e := s(c,c)$ convient.  Les fonctions $d \mapsto c \mapsto e$
+sont p.r.\qed
+
+\bigskip
+
+\textbf{Moralité :} \alert{on peut donner aux programmes accès à leur
+  propre numéro} (= « code source »), cela ne change rien.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Le théorème du point fixe de Kleene-Rogers}
+
+Reformulation du théorème de récursion utilisant l'universalité :
+
+\smallskip
+
+\itempoint\textbf{Théorème} (Kleene-Rogers) : si $F \colon \mathbb{N}
+\to \mathbb{N}$ est récursive \emph{totale} et $k\in\mathbb{N}$, il
+existe $e$ tel que
+\[
+\varphi_e^{(k)} = \varphi_{F(e)}^{(k)}
+\]
+
+\bigskip
+
+\underline{Preuve :} $h\colon (e,\underline{x}) \mapsto
+\varphi_{F(e)}^{(k)}(\underline{x})$ est récursive car $e \mapsto
+F(e)$ l'est et que $(e',\underline{x}) \mapsto
+\varphi_{e'}^{(k)}(\underline{x})$ l'est (universalité).  Par le
+théorème de récursion, il existe $e$ tel que
+$\varphi^{(k)}_e(\underline{x}) = h(e,\underline{x}) =
+\varphi_{F(e)}^{(k)}(\underline{x})$.\qed
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Récursion !}
+
+Le langage des fonctions générales récursives,
+\textcolor{orange}{malgré le nom} ne permet pas les définitions par
+appels récursifs.
+
+\smallskip
+
+{\footnotesize Uniquement des opérations élémentaires, appels de
+  fonctions précédemment définies, boucles.\par}
+
+\bigskip
+
+Comment permettre quand même les appels récursifs ?
+
+\smallskip
+
+\alert{Par le théorème de récursion de Kleene !} (ou théorème du point fixe) :
+
+\begin{itemize}
+\item je veux définir (comme fonction générale récursive) une fonction
+  $f$ dont la définition fait appel à $f$ elle-même :
+\item par le théorème de récursion de Kleene (« astuce de Quine »), je
+  peux supposer que $f$ a accès à son propre numéro (« code source »),
+\item je convertis chaque appel à $f$ depuis $f$ en un appel à la
+  fonction universelle (interpréteur) sur le numéro de $f$.
+\end{itemize}
+
+\bigskip
+
+\textcolor{orange}{Ne pas implémenter la récursion comme ça dans la vraie vie !}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{\textit{Kids, don't try this at home !}}
+
+Pseudocode :
+
+\smallskip
+
+{\footnotesize\texttt{%
+fibonacci(n) \{\\
+str = "self = \textbackslash"fibonacci(n) \{\textbackslash \textbackslash nstr = \textbackslash" + quote(str) + str;\textbackslash n\textbackslash\\
+if (n==0 || n==1) return n;\textbackslash n\textbackslash\\
+return interpret(self, n-1) + interpret(self, n-2);\textbackslash n\textbackslash\\
+\}";\\
+self = "fibonacci(n) \{\textbackslash nstr = " + quote(str) + str;\\
+if (n==0 || n==1) return n;\\
+return interpret(self, n-1) + interpret(self, n-2);\\
+\}
+}\par}
+
+\medskip
+
+\centerline{*}
+
+\medskip
+
+\textbf{Défi :} trouver explicitement un $e$ tel que $\varphi^{(3)}_e$
+soit la fonction d'Ackermann.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Le problème de l'arrêt}
+
+{\footnotesize Le terme « problème de l'arrêt » prendra plus de sens
+  pour les machines de Turing.\par}
+
+\medskip
+
+\itempoint\textbf{Problème :} donné un programme $e$ (mettons d'arité
+$k=1$) et une entrée $x$ à ce programme, comment savoir si $e$ termine
+(c'est-à-dire $\varphi^{(1)}_e(x)\downarrow$) ou non
+($\varphi^{(1)}_e(x)\uparrow$) ?
+
+\medskip
+
+Cette question est-elle \alert{algorithmique} ?
+
+\bigskip
+
+\textbf{Réponse} de Turing : \alert{non}.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{L'indécidabilité du problème de l'arrêt}
+
+\itempoint\textbf{Théorème} (Turing) : il n'existe pas de fonction
+récursive $h\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $h(e,x) = 1$
+si $\varphi^{(1)}_e(x)\downarrow$ et $h(e,x) = 0$ si
+$\varphi^{(1)}_e(x)\uparrow$.
+
+\bigskip
+
+\underline{Preuve :} par l'absurde : si un tel $h$ existe, alors la
+fonction
+\[
+v\colon (e,x) \mapsto \left\{
+\begin{array}{ll}
+42&\text{~si~}h(e,x) = 0\\
+\uparrow&\text{~si~}h(e,x) = 1\\
+\end{array}
+\right.
+\]
+est générale récursive (tester is $h(e,x)=0$, si oui renvoyer $42$,
+sinon faire une boucle infinie, p.ex. $\mu(x\mapsto 1)$).
+
+Par le théorème de récursion de Kleene, il existe $e$ tel que
+$\varphi^{(1)}_e(x) = v(e,x)$.
+
+Si $\varphi^{(1)}_e(x)\downarrow$ alors $h(e,x) = 1$ donc
+$v(e,x)\uparrow$ donc $\varphi^{(1)}_e(x)\uparrow$, une contradiction.
+Si $\varphi^{(1)}_e(x)\uparrow$ alors $h(e,x) = 0$ donc
+$v(e,x)\downarrow$ donc $\varphi^{(1)}_e(x)\downarrow$, une
+contradiction.\qed
+
+\bigskip
+
+\itempoint Intuition de la preuve : supposons que j'aie un moyen
+algorithmique $h$ pour savoir si un algorithme termine ou pas, je peux
+lui demander ce que « je » vais faire (astuce de Quine), et faire le
+contraire, ce qui conduit à un paradoxe.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{L'indécidabilité du problème de l'arrêt : redite}
+
+{\footnotesize Notons $\varphi$ pour $\varphi^{(1)}$.\par}
+
+\smallskip
+
+\itempoint\textbf{Théorème} (Turing) : il n'existe pas de fonction
+récursive $h\colon \mathbb{N}^2 \to \mathbb{N}$ telle que $h(e,x) = 1$
+si $\varphi_e(x)\downarrow$ et $h(e,x) = 0$ si $\varphi_e(x)\uparrow$.
+
+\bigskip
+
+\underline{Preuve} (incluant celle du théorème de récursion) :
+considérons la fonction $v\colon \mathbb{N} \dasharrow \mathbb{N}$ qui
+à $e$ associe $42$ si $h(e,e)=0$ et $\uparrow$ (non définie) si
+$h(e,e)=1$.
+
+Supposons par l'absurde $h$ est calculable : alors cette fonction
+(partielle) $v$ est calculable, disons $v = \varphi_c$.
+
+Si $\varphi_c(c)\downarrow$ alors $h(c,c)=1$ donc $v(c)\uparrow$,
+c'est-à-dire $\varphi_c(c)\uparrow$, une contradiction.  Si
+$\varphi_c(c)\uparrow$ alors $h(c,c)=0$ donc $v(c)\downarrow$,
+c'est-à-dire $\varphi_c(c)\downarrow$, une contradiction.\qed
+
+\bigskip
+
+C'est un \alert{argument diagonal} : on utilise $h$ pour construire
+une fonction qui diffère en tout point de la diagonale $c \mapsto
+\varphi_c(c)$, donc elle ne peut pas être une $\varphi_c$.
+
+\medskip
+
+Pour les fonctions p.r. (terminent toujours !), le même argument
+diagonal donnait l'inexistence d'un programme universel
+(transp. \ref{primitive-recursive-no-universality}).
+
 \end{frame}
 %
 \end{document}