An exercise on computing a large number.

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}
+
 
 %
 %