diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 44 |
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} |