diff options
| -rw-r--r-- | exercices-inf110.tex | 130 |
1 files changed, 130 insertions, 0 deletions
diff --git a/exercices-inf110.tex b/exercices-inf110.tex index 538149b..d7e258e 100644 --- a/exercices-inf110.tex +++ b/exercices-inf110.tex @@ -3460,6 +3460,136 @@ par la question (1), $h$ termine effectivement. disant que « ceci est un théorème » est un théorème (mais la preuve, comme on vient de le voir, n'est pas vraiment évidente). +% + +\exercice\ (${\star}{\star}{\star}{\star}$)\par\nobreak + +Dans cet exercice, on s'intéresse au programme $p$ suivant\footnote{On +pourra supposer ici les programmes écrits dans un langage de +raisonnablement haut niveau.} : il prend en entrée un entier qu'il +ignore ; il part de $N=42$, puis il énumère toutes les démonstrations +dans l'arithmétique de Peano dont la longueur (en nombre de symboles +sur un alphabet fini fixé) vaut au plus $10^{10^{100}}$, et, pour +chacune, si la \emph{conclusion} de la démonstration est une +affirmation du type « le $e$-ième programme termine sur l'entrée $i$ » +(i.e., $\varphi_e(i){\downarrow}$) avec $e$ et $i$ des entiers +naturels explicites, alors il exécute $\varphi_e(i)$ et si ce +programme termine, il ajoute le résultat (considéré comme un entier +naturel) à $N$. Une fois que tout ceci est fait, il renvoie $N$. + +\textbf{(1)} Commenter brièvement les aspects suivants du +programme $p$ : est-il très long à écrire ? est-il plus ou moins +évident qu'il termine ? + +On désigne par « $\Sigma_1\mathsf{Sound}(\mathsf{PA})$ » (peu importe +ce que signifie « $\Sigma_1\mathsf{Sound}$ » ici) l'affirmation +suivante : « si l'arithmétique de Peano prouve +$\varphi_e(i){\downarrow}$, alors effectivement +$\varphi_e(i){\downarrow}$ ». On ne cherchera pas (pour l'instant) à +se demander si $\Sigma_1\mathsf{Sound}(\mathsf{PA})$ est vrai, ou bien +démontrable. + +\textbf{(2)} En \emph{admettant} l'affirmation +$\Sigma_1\mathsf{Sound}(\mathsf{PA})$ qu'on vient de définir, montrer +que le programme $p$ termine en temps fini. Expliquer, de plus, +pourquoi l'arithmétique de Peano $\mathsf{PA}$ prouve ce fait. + +\textbf{(3)} Sans entrer dans les détails, et toujours en admettant +$\Sigma_1\mathsf{Sound}(\mathsf{PA})$, expliquer pourquoi la valeur +renvoyée par $p$ (i.e., $\varphi_p(0)$) est gigantesque, par exemple +beaucoup \emph{beaucoup} plus grande que $10^{10^{1000}}$ itérations +de la fonction $n \mapsto A(n,n,n)$, où $A$ est la fonction +d'Ackermann, en partant de $10^{10^{1000}}$ (\emph{indication :} +esquisser comment on pourrait écrire un programme $q$ qui calcule +cette dernière valeur, et comment on prouverait que ce programme $q$ +termine). Quelle est la partie la plus longue dans l'exécution de +$p$ : l'énumération des démonstrations ou l'exécution des programmes +dont on a prouvé l'arrêt ? + +\textbf{(4)} Toujours en admettant +$\Sigma_1\mathsf{Sound}(\mathsf{PA})$, montrer que la démonstration la +plus courte de l'arrêt de $p$ dans l'arithmétique de Peano est de +longueur supérieure à $10^{10^{100}}$. + +En fait, $\mathsf{ZFC}$ prouve l'affirmation +$\Sigma_1\mathsf{Sound}(\mathsf{PA})$ énoncée plus haut, et la +démonstration n'est pas terriblement longue (on ne rentre pas dans les +détails ici). + +\textbf{(5)} Conclure que la démonstration du fait que $p$ termine, +bien que démontrable dans l'arithmétique de Peano, est beaucoup plus +long à démontrer que dans $\mathsf{ZFC}$. + +\begin{corrige} +\textbf{(1)} Le programme $p$ n'est pas très long à écrire : il s'agit +de calculer $10^{10^{100}}$, ce qui n'est pas difficile, puis +d'effectuer une boucle finie sur tous les entiers pouvant coder une +chaîne de longueur au plus $10^{10^{100}}$, de tester si chacun est +une démonstration valable dans $\mathsf{PA}$ (ce qui est algorithmique +et pas terriblement difficile) avec pour conclusion +$\varphi_e(i){\downarrow}$ et, le cas échéant, d'utiliser +l'interpréteur universel pour simuler l'exécution de $\varphi_e(i)$ et +l'ajouter à $N$, puis finalement renvoyer $N$. Aucune de ces +étapes n'est très difficile, et on peut certainement dire que le +programme est de longueur bien inférieure à $10^{100}$, par exemple. + +Quant à sa terminaison, la seule partie qui n'est pas évidente est le +fait que $\varphi_e(i){\downarrow}$. On en a une preuve dans +$\mathsf{PA}$ (par construction du programme !), mais encore faut-il +que $\mathsf{PA}$ dise la vérité, ce qui constitue précisément +l'hypothèse $\Sigma_1\mathsf{Sound}(\mathsf{PA})$ introduite par +l'énoncé. + +\textbf{(2)} Une fois admise l'hypothèes +$\Sigma_1\mathsf{Sound}(\mathsf{PA})$, il est évident que $p$ termine, +puisqu'il exécute $\varphi_e(i)$ une fois qu'il a une preuve dans +$\mathsf{PA}$ que $\varphi_e(i){\downarrow}$, donc toutes ces +exécutions terminent bien par $\Sigma_1\mathsf{Sound}(\mathsf{PA})$. +Tout le reste est une boucle finie, donc termine certainement. + +Comme on a vu en cours que si un programme s'arrête, ce fait est +prouvable dans $\mathsf{PA}$ (en transformant une trace d'exécution +complète en démonstration), c'est le cas pour notre programme $p$. + +\textbf{(3)} Soit $q$ le programme qui implémente la fonction +d'Ackermann et s'en sert pour calculer $10^{10^{1000}}$ itérations de +la fonction $n \mapsto A(n,n,n)$ en partant de $10^{10^{1000}}$ : ce +programme termine car la fonction d'Ackermann est bien définie. Le +\emph{fait} que ce programme termine est facile à prouver, et cette +preuve, qui repose sur des considérations arithmétiques (des +récurrences imbriquées) est menable dans $\mathsf{PA}$ ; de plus, elle +n'est pas terriblement longue, certainement bien plus courte que +$10^{100}$. Par conséquent, $p$ va, entre autres, tomber sur cette +preuve au cours de son énumération, donc il va exécuter $p$, donc +ajouter son résultat à $N$. Donc la valeur de retour de $p$ est +supérieure à celle de $q$, et même considérablement plus grand puisque +$q$ va ajouter le résultat de tous les calculs de ce genre dont on +peut prouver la terminaison en moins de $10^{10^{100}}$ symboles. + +Au cours de l'exécution de $p$, on doit parcourir toutes les +démonstrations de longueur au plus $10^{10^{100}}$ : cette énumération +est certes très longue (en gros une exponentielle de plus), mais +complètement minuscule par rapport au temps d'exécution des programmes +car on vient de voir qu'il y en a qui calculent des nombres +considérablement plus gigantesques (et parmi les programmes il y en a +qui calculent ce nombre puis attendent ce nombre d'étapes). + +\textbf{(4)} On a vu en (2) que $\mathsf{PA}$ prouve que $p$ termine, +mais il n'est pas possible qu'il le prouve en moins de $10^{10^{100}}$ +symboles, car si tel était le cas, $p$ ferait partie des programmes +exécutés lors de la boucle de $p$, donc le résultat ferait partie de +ceux ajoutés à $N$, donc on aurait $N>N$. + +\textbf{(5)} Le fait que $p$ termine est prouvable dans $\mathsf{ZFC}$ +grâce au raisonnement expliqué en (2), et la preuve n'est pas très +longue, certainement bien plus courte que $10^{100}$ symboles, même +quand on ajoute la preuve de $\Sigma_1\mathsf{Sound}(\mathsf{PA})$ qui +n'est elle-même pas bien longue d'après l'énoncé. Comme on vient de +voir que la plus courte preuve de la terminaison de $p$ dans +$\mathsf{PA}$ est, pour sa part, plus longue que $10^{10^{100}}$ +symboles, la preuve dans $\mathsf{ZFC}$ est beaucoup plus courte. +\end{corrige} + % % |