Continue writing test (proof of the Kreisel-Lacombe-Shoenfield theorem).

1 files changed, 172 insertions, 28 deletions

diff --git a/controle-20250129.tex b/controle-20250129.tex
index b268a5f..37001d5 100644
--- a/controle-20250129.tex
+++ b/controle-20250129.tex
@@ -131,10 +131,10 @@ Git: \input{vcline.tex}
 
 \exercice[Problème]
 
-\textbf{Notations :} Dans cet exercice, on notera comme d'habitude
-$\varphi_e\colon\mathbb{N}\dasharrow\mathbb{N}$ la $e$-ième fonction
-générale récursive (i.e., calculable) pour $e\in\mathbb{N}$.  On
-notera
+\textbf{Notations :} Dans tout cet exercice, on notera comme
+d'habitude $\varphi_e\colon\mathbb{N}\dasharrow\mathbb{N}$ la $e$-ième
+fonction générale récursive (i.e., calculable) partielle pour
+$e\in\mathbb{N}$.  On notera
 \[
 \mathsf{PartCalc} := \{\varphi_e \; : \; e\in\mathbb{N}\}
 = \{g\colon\mathbb{N}\dasharrow\mathbb{N} \; : \;
@@ -172,21 +172,22 @@ et $\mathsf{TotCalc} \to \mathbb{N}$ d'autre part.
 \medskip
 
 \textbf{Définition :} (A) Une fonction (totale !) $F\colon
-\mathsf{PartCalc} \to \mathbb{N}$ est dite \emph{calculable} lorsqu'il
-existe une fonction calculable $\hat F\colon \mathbb{N} \to
-\mathbb{N}$ telle que $\hat F(e) = F(\varphi_e)$ pour tout $e \in
-\mathbb{N}$.\quad (B) De même, une fonction (totale) $F\colon
-\mathsf{TotCalc} \to \mathbb{N}$ est dite calculable lorsqu'il existe
-une fonction calculable $\hat F\colon \mathsf{TotIdx} \to \mathbb{N}$
-telle que $\hat F(e) = F(\varphi_e)$ pour tout $e \in
-\mathsf{TotIdx}$.
+\mathsf{PartCalc} \to \mathbb{N}$ est dite \emph{calculable} lorsque
+la fonction $\hat F\colon \mathbb{N} \to \mathbb{N}$ définie par $\hat
+F(e) = F(\varphi_e)$ est calculable.\quad (B) De même, une fonction
+(totale) $F\colon \mathsf{TotCalc} \to \mathbb{N}$ est dite calculable
+lorsqu'il existe une fonction $\hat F\colon \mathbb{N} \dasharrow
+\mathbb{N}$ partielle calculable telle que telle que $\hat F(e) =
+F(\varphi_e)$ pour tout $e \in \mathsf{TotIdx}$.
 
 \smallskip
 
 En français : une fonctionnelle définie sur l'ensemble des fonctions
 calculables partielles ou partielles est elle-même dite calculable
 lorsqu'il existe un programme qui calcule $F(g)$ à partir du code $e$
-d'un programme calculant $g$.
+d'un programme quelconque calculant $g$.
+
+\smallskip
 
 {\footnotesize
 
@@ -200,10 +201,11 @@ de justifier ce fait, qui est facile), se donner une fonction $F\colon
 fonction $\hat F\colon \mathbb{N} \to \mathbb{N}$ ayant cette
 propriété d'« extensionnalité » ; et de même, se donner une fonction
 $F\colon \mathsf{TotCalc} \to \mathbb{N}$ revient exactement à se
-donner une fonction $\hat F\colon \mathsf{TotIdx} \to \mathbb{N}$ qui
-soit extensionnelle.  La définition ci-dessus dit donc que $F$ est
-calculable losrque la $\hat F$ qui lui correspond est elle-même
-calculable.
+donner une fonction $\hat F\colon \mathsf{TotIdx} \dasharrow
+\mathbb{N}$ qui soit extensionnelle.  La définition ci-dessus dit donc
+que $F$ est calculable lorsque la $\hat F$ qui lui correspond est
+elle-même calculable dans le cas (A), ou la restriction à
+$\mathsf{TotIdx}$ d'une fonction calculable dans le cas (B).
 
 \par}
 
@@ -214,29 +216,171 @@ calculable.
 
 Pour cela, on pourra supposer par l'absurde que $F$ prend deux valeurs
 distinctes, disons $v_1$ et $v_2$, et considérer l'ensemble des $e$
-tels que $F(\varphi_e) = v_1$ (i.e., $\hat F(e) = v_1$).  (Pourquoi
-est-il décidable ?  Et pourquoi est-ce une contradiction ?)
+tels que $F(\varphi_e) = v_1$ (i.e., tels que $\hat F(e) = v_1$).
+(Pourquoi est-il décidable ?  Et pourquoi est-ce une contradiction ?)
 
 \medskip
 
 \textbf{(2)} Expliquer pourquoi il existe des fonctions calculables
 (totales) $F\colon \mathsf{TotCalc} \to \mathbb{N}$ qui ne sont pas
-constantes.
+constantes.  Donner un exemple explicite.
 
 Pour cela, on pourra penser évaluer en un point, c'est-à-dire
-exécuter, le programme qu'on a reçu en argument (on rappellera
-pourquoi on peut faire cela).
+exécuter, le programme dont on a reçu le code en argument (on
+rappellera pourquoi on peut faire cela).
 
 \medskip
 
 Fixons maintenant une fonction calculable $F\colon \mathsf{TotCalc}
