Some comments and final thoughts.

1 files changed, 109 insertions, 11 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index bba20d9..82f2f47 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -259,6 +259,45 @@ Pour toutes ces raisons, le sujet mérite d'être étudié !
 \end{frame}
 %
 \begin{frame}
+\frametitle{Trois grandes approches}
+
+On va décrire trois approches des (mêmes !) fonctions calculables au
+sens de Church-Turing, et esquisser leur équivalence :
+
+\medskip
+
+\itempoint Les \textbf{fonctions générales récursives} sont
+mathématiq\textsuperscript{t} plus commodes :
+\begin{itemize}
+\item « tout est un entier » (fonctions $\mathbb{N}^k \dasharrow
+  \mathbb{N}$),
+\item définition inductive, numérotation associé.
+\end{itemize}
+
+\medskip
+
+\itempoint Les \textbf{machines de Turing} représentent des
+ordinateurs très simple :
+\begin{itemize}
+\item travaillent sur une « bande » illimitée a priori (mémoire),
+\item aspect algorithmique évident, plus proche d'un « vrai » ordinateur,
+\item approche la plus commode pour la complexité (pas considérée ici).
+\end{itemize}
+
+\medskip
+
+\itempoint Le \textbf{$\lambda$-calcul} pur non typé est un système
+symbolique :
+\begin{itemize}
+\item proche des langages de program\textsuperscript{on} fonctionnels
+  (p.ex., Lisp, Haskell, OCaml),
+\item plus facile à « programmer » réellement, mais nombreuses
+  subtilités.
+\end{itemize}
+
+\end{frame}
+%
+\begin{frame}
 \frametitle{Données finies}
 
 Un algorithme travaille sur des \textbf{données finies}.
@@ -2573,15 +2612,15 @@ De Bruijn est identique.
 \begin{frame}
 \frametitle{Le $\lambda$-calcul : $\beta$-réduction}
 
-{\footnotesize On travaille sur des termes à $\alpha$-équivalence
-  près.\par}
+{\footnotesize On travaille désormais sur des termes à
+  $\alpha$-équivalence près.\par}
 
 \bigskip
 
 \itempoint Un \textbf{redex} (« reducible expression ») est un terme
 de la forme $(\lambda v. E)T$.
 
-Son \textbf{reduct} est le terme $E[v\backslash T]$ obtenu par
+Son \textbf{réduit} est le terme $E[v\backslash T]$ obtenu par
 remplacement de $T$ pour $v$ dans $E$, en évitant tout conflit de
 variables.
 
@@ -2591,7 +2630,7 @@ Exemples :
 \begin{itemize}
 \item $(\lambda x.xx)y \rightarrow yy$
 \item $(\lambda x.xx)(\lambda x.xx) \rightarrow (\lambda x.xx)(\lambda
-  x.xx)$ (est son propre reduct)
+  x.xx)$ (est son propre réduit)
 \item $(\lambda xy.x)z \rightarrow \lambda y.z$ (car $\lambda xy.x$
   abrège $\lambda x.\lambda y.x$)
 \item $(\lambda xy.x)y \rightarrow \lambda y_1.y$ (attention au
@@ -2611,7 +2650,7 @@ xyz.((xz)(yz))$.
 
 \itempoint On appelle \textbf{$\beta$-réduction} le remplacement en
 sous-expression d'une \textcolor{purple}{redex} par son
-\textcolor{olive}{reduct}.\quad Ex. : $\lambda
+\textcolor{olive}{réduit}.\quad Ex. : $\lambda
 x. \textcolor{purple}{(\lambda y. y (\lambda z. z)) (\lambda z. x z)}
 \rightarrow \lambda x. \textcolor{olive}{(\lambda z. x z)(\lambda
   z. z)}$.
@@ -2683,7 +2722,7 @@ réductions.
 
 \bigskip
 
-On peut montrer :
+On peut montrer (mais on évitera d'utiliser) :
 
 \itempoint\textbf{Théorème} (Curry \&al) : si $T \twoheadrightarrow
 T'$ avec $T'$ en forme normale, alors $T
@@ -2766,8 +2805,8 @@ nombre d'étapes d'exécution) \alert{si la réduction extérieure gauche
 
 \textcolor{blue}{\textbf{Moralité :}} les fonctions récursives peuvent
 simuler la réduction extérieure gauche du $\lambda$-calcul
-{\footnotesize (ou n'importe quelle autre réduction, mais on a choisi
-  celle-ci)}.
+{\footnotesize (ou n'importe quelle autre réduction, mais on se
+  concentre sur celle-ci)}.
 
 \end{frame}
 %
@@ -3048,7 +3087,7 @@ T
 z
 (h (A z) x_1\cdots x_k)
 )\\
-\rightarrow & \mathsf{Y}
+\rightarrow\strut & \mathsf{Y}
 (\lambda h z x_1\cdots x_k.
 (v z x_1\cdots x_k)
 (\lambda y.h (A z) x_1\cdots x_k)
@@ -3096,6 +3135,7 @@ existe des fonctions p.r. :
 
 \end{frame}
 %
+\section{Conclusion}
 \begin{frame}
 \frametitle{Récapitulation}
 
@@ -3128,7 +3168,65 @@ algorithmiquement :
 
 \end{frame}
 %
-% Add somewhere:
-% - "Turing tarpit"
+\begin{frame}
+\frametitle{Turing-complétude}
+
+Un langage de programmation est dit \textbf{Turing-complet} lorsque
+(convenablement idéalisé !) il permet d'implémenter précisément les
+fonctions calculables au sens de Church-Turing.
+
+\bigskip
+
+Un ordinateur réel ne peut \alert{jamais faire plus} qu'une machine de
+Turing (sauf p.-ê. : génération de hasard vrai).  La question est de
+savoir si le langage permet \alert{autant}.
+
+\bigskip
+
+Tous les langages de programmation généralistes \alert{sont
+  Turing-complets} : Python, Java, JavaScript, C, C++, OCaml, Haskell,
+Lisp, Perl, Ruby, Smalltalk, Prolog…
+
+\bigskip
+
+Certains le sont même plus ou moins « par accident » : CSS, TeX, XSLT, m4…
+(parfois sous conditions, ou sous réserve d'interprétation).
+
+\bigskip
+
+Pas toujours clair : assembleurs (pas évident d'idéaliser les entiers).
+
+\bigskip
+
+Conséquence du problème de l'arrêt : on ne peut pas algorithmiquement
+décider si un programme donné (en Python, etc.) termine ou non.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Turing tarpit}
+
+{\footnotesize « Fosse à bitume de Turing » ?\par}
+
+\bigskip
+
+\itempoint Tous les langages usuels se valent du point de vue de la
+calculabilité.  Ce n'est pas pour autant qu'ils se valent en
+pratique !  (En commodité et/ou efficacité.)
+
+\bigskip
+
+\itempoint Ça ne signifie pas qu'un langage Turing-complet peut
+forcément « tout » faire.  Par exemple, un langage qui ne permet comme
+entrée/sortie que d'afficher des entiers peut être Turing-complet et
+ne permet pas d'écrire « bonjour ».
+
+\bigskip
+
+\itempoint Si en principe on peut convertir toute fonction calculable
+dans tout langage Turing-complet, la conversion peut devenir
+extrêmement inefficace, malcommode ou illible.
+
+\end{frame}
 %
 \end{document}