Initial commit with a basic set of slides.

1 files changed, 220 insertions, 0 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
new file mode 100644
index 0000000..1ed0662
--- /dev/null
+++ b/transp-inf110-01-calc.tex
@@ -0,0 +1,220 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[mathserif,a4paper,aspectratio=169]{beamer}
+%\documentclass[a4paper]{article}
+%\usepackage[envcountsect,noxcolor]{beamerarticle}
+\usepackage[shorthands=off,francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{2026}{...}
+\DeclareUnicodeCharacter{1E25}{\d{h}}
+% Beamer theme:
+\usetheme{Goettingen}
+%\usecolortheme{albatross}
+%\usecolortheme{lily}
+%\setbeamercovered{transparent}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+%
+\usepackage{graphicx}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,calc}
+%
+\newcommand{\itempoint}{\strut\hbox{\color{beamerstructure}\donotcoloroutermaths$\blacktriangleright$}\nobreak\hskip.5em plus.5em\relax}
+\renewcommand{\thefootnote}{\textdagger}
+%
+%
+%
+\title{Calculabilité}
+\subtitle{INF110 (Logique et Fondements de l'Informatique)}
+\author[David Madore]{David A. Madore\\
+{\footnotesize Télécom Paris}\\
+\texttt{david.madore@enst.fr}}
+\date{2023–2024}
+\mode<presentation>{%
+\beamertemplatenavigationsymbolsempty
+\usenavigationsymbolstemplate{\vbox{\hbox{\footnotesize\hyperlinkslideprev{$\leftarrow$}\insertframenumber/\inserttotalframenumber\hyperlinkslidenext{$\rightarrow$}}}}
+}
+\setbeamercolor{myhighlight}{fg=black,bg=white!90!green}
+\begin{document}
+\mode<article>{\maketitle}
+%
+\setlength\abovedisplayskip{2pt plus 2pt minus 2pt}
+\setlength\belowdisplayskip{2pt plus 2pt minus 2pt}
+%
+\begin{frame}
+\titlepage
+{\footnotesize\center{\url{http://perso.enst.fr/madore/inf110/transp-inf110.pdf}}\par}
+{\tiny
+\immediate\write18{sh ./vc > vcline.tex}
+\begin{center}
+Git: \input{vcline.tex}
+\end{center}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+\end{frame}
+%
+\section*{Plan}
+\begin{frame}
+\frametitle{Plan}
+\tableofcontents
+\end{frame}
+%
+\section{Introduction}
+\begin{frame}
+\frametitle{Qu'est-ce que la calculabilité ?}
+
+\itempoint À l'interface entre \textbf{logique mathématique} et
+\textbf{informatique théorique}
+\begin{itemize}
+\item née de préoccupations venues de la logique (Hilbert, Gödel),
+\item à l'origine des 1\textsuperscript{ers} concepts informatiques
+  ($\lambda$-calcul, machine de Turing).
+\end{itemize}
+
+\bigskip
+
+\itempoint But : étudier les limites de ce que \textbf{peut ou ne peut
+  pas faire un algorithme}
+\begin{itemize}
+\item sans limite de ressources (temps, mémoire juste « finis »),
+\item sans préoccupation d'efficacité ($\neq$ complexité, algorithmique),
+\item y compris résultats négatifs (« \emph{aucun} algorithme ne peut… »),
+\item voire relatifs (calculabilité relative),
+\item admettant diverses généralisations (calculabilité supérieure).
+\end{itemize}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Quelques noms}
+
+\itempoint Muḥammad ibn Mūsá al-\b{H}wārizmī (v.780–v.850) :
+$\rightsquigarrow$« algorithme »
+
+\itempoint Blaise Pascal (1623–1662) : machine à calculer
+$\rightsquigarrow$automates
+
+\itempoint Charles Babbage (1791–1871) : \textit{Analytical Engine} (Turing-complète !)
+
+\itempoint Ada (née Byron) Countess of Lovelace (1815–1852) : programmation
+
+\itempoint Richard Dedekind (1831–1916) : définitions primitives récursives
+
+\itempoint David Hilbert (1862–1943) : \textit{Entscheidungsproblem}
+(décider la vérité)
+
+\itempoint Jacques Herbrand (1908–1931) : fonctions générales récursives
+
+\itempoint Kurt Gödel (1906–1978) : incomplétude en logique
+
+\itempoint Alonzo Church (1903–1995) : $\lambda$-calcul
+
+\itempoint Alan M. Turing (1912–1954) : machine de Turing, problème de l'arrêt
+
+\itempoint Emil Post (1897–1954) : ensembles calculablement énumérables
+
+\itempoint Stephen C. Kleene (1909–1994) : $\mu$-récursion, th. de récursion, forme normale
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonction calculable}
+
+« Définition » : une fonction $f$ est \textbf{calculable}
+quand il existe un algorithme qui
+\begin{itemize}
+\item prenant en entrée un $x$ du domaine de définition de $f$,
+\item \textbf{termine en temps fini},
+\item et renvoie la valeur $f(x)$.
+\end{itemize}
+
+\bigskip
+
+Difficultés :
+\begin{itemize}
+\item Comment définir ce qu'est un algorithme ?
+\item Quel type de valeurs ?
+\item Et si l'algorithme ne termine pas ?
+\item Distinction entre intention (l'algorithme) et extension (la fonction).
+\end{itemize}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Approches de la calculabilité}
+
+\itempoint Approche informelle : \textbf{algorithme = calcul
+  finitiste} mené par un humain ou une machine, selon des instructions
+précises, en temps fini, sur des données finies
+
+\medskip
+
+\itempoint Approche pragmatique : tout ce qui peut être fait sur un
+langage de programmation « Turing-complet » (Python, Java, C, Caml…)
+idéalisé
+\begin{itemize}
+\item sans limites d'implémentation (p.ex., entiers arbitraires !),
+\item sans source de hasard ou de non-déterminisme.
+\end{itemize}
+
+\medskip
+
+\itempoint Approches formelles, p.ex. :
+\begin{itemize}
+\item fonctions générales récursives (Herbrand-Gödel-Kleene),
+\item $\lambda$-calcul (Church) ($\leftrightarrow$ langages fonctionnels),
+\item machine de Turing (Turing),
+\item machines à registres (Post…).
+\end{itemize}
+
+\bigskip
+
+\itempoint\textbf{« Thèse » de Church-Turing} : \alert{tout ceci
+  donne la même chose}.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Thèse de Church-Turing}
+
+\itempoint\textbf{Théorème} (Post, Turing) : les fonctions (disons
+$\mathbb{N} \dasharrow \mathbb{N}$) \textbf{(1)} générales récursives,
+\textbf{(2)} exprimables en $\lambda$-calcul, et
+\textbf{(3)} calculables par machine de Turing, coïncident toutes.
+
+\smallskip
+
+$\Rightarrow$ On parle de \alert{calculabilité au sens de Church-Turing}.
+
+\bigskip
+
+\itempoint\textbf{Observation} : tous les langages de programmation
+informatiques généraux usuels, idéalisés, calculent aussi exactement
+ces fonctions.
+
+\bigskip
+
+\itempoint\textbf{Thèse philosophique} : la calculabilité de C-T
+définit précisément la notion d'algorithme finitiste.
+
+\bigskip
+
+\itempoint\textbf{Conjecture physique} : la calculabilité de C-T
+correspond aux calculs réalisables mécaniquement dans l'Univers (en
+temps/énergie finis mais illimités).
+
+{\footnotesize $\uparrow$ (même avec un ordinateur quantique)}
+
+\bigskip
+
+Pour toutes ces raisons, le sujet mérite d'être étudié !
+
+\end{frame}
+%
+\end{document}