Googological meditation.

1 files changed, 39 insertions, 5 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 811e6d9..a678a59 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -2818,7 +2818,7 @@ simuler la réduction extérieure gauche du $\lambda$-calcul
 \frametitle{Entiers de Church}
 
 On définit les termes en forme normale $\overline{n} := \lambda
-fx.f^{(n)}(x)$ pour $n\in\mathbb{N}$, c-à-d :
+fx.f^{\circ n}(x)$ pour $n\in\mathbb{N}$, c-à-d :
 \begin{itemize}
 \item $\overline{0} := \lambda fx.x$
 \item $\overline{1} := \lambda fx.fx$
@@ -2838,11 +2838,11 @@ Alors
 \[
 \begin{aligned}
 A\overline{n} &= (\lambda m.\lambda f.\lambda x.f(mfx))(\lambda
-g.\lambda y.g^{(n)}(y))\\
+g.\lambda y.g^{\circ n}(y))\\
 & \rightarrow_{\mathsf{lft}} \lambda f.\lambda
-x.f(((\lambda g.\lambda y.g^{(n)}(y)))fx)\\
+x.f(((\lambda g.\lambda y.g^{\circ n}(y)))fx)\\
 &\rightarrow_{\mathsf{lft}}\rightarrow_{\mathsf{lft}} \lambda f.\lambda
-x.f(f^{(n)}(x)) = \lambda f.\lambda x.f^{(n+1)}(x) = \overline{n+1}
+x.f(f^{\circ n}(x)) = \lambda f.\lambda x.f^{\circ(n+1)}(x) = \overline{n+1}
 \end{aligned}
 \]
 
@@ -2958,7 +2958,7 @@ On voudrait définir
 On va définir (temporairement ?)
 \[
 \begin{aligned}
-\overline{m,n} &:= \lambda fgx.f^{(m)}(g^{(n)}(x))
+\overline{m,n} &:= \lambda fgx.f^{\circ m}(g^{\circ n}(x))
 \quad\text{~si~}m,n\in\mathbb{N}\\
 \Pi &:= \lambda mnfgx.(mf)(ngx)
 \quad\text{~donc~}\Pi\overline{m}\,\overline{n} \twoheadrightarrow_{\mathsf{lft}} \overline{m,n}\\
@@ -3269,4 +3269,38 @@ Remarquer qu'ici on arrive à provoquer une boucle infinie sans aucun
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Une méditation googologique}
+
+{\footnotesize\textcolor{gray}{Ceci est une sorte de digression, pour
+    inviter à la réflexion.}\par}
+
+\medskip
+
+{\footnotesize « googologie » = étude des grands nombres ; de
+  « googol », nom fantaisiste de $10^{100}$\par}
+
+\bigskip
+
+On cherche à minorer calculabl\textsuperscript{t} la fonction « castor
+affairé », c-à-d :
+\begin{itemize}
+\item concevoir un programme dans un langage de programmation idéalisé
+  (machine de Turing, $\lambda$-calcul, Python, OCaml…),
+\item de taille « humainement raisonnable » (peu importent les détails),
+\item qui \alert{termine en temps fini} (théoriquement !),
+\item mais calcule un nombre aussi grand que possible (variante :
+  attend un temps aussi long que possible).
+\end{itemize}
+
+\bigskip
+
+Exemple : implémenter $A_\Delta\colon n \mapsto A(n,n,n)$ (fonction
+d'Ackermann diagonale) et calculer $A_\Delta(A_\Delta(\cdots(100))) =
+A_\Delta^{\circ 100}(100)$ ou qqch du genre.
+
+…On peut faire \textcolor{orange}{beaucoup} plus grand !
+
+\end{frame}
+%
 \end{document}