path: root/transp-inf110-01-calc.tex

%% 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{Sans préoccupation d'efficacité}

\itempoint La calculabilité \alert{ne s'intéresse pas à l'efficacité}
des algorithmes qu'elle étudie, uniquement leur \textbf{terminaison en
  temps fini}.

\medskip

P.ex. : pour savoir si $n$ est premier, on peut tester si $i\times
j=n$ pour tout $i$ et $j$ allant de $2$ à $n-1$.  (Hyper inefficace ?
On s'en fout.)

\bigskip

\itempoint La calculabilité \alert{n'a pas peur des grands entiers}.

\medskip

P.ex. : \textbf{fonction d'Ackermann} définie par :
\[
\begin{aligned}
A(m,n,0) &= m+n \\
A(m,1,k+1) &= m \\
A(m,n+1,k+1) &= A(m,\,A(m,n,k+1),\,k)
\end{aligned}
\]
définition algorithmique par récursion, donc calculable.

\smallskip

Mais $A(2,6,3) = 2^{2^{2^{2^{2^2}}}} = 2^{2^{65\,536}}$ et $A(2,4,4) =
A(2,65\,536,3)$ est inimaginablement grand (et que dire de
$A(100,100,100)$ ?).

$\Rightarrow$ Ingérable sur un vrai ordinateur.

\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}
%
\begin{frame}
\frametitle{Données finies}

Un algorithme travaille sur des \textbf{données finies}.

\medskip

Qu'est-ce qu'une « donnée finie » ?  Tout objet représentable
informatiquement : booléen, entier, chaîne de caractères, structure,
liste/tableau de ces choses, ou même plus complexe (p.ex., graphe).

\medskip

$\rightarrow$ Comment y voir plus clair ?

\bigskip

Deux approches opposées :
\begin{itemize}
\item\textbf{typage} : distinguer toutes ces données,
\item\textbf{codage de Gödel} : tout représenter comme des entiers !
\end{itemize}

\bigskip

Le typage est plus élégant, plus satisfaisant, plus proche de
l'informatique réelle.

\smallskip

Le codage de Gödel simplifie l'approche/définition de la calculabilité
(on étudie juste des fonctions $\mathbb{N} \dasharrow \mathbb{N}$).

\end{frame}
%
\begin{frame}
\frametitle{Codage de Gödel (« tout est un entier »)}

\itempoint Représenter \textbf{n'importe quelle donnée finie par un
  entier}.

\bigskip

\itempoint Codage des couples : par exemple,
\[
\langle m,n\rangle := m + \frac{1}{2}(m+n)(m+n+1)
\]
définit une bijection calculable $\mathbb{N}^2 \to \mathbb{N}$.

\bigskip

\itempoint Codage des listes finies : par exemple,
\[
\langle\!\langle a_0,\ldots,a_{k-1}\rangle\!\rangle
:= \langle a_0, \langle a_1, \langle\cdots,\langle a_{k-1},0\rangle+1\cdots\rangle+1\rangle+1
\]
définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \to \mathbb{N}$.

\bigskip

\itempoint Il sera aussi utile de représenter les programmes par des
entiers.

\bigskip

\itempoint Les détails du codage sont \textbf{sans importance}.

\bigskip

\itempoint\alert{Ne pas utiliser dans la vraie vie} (hors calculabilité) !

\end{frame}
%
\begin{frame}
\frametitle{Fonctions partielles}

\itempoint Même si on s'intéresse à des algorithmes qui
\textbf{terminent}, la définition de la calculabilité \alert{doit
  forcément} passer aussi par ceux qui ne terminent pas.

{\footnotesize (Aucun langage Turing-complet ne peut exprimer
  uniquement des algorithmes qui terminent toujours, à cause de
  l'indécidabilité du problème de l'arrêt.)\par}

\bigskip

\itempoint Lorsque l'algorithme censé calculer $f(n)$ ne termine pas,
on dira que $f$ n'est pas définie en $n$, et on notera $f(n)\uparrow$.
Au contraire, s'il termine, on note $f(n)\downarrow$.

\bigskip

\itempoint Notation : $f\colon \mathbb{N} \dasharrow \mathbb{N}$ :
une fonction $D \to \mathbb{N}$ définie sur une partie $D \subseteq
\mathbb{N}$.

\itempoint Notation : $f(n) \downarrow$ signifie « $n \in D$ », et $f(n)
\uparrow$ signifie « $n \not\in D$ ».

\itempoint Notation : $f(n) \downarrow = g(m)$ signifie
« $f(n)\downarrow$ et $g(m)\downarrow$ et $f(n) = g(m)$ ».

\itempoint Convention : $f(n) = g(m)$ signifie « $f(n)\downarrow$ ssi
$g(m)\downarrow$, et $f(n) = g(m)$ si $f(n)\downarrow$ ».  (Certains
préfèrent $f(n) \simeq g(m)$ pour ça.)

\end{frame}
%
\end{document}