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