Terminological cleanup.

1 files changed, 212 insertions, 26 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 922c76a..211f842 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -175,7 +175,7 @@ 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.
+définition algorithmique (par appels récursifs), donc calculable.
 
 \smallskip
 
@@ -237,7 +237,7 @@ $\Rightarrow$ On parle de \alert{calculabilité au sens de Church-Turing}.
 
 \itempoint\textbf{Observation} : tous les langages de programmation
 informatiques généraux usuels, idéalisés, calculent aussi exactement
-ces fonctions.
+ces fonctions ($\rightarrow$ « Turing-complets »).
 
 \bigskip
 
@@ -277,7 +277,7 @@ $\rightarrow$ Comment y voir plus clair ?
 
 Deux approches opposées :
 \begin{itemize}
-\item\textbf{typage} : distinguer toutes ces données,
+\item\textbf{typage} : distinguer toutes ces sortes de données,
 \item\textbf{codage de Gödel} : tout représenter comme des entiers !
 \end{itemize}
 
@@ -305,7 +305,8 @@ Le codage de Gödel simplifie l'approche/définition de la calculabilité
 \[
 \langle m,n\rangle := m + \frac{1}{2}(m+n)(m+n+1)
 \]
-définit une bijection calculable $\mathbb{N}^2 \to \mathbb{N}$.
+définit une bijection calculable $\mathbb{N}^2 \to \mathbb{N}$
+(calculable dans les deux sens).
 
 \bigskip
 
@@ -318,12 +319,12 @@ définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \t
 
 \bigskip
 
-\itempoint Il sera aussi utile de représenter les programmes par des
+\itempoint Il sera aussi utile de représenter les \alert{programmes} par des
 entiers.
 
 \bigskip
 
-\itempoint Les détails du codage sont \textbf{sans importance}.
+\itempoint Les détails précis du codage sont \textbf{sans importance}.
 
 \bigskip
 
@@ -375,13 +376,16 @@ $h(g_1(\underline{x}),\ldots,g_k(\underline{x}))\uparrow$.
 \itempoint Terminologie : une fonction $f\colon \mathbb{N} \to
 \mathbb{N}$ est dite \textbf{totale}.
 
+{\footnotesize Une fonction totale est un \alert{cas particulier} de
+  fonction partielle !\par}
+
 \end{frame}
 %
 \begin{frame}
 \frametitle{Terminologie à venir (avant-goût)}
 
 \itempoint Une fonction partielle $f\colon \mathbb{N} \dasharrow
-\mathbb{N}$ est dite \textbf{calculable partielle} lorsqu'il existe
+\mathbb{N}$ est dite \textbf{calculable} (partielle) lorsqu'il existe
 un algorithme qui prend $n$ en entrée et :
 \begin{itemize}
 \item termine (en temps fini) et renvoie $f(n)$ lorsque $f(n)\downarrow$,
