%% 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}