diff options
| -rw-r--r-- | controle-20230615.tex | 120 |
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} + % % |