Second exercise for 2023 test.

1 files changed, 120 insertions, 0 deletions

diff --git a/controle-20230615.tex b/controle-20230615.tex
index cc97f35..b7eaf30 100644
--- a/controle-20230615.tex
+++ b/controle-20230615.tex
@@ -718,6 +718,126 @@ décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels.
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+\textbf{(1)} La fonction $h\colon \mathbb{N} \to \mathbb{N}$ suivante
+est-elle calculable ?
+\[
+h(0) = 1\;\;,\;\;
+h(1) = 10\;\;,\;\;
+h(2) = 10^{10}\;\;,\;\;
+h(3) = 10^{10^{\scriptstyle 10}}\;\;,\;\;
+h(4) = 10^{10^{\scriptstyle 10^{\scriptstyle 10}}}\;\;,\;\;
+\]
+\[
+\left.\begin{matrix} h(n) = 10^{\scriptstyle 10^{\scriptstyle \cdots^{\scriptstyle 10}}}\end{matrix}\right\} n
+\]
+(Autrement dit, $h(n)$ est une tour d'exponentielle de hauteur $n$ sur
+le nombre $10$.  Bien sûr, $10^{10^{\scriptstyle 10}}$ se comprend
+comme $10^{\big(10^{\scriptstyle 10}\big)}$.)
+
+\begin{corrige}
+La fonction $g\colon n\mapsto 10^n$ est calculable : en effet, on peut
+exécuter une boucle à $n$ itérations en multipliant par $10$ la valeur
+d'une variable en partant de $1$.  On en déduit que la fonction $h$
+est calculable : en effet, on peut exécuter une boucle à $n$
+itérations en appliquant la fonction $g$ à une variable en partant
+de $1$.
+\end{corrige}
+
+\medskip
+
+Fixons maintenant une numérotation (« codage de Gödel ») des
+algorithmes prenant en entrée un entier et renvoyant un entier, et
+appelons $\varphi_e(n)$ le résultat de l'exécution du programme codé
+par l'entier $e$ sur l'entrée $n$, si cette exécution termine (et
+$\varphi_e(n)$ non défini si cette exécution ne termine pas).
+Considérons la fonction $b\colon \mathbb{N} \to \mathbb{N}$ suivante :
+\[
+b(n) = \max\{\varphi_e(n) : 0\leq e\leq n
+\text{~et~}\varphi_e(n)\text{~défini}\}
+\]
+(Autrement dit, $b(n)$ est la plus grande des valeurs $\varphi_e(n)$
+qui sont définies lorsque $e$ parcourt les entiers de $0$ à $n$.)
+
+\textbf{(2)} On veut montrer que pour toute fonction calculable
+$f\colon \mathbb{N} \to \mathbb{N}$, il existe un $n_0$ tel que pour
+tout $n\geq n_0$ on ait $b(n) > f(n)$.  Supposons donc $f\colon
+\mathbb{N} \to \mathbb{N}$ calculable.\quad\textbf{(a)} Expliquer
+pourquoi il existe $p$ tel que $\varphi_p = f+1$ (c'est-à-dire
+$\varphi_p(n) = f(n)+1$ pour tout $n$).\quad\textbf{(b)} En déduire
+que $b(n) > f(n)$ lorsque $n\geq p$, et conclure.
+
+\begin{corrige}
+\textbf{(a)} La fonction $n \mapsto f(n)+1$ est calculable puisque $f$
+l'est et que l'addition l'est.  Il existe donc un algorithme qui la
+calcule, c'est-à-dire un $p$ tel que $\varphi_p = f+1$.
+
+\textbf{(b)} Sachant que $\varphi_p = f+1$, si $n \geq p$, la valeur
+$b(n)$ est le maximum des valeurs $\varphi_e(n)$ qui sont définies
+lorsque $e$ et $n$ parcourent les entiers de $0$ à $n$.  En
+particulier, puisque $0\leq p\leq n$, parmi ces entiers se trouve la
+valeur $\varphi_p(n) = f(n)+1$ (qui est bien définie car $f$ est une
+fonction totale ici).  On a donc $b(n) \geq \varphi_p(n) = f(n)+1 >
+f(n)$.  On a bien montré que si $n \geq p$ alors $b(n) > f(n)$, ce qui
+était voulu (pour $n_0 = p$).
+\end{corrige}
+
+\textbf{(3)} Montrer que (pour les fonctions $h$ et $b$ introduites
+ci-dessus) :
+\[
+\lim_{m\to+\infty} \frac{b(n)}{h(n)} = +\infty
+\]
+
+\begin{corrige}
+On souhaite montrer que pour tout $C>0$ il existe $n_0$ tel que si
+$n\geq n_0$ alors $\frac{b(n)}{h(n)} > C$.  Pour cela, soit $C$ un
+réel $>0$, et, quitte à l'augmenter encore un peu, on peut supposer
+$C$ entier.  La fonction $C\cdot h$ (c'est-à-dire $n \mapsto C\cdot
+h(n)$) est calculable car $h$ l'est (question (1)) et que la
+multiplication l'est.  D'après la question (2), il existe $n_0$ tel
+que pour tout $n\geq n_0$ on ait $b(n) > C\cdot h(n)$ : c'est ce qu'on
+voulait montrer.
+\end{corrige}
+
+\textbf{(4)} On se propose ici de redémontrer l'indécidabilité du
+problème de l'arrêt de manière légèrement différente de ce qui a été
+vu en cours.  Supposons donc par l'absurde que le problème de l'arrêt
+$H = \{(e,n) : \varphi_e(n)\text{~défini}\}$ soit
+décidable.\quad\textbf{(a)} Montrer soigneusement, sous cette
+hypothèse, que $b$ est calculable.\quad\textbf{(b)} Conclure.
+
+\begin{corrige}
+\textbf{(a)} Supposons par l'absurde qu'il existe un algorithme $T$
+qui décide le problème de l'arrêt : autrement dit, donnés $e$ et $n$,
+cet algorithme est censé terminer en temps fini et répondre « oui » si
+le programme codé par $e$ termine sur l'entrée $n$, « non » sinon.  On
+peut alors calculer $b(n)$ de la manière suivante : on démarre avec
+$m=0$ et on effectue une boucle pour $e$ allant de $0$ à $n$, et pour
+chacune des valeurs en question, on utilise $T$ pour savoir si
+$\varphi_e(n)$ est défini, puis, \emph{si} c'est le cas, on caclcule
+cette valeur $\varphi_e(n)$ au moyen de la machine universelle (ce
+calcul termine en temps fini justement puisque $\varphi_e(n)$ est
+défini), et on remplace la variable $m$ par $\max(m, \varphi_e(n))$.
+À la fin de la boucle, on a bien calculé le max de toutes les valeurs
+$\varphi_e(n)$ qui sont définies, c'est-à-dire $b(m)$.  La fonction
+$b$ est donc calculable (de nouveau, sous l'hypothèse que le problème
+de l'arrêt l'est).
+
+\textbf{(b)} On a vu en (2) que pour toute fonction calculable $f$ il
+existe un $n_0$ tel que pour tout $n\geq n_0$ on ait $b(n) > f(n)$.
+Comme on vient de voir que (sous l'hypothèse que le problème de
+l'arrêt est calculable) la fonction $b$ est calculable, en appliquant
+ce résultat à $f = b$, il doit exister un $n_0$ tel que tout $n\geq
+n_0$ on ait $b(n) > b(n)$, ce qui est absurde.  C'est donc que
+l'hypothèse était absurde : le problème de l'arrêt n'est pas
+décidable.
+\end{corrige}
+
 
 %
 %