diff options
| -rw-r--r-- | controle-20250129.tex | 200 |
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$. % |