From c38ccfe9ccabe640c88289006de3d5e8e467bf75 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 12 Oct 2023 16:34:28 +0200 Subject: Initial commit with a basic set of slides. --- transp-inf110-01-calc.tex | 220 ++++++++++++++++++++++++++++++++++++++++++++++ vc | 2 + 2 files changed, 222 insertions(+) create mode 100644 transp-inf110-01-calc.tex create mode 100755 vc 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{% +\beamertemplatenavigationsymbolsempty +\usenavigationsymbolstemplate{\vbox{\hbox{\footnotesize\hyperlinkslideprev{$\leftarrow$}\insertframenumber/\inserttotalframenumber\hyperlinkslidenext{$\rightarrow$}}}} +} +\setbeamercolor{myhighlight}{fg=black,bg=white!90!green} +\begin{document} +\mode
{\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} diff --git a/vc b/vc new file mode 100755 index 0000000..2ab3e90 --- /dev/null +++ b/vc @@ -0,0 +1,2 @@ +#! /bin/sh +git log --pretty=format:'\verb=%h %ad=' -1 -- cgit v1.2.3