@@ -406,7 +410,7 @@ est calculable (répondre « oui » ou « non » selon que $n\in A$ ou $n\no
 \bigskip
 
 \itempoint Une partie $A \subseteq \mathbb{N}$ est dite
-\textbf{semi-décidable} lorsque sa fonction « semi-indicatrice »
+\textbf{semi-décidable} lorsque sa fonction partielle « semi-indicatrice »
 $\mathbb{N}\dasharrow\mathbb{N}$ (d'ensemble de définition $A$)
 \[
 n \mapsto \left\{
@@ -484,7 +488,7 @@ complexité).
 
 \bigskip
 
-\itempoint Mais p.ex. la fonction d'Ackermann n'est pas p.r.
+\itempoint Mais pas tous : p.ex. la fonction d'Ackermann n'est pas p.r.
 
 \end{frame}
 %
@@ -678,7 +682,54 @@ terminant clairement).
 \end{frame}
 %
 \begin{frame}
-\frametitle{Fonctions primitives récursives : numérotation}
+\frametitle{Fonctions primitives récursives : numérotation (idée)}
+
+\itempoint On veut \alert{coder} les fonctions p.r. {\footnotesize (et
+  plus tard : gén\textsuperscript{ales} récursives)} \alert{par des
+  entiers}.
+
+\bigskip
+
+\itempoint Pour (certains) entiers $e \in \mathbb{N}$, on va définir
+$\psi_e^{(k)}\colon \mathbb{N}^k \to \mathbb{N}$ primitive récursive,
+la fonction p.r. \alert{codée} par $e$ ou ayant $e$ comme
+\textbf{code} (source).
+
+\bigskip
+
+\itempoint Toute fonction p.r. $f\colon \mathbb{N}^k \to \mathbb{N}$
+sera un $\psi_e^{(k)}$ pour un certain $e$.
+
+\smallskip
+
+\itempoint Ce $e$ décrit la manière dont $f$ est construite selon la
+définition de $\mathbf{PR}$
+(cf. transp. \ref{primitive-recursive-definition}).
+
+\smallskip
+
+\itempoint Il faut l'imaginer comme le \alert{code source} de $f$ (au
+sens informatique).
+
+\smallskip
+
+\itempoint Il n'est \alert{pas du tout unique} : $f = \psi_{e_1}^{(k)}
+= \psi_{e_2}^{(k)} = \cdots$
+
+\bigskip
+
+{\footnotesize
+
+\itempoint On va ensuite se demander si $(e,\underline{x}) \mapsto
+\psi_e^{(k)}(\underline{x})$ est \alert{elle-même p.r.} (divulgâchis :
+\alert{non}).
+
+\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions primitives récursives : numérotation (définition)}
 
 On définit $\psi_e^{(k)}\colon \mathbb{N}^k \dasharrow \mathbb{N}$ par
 induction suivant la déf\textsuperscript{n} de $\mathbf{PR}$
@@ -730,6 +781,11 @@ en « langage p.r. ».
 
 \medskip
 
+\itempoint Une fonction p.r. a généralement \alert{beaucoup d'indices} :
+$\psi_{e_1}^{(k)} = \psi_{e_2}^{(k)} = \cdots$ (programmes équivalents).
+
+\medskip
+
 \centerline{*}
 
 \bigskip
@@ -769,7 +825,7 @@ gardés variables.
 
 {\footnotesize Le nom de Willard Van Orman Quine (1908–2000) a été
   associé à cette astuce par Douglas Hofstadter.  En fait, l'astuce
-  est plutôt due à Cantor, Turing ou Kleene.\par}
+  est plutôt due à Cantor, Gödel, Turing ou Kleene.\par}
 
 \smallskip
 
@@ -842,8 +898,9 @@ sont p.r.\qed
 
 \bigskip
 
-\textcolor{blue}{\textbf{Moralité :}} \alert{on peut donner aux programmes accès à leur
-  propre numéro} (= « code source »), cela ne change rien.
+\textcolor{blue}{\textbf{Moralité :}} \alert{on peut donner aux
+  programmes accès à leur propre numéro} (= « code source », ici $e$),
+cela ne change rien.
 
 \end{frame}
 %
@@ -868,10 +925,10 @@ contredit $u(e,x) = \psi^{(1)}_e(x)$.\qed
 
 \medskip
 
-\textcolor{blue}{\textbf{Moralité :}} \alert{un interpréteur du langage p.r. ne peut pas
-  être p.r.} (preuve : on peut interpréter l'interpréteur
-s'interprétant lui-même, en ajoutant un au résultat, ce qui donne un
-paradoxe ; c'est un argument diagonal de Cantor).
+\textcolor{blue}{\textbf{Moralité :}} \alert{un interpréteur du
+  langage p.r. ne peut pas être p.r.} (preuve : on peut interpréter
+l'interpréteur s'interprétant lui-même, en ajoutant $1$ au résultat
+ceci donne un paradoxe ; c'est un argument diagonal de Cantor).
 
 \bigskip
 
@@ -880,7 +937,7 @@ fonctions p.r. sont \alert{totales}.  Pour définir une théorie
 satisfaisante de la calculabilité, on va sacrifier la totalité pour
 sauver le théorème s-m-n.
 
-{\footnotesize Cette même preuve donnera alors la preuve de
+{\footnotesize Cette même preuve deviendra alors la preuve de
   l'indécidabilité du problème de l'arrêt.\par}
 
 \end{frame}
@@ -910,8 +967,8 @@ $\psi^{(2)}_{a(k)}(m,n) = A(m,n,k)$.
 
 \smallskip
 
-I.e., on peut calculer de façon p.r. en $k$ le code d'un programme
-p.r. qui calcule $(m,n) \mapsto A(m,n,k)$.
+I.e., on peut calculer de façon p.r. en $k$ le \alert{code} d'un
+programme p.r. qui calcule $(m,n) \mapsto A(m,n,k)$.
 
 \bigskip
 
@@ -941,7 +998,7 @@ couvrent pas la notion générale d'algorithme :
 lever ces limitations.  On va \alert{autoriser les boucles infinies}.
 
 $\rightarrow$ Fonctions \textbf{générales récursives} ou simplement
-\textbf{récursives}.
+« \textbf{récursives} ».
 
 Ce seront aussi nos fonctions \textbf{calculables} !
 
@@ -1025,7 +1082,59 @@ Cette fois le langage \alert{permet les boucles non bornées} !
 \end{frame}
 %
 \begin{frame}
-\frametitle{Fonctions générales récursives : numérotation}
+\frametitle{Fonctions générales récursives : numérotation (idée)}
+
+\itempoint On veut \alert{coder} les fonctions générales récursives
+\alert{par des entiers}.
+
+\smallskip
+
+{\footnotesize Exactement comme on l'a fait pour les fonctions p.r.,
+  on change juste la notation de $\psi$ en $\varphi$.\par}
+
+\bigskip
+
+\itempoint Pour (certains) entiers $e \in \mathbb{N}$, on va définir
+$\varphi_e^{(k)}\colon \mathbb{N}^k \dasharrow \mathbb{N}$ générale
+récursive, la fonction récursive \alert{codée} par $e$ ou ayant $e$
+comme \textbf{code} (source).
+
+\bigskip
+
+\itempoint Toute fonction récursive (partielle !) $f\colon
+\mathbb{N}^k \dasharrow \mathbb{N}$ sera un $\varphi_e^{(k)}$ pour un
+certain $e$.
+
+\smallskip
+
+\itempoint Ce $e$ décrit la manière dont $f$ est construite selon la
+définition de $\mathbf{R}$
+(cf. transp. \ref{general-recursive-definition}).
+
+\smallskip
+
+\itempoint Il faut l'imaginer comme le \alert{code source} de $f$ (au
+sens informatique).
+
+\smallskip
+
+\itempoint Il n'est \alert{pas du tout unique} : $f = \varphi_{e_1}^{(k)}
+= \varphi_{e_2}^{(k)} = \cdots$
+
+\bigskip
+
+{\footnotesize
+
+\itempoint On va ensuite se demander si $(e,\underline{x}) \mapsto
+\varphi_e^{(k)}(\underline{x})$ est \alert{elle-même récursive}
+(divulgâchis : \alert{oui}, contrairement au cas p.r.).
+
+\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions générales récursives : numérotation (définition)}
 
 On définit $\varphi_e^{(k)}\colon \mathbb{N}^k \dasharrow \mathbb{N}$ par
 induction suivant la déf\textsuperscript{n} de $\mathbf{R}$
@@ -1207,7 +1316,7 @@ Les points-clés :
 D'où l'algorithme « universel » pour calculer
 $\varphi_e^{(k)}(\underline{x})$ en fonction de $e,\underline{x}$ :
 \begin{itemize}
-\item parcourir $n=0,1,2,3,4,\ldots$,
+\item parcourir $n=0,1,2,3,4,\ldots$ (boucle non bornée),
 \item pour chacun, tester s'il code un arbre de calcul valable de
   $\varphi_e^{(k)}(\underline{x})$,
 \item si oui, terminer et renvoyer le $y$ contenu.
@@ -1433,9 +1542,9 @@ soit la fonction d'Ackermann.
 \medskip
 
 \itempoint\textbf{Problème :} donné un programme $e$ (mettons d'arité
-$k=1$) et une entrée $x$ à ce programme, comment savoir si $e$ termine
-(c'est-à-dire $\varphi^{(1)}_e(x)\downarrow$) ou non
-($\varphi^{(1)}_e(x)\uparrow$) ?
+$k=1$) et une entrée $x$ à ce programme, comment savoir si
+l'algorithme $e$ termine (c'est-à-dire $\varphi^{(1)}_e(x)\downarrow$)
+ou non ($\varphi^{(1)}_e(x)\uparrow$) sur cette entrée ?
 
 \medskip
 
@@ -1887,6 +1996,83 @@ jour ».
 
 \end{frame}
 %
+\section{Décidabilité et semi-décidabilité}
+\begin{frame}
+\frametitle{Terminologie calculable/décidable}
+
+\itempoint Une fonction partielle $f\colon \mathbb{N}^k \dasharrow
+\mathbb{N}$ est dite \textbf{calculable} (partielle) lorsqu'elle est
+(c'est équivalent) :
+\begin{itemize}
+\item générale récursive,
+\item calculable par machine de Turing,
+\item \textcolor{brown}{à voir $\rightarrow$} exprimable dans le $\lambda$-calcul.
+\end{itemize}
+
+\bigskip
+
+\itempoint Une partie $A \subseteq \mathbb{N}^k$ est dite
+\textbf{décidable} lorsque sa fonction indicatrice
+$\mathbb{N}^k\to\mathbb{N}$
+\[
+\mathbf{1}_A\colon n \mapsto \left\{
+\begin{array}{ll}
+1&\text{~si~}n\in A\\
+0&\text{~si~}n\not\in A\\
+\end{array}
+\right.
+\]
+est calculable (répondre « oui » ou « non » selon que $n\in A$ ou $n\not\in A$).
+
+\bigskip
+
+\itempoint Une partie $A \subseteq \mathbb{N}^k$ est dite
+\textbf{semi-décidable} lorsque sa fonction partielle « semi-indicatrice »
+$\mathbb{N}\dasharrow\mathbb{N}$ (d'ensemble de définition $A$)
+\[
+n \mapsto \left\{
+\begin{array}{ll}
+1&\text{~si~}n\in A\\
+\uparrow&\text{~si~}n\not\in A\\
+\end{array}
+\right.
+\]
+est calculable (répondre « oui » ou « ... » selon que $n\in A$ ou $n\not\in A$).
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fluctuations terminologiques}
+
+\itempoint Synonymes de \textbf{calculable} pour une fonction
+partielle $\mathbb{N}^k \dasharrow \mathbb{N}$ :
+\begin{itemize}
+\item « semi-calculable » (réservant « calculable » pour les fonctions \emph{totales}),
+\item « (générale) récursive ».
+\end{itemize}
+
+\bigskip
+
+\itempoint Synonymes de \textbf{décidable} pour une partie $\subseteq
+\mathbb{N}^k$ :
+\begin{itemize}
+\item « calculable »,
+\item « récursive ».
+\end{itemize}
+
+\bigskip
+
+\itempoint Synonymes de \textbf{semi-décidable} pour une partie $\subseteq
+\mathbb{N}^k$ :
+\begin{itemize}
+\item « semi-calculable »,
+\item « calculablement énumérable »,
+\item « récursivement énumérable ».
+\end{itemize}
+{\footnotesize (La raison du « énumérable » sera expliquée après.)\par}
+
+\end{frame}
+%
 % Add somewhere:
 % - busy beaver
 % - "Turing tarpit"