-\to \mathbb{N}$.  On cherche à démontrer qu'elle a la propriété
-suivante (« théorème de Kreisel-Lacombe-Shoenfield ») : quelle que
-soit $g \in \mathsf{TotCalc}$, il existe $n_0$ telle que pour toute
-fonction $g' \in \mathsf{TotCalc}$ qui coïncide avec $g$ jusqu'au rang
-$n_0$ (i.e. : $\forall i\leq n_0.\,(g'(i) = g(i))$) on ait $F(g') =
-F(g)$.
+\to \mathbb{N}$, ainsi que la fonction $\hat F\colon \mathbb{N}
+\dasharrow \mathbb{N}$ qui lui correspond d'après le (B) des
+définitions ci-dessus.
+
+Dans les questions (3) à (8) qui suivent, on cherche à démontrer que
+$F$ a la propriété\footnote{Si on sait ce que cela signifie, cette
+propriété peut s'exprimer ainsi : $F$ est continue lorsque
+$\mathsf{TotCalc}$ est muni de la topologie (héritée de la topologie)
+produit sur $\mathbb{N}^{\mathbb{N}}$.} suivante (« théorème de
+Kreisel-Lacombe-Shoenfield ») : quelle que soit $g \in
+\mathsf{TotCalc}$, il existe $n$ telle que pour toute fonction $g' \in
+\mathsf{TotCalc}$ qui coïncide avec $g$ jusqu'au rang $n$ (i.e. :
+$\forall i\leq n.\,(g'(i) = g(i))$) on ait $F(g') = F(g)$.
+
+\medskip
+
+\textbf{Notations :} Soit $\mathsf{NulAPCR}$ l'ensemble des fonctions
+$h\colon\mathbb{N}\to\mathbb{N}$ qui sont nulles à partir d'un certain
+rang, c'est-à-dire telles que $\exists m. \forall i\geq m.\,(h(i) =
+0)$.
+
+\medskip
+
+\textbf{(3)} \textbf{(a)} Expliquer pourquoi $\mathsf{NulAPCR}
+\subseteq \mathsf{TotCalc}$, i.e., pourquoi toute fonction
+$\mathbb{N}\to\mathbb{N}$ nulle à partir d'un certain rang est
+automatiquement calculable.\quad\textbf{(b)} Montrer, plus
+précisément, qu'il existe une fonction calculable $\Gamma\colon
+\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ telle que toute fonction $h
+\in \mathsf{NulAPCR}$ soit de la forme $\Gamma(j,\emdash)$
+(c'est-à-dire $i \mapsto \Gamma(j,i)$) pour un certain $j$.
+(\emph{Indication :} on pourra utiliser un codage de Gödel des suites
+finies d'entiers naturels par des entiers
+naturels $j$.)\quad\textbf{(c)} En déduire qu'il existe $\gamma\colon
+\mathbb{N}\to\mathbb{N}$ calculable telle que toute fonction $h \in
+\mathsf{NulAPCR}$ soit de la forme $\varphi_{\gamma(j)}$ pour un
+certain $j$.  (\emph{Indication :} on pourra utiliser le théorème
+s-m-n.)
+
+\medskip
+
+\textbf{Notations :} Si $g \in \mathsf{TotCalc}$ et $n\in\mathbb{N}$,
+on appellera $\mathcal{B}(g,n) := \{g' \in \mathsf{TotCalc} : \forall
+i\leq n.\,(g'(i) = g(i))\}$ l'ensemble des $g'$ qui coïncident avec
+$g$ jusqu'au rang $n$, et $\mathcal{B}_0(g,n) := \mathcal{B}(g,n) \cap
+\mathsf{NulAPCR}$ celles qui, en outre, sont nulles à partir d'un
+certain rang (c'est-à-dire les fonctions prenant les valeurs
+$g(0),g(1),\ldots,g(n),?,?,\ldots,?,0,0,0,\ldots$).
+
+\medskip
+
+\textbf{(4)} Soit $g \in \mathsf{TotCalc}$ et $n\in\mathbb{N}$.
+Expliquer \emph{brièvement} pourquoi les conclusions de la
+question (3) valent encore en remplaçant $\mathsf{NulAPCR}$ par
+$\mathcal{B}_0(g,n)$ partout.  On notera $\gamma(g,n,j)$ la conclusion
+de la dernière sous-question, c'est-à-dire que toute fonction $h \in
+\mathcal{B}_0(g,n)$ soit de la forme $h = \varphi_{\gamma(g,n,j)}$
+pour un certain $j$.  On expliquera \emph{brièvement} pourquoi
+$\gamma(g,n,j)$ est calculable en fonction de $j$, de $n$ et du code
+(dans $\mathsf{TotIdx}$) d'un programme calculant $g$.
+
+\medskip
+
+Si on n'a pas su traiter la question (4), pour les questions
+suivantes, \textbf{on retiendra juste ceci :} $\gamma(g,n,j)$ est
+calculable, et toute fonction $\mathcal{B}_0(g,n)$ est de la forme
+$\varphi_{\gamma(g,n,j)}$ pour un certain $j$.
+
+\medskip
+
+\textbf{Algorithme A :} Pour $g \in \mathsf{TotCalc}$, on considère
+maintenant le programme prenant deux entrées $d$ et $\ell$, décrit
+informellement ainsi :
+\begin{itemize}
+\item lancer l'exécution de $\varphi_d(0)$ pour au plus $\ell$
+  étapes\footnote{Si on préfère la notion d'arbre de calcul, remplacer
+  par : « rechercher parmi les entiers $n\leq\ell$ un arbre de calcul
+  de $\varphi_d(0)$ », et de même plus loin, remplacer « l'exécution
+  s'est terminée en exactement $n\leq\ell$ étapes » par « $n$ est un
+  arbre de calcul de $\varphi_d(0)$ ».  Cela ne changera rien au
+  problème.} ;
+\item si l'exécution ne s'est pas terminée dans le temps imparti,
+  terminer en renvoyant la valeur $g(\ell)$ ;
+\item sinon, disons si l'exécution s'est terminée en exactement
+  $n\leq\ell$ étapes, lancer une boucle non bornée pour rechercher un
+  $j \in \mathbb{N}$ tel que\footnote{On rappelle à toutes fins utiles
+que $\hat F(\gamma(g,n,j)) = F(\varphi_{\gamma(g,n,j)})$ (c'est la
+définition de $\hat F$).} $\hat F(\gamma(g,n,j)) \neq F(g)$ :
+\begin{itemize}
+\item si un tel $j$ est trouvé, on renvoie
+  $\varphi_{\gamma(g,n,j)}(\ell)$,
+\item sinon, bien sûr, l'algorithme ne termine pas.
+\end{itemize}
+\end{itemize}
+
+\medskip
+
+On notera $g_d(\ell)$ la valeur calculée par cet algorithme A (s'il
+termine).
+
+\medskip
+
+\textbf{(5)} \textbf{(a)} Justifier que les opérations présentées dans
+l'algorithme A ont bien un sens (i.e., que c'est bien un algorithme,
+qu'on a bien défini une fonction $\mathbb{N}\times\mathbb{N}
+\dasharrow \mathbb{N}$ partielle calculable $(d,\ell) \mapsto
+g_d(\ell)$).\quad\textbf{(b)} En déduire qu'il existe une fonction
+calculable totale $e \mapsto e_d$ telle que $g_d = \varphi_{e_d}$ pour
+tout $d$.  (\emph{Indication :} on pourra utiliser le théorème s-m-n.)
+
+\medskip
+
+\textbf{(6)} Soit $\mathscr{H} := \{d\in\mathbb{N} :
+\varphi_d(0)\downarrow\}$ l'ensemble des $d$ tels que l'exécution de
+$\varphi_d(0)$ termine.\quad\textbf{(a)} Lorsque
+$d\not\in\mathscr{H}$, que vaut $g_d$ ? et du coup, que vaut $\hat
+F(e_d)$ ?\quad\textbf{(b)} Montrer que $\{d\in\mathbb{N} : \hat F(e_d)
+= F(g)\}$ est semi-décidable.\quad\textbf{(c)} Le complémentaire
+$\complement\mathscr{H} = \{d\in\mathbb{N} : \varphi_d(0)\uparrow\}$
+de $\mathscr{H}$ est-il semi-décidable ?\quad\textbf{(d)} En déduire
+qu'il existe $d\in\mathscr{H}$ tel que $\hat F(e_d) = F(g)$.
+
+\medskip
+
+\textbf{(7)} On a montré en (6) qu'il existe $d$ tel que
+$\varphi_d(0)\downarrow$ et que $\hat F(e_d) = F(g)$.  Soit $n$ le
+nombre d'étapes d'exécution\footnote{Ou si on préfère : l'arbre de
+calcul.} de $\varphi_d(0)$.  Montrer que pour tout $g' \in
+\mathcal{B}_0(g,n)$ on a $F(g') = F(g)$.  (\emph{Indication :} sinon,
+la recherche d'un $j$ dans l'algorithme A aurait trouvé un $j$ et on
+aurait $g_d = \varphi_{\gamma(g,n,j)}$.)
+
+\medskip
+
+\textbf{(8)} On a montré en (7) que pour tout $g\in\mathsf{TotCalc}$
+il existe $n$ tel que pour tout $g' \in \mathcal{B}_0(g,n)$ on a
+$F(g') = F(g)$.  On considère maintenant $g' \in \mathcal{B}(g,n)$
+(qui n'est plus supposé nul à partir d'un certain rang) : d'après ce
+qu'on vient de dire, il existe $n'$ tel que pour tout $g'' \in
+\mathcal{B}_0(g',n')$ on a $F(g'') = F(g')$.  En justifiant qu'on peut
+trouver $g'' \in \mathcal{B}_0(g,n) \cap \mathcal{B}_0(g',n')$,
+montrer que $F(g') = F(g)$.  Conclure.
+
+\medskip
 
+\textbf{(9)} En observant que l'algorithme A peut s'écrire à partir du
+code d'un programme calculant $g$, justifier que le $n$ dont on a
+montré l'existence en (8) peut être obtenu de façon calculable en
+fonction du code d'un programme calculant $g$.
 
 
 %