Reread up to Rice's theorem.

1 files changed, 166 insertions, 97 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 66a9d84..ce1033f 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -116,6 +116,8 @@ $\rightsquigarrow$automates
 
 \itempoint Kurt Gödel (1906–1978) : incomplétude en logique
 
+\itempoint Haskell Curry (1900–1982) : logique combinatoire, lien preuves-typage
+
 \itempoint Alonzo Church (1903–1995) : $\lambda$-calcul
 
 \itempoint Alan M. Turing (1912–1954) : machine de Turing, problème de l'arrêt
@@ -142,7 +144,7 @@ quand il existe un algorithme qui
 Difficultés :
 \begin{itemize}
 \item Comment définir ce qu'est un algorithme ?
-\item Quel type de valeurs ?
+\item Quel type de valeurs (acceptées et renvoyées) ?
 \item Et si l'algorithme ne termine pas ?
 \item Distinction entre intention (l'algorithme) et extension (la fonction).
 \end{itemize}
@@ -160,7 +162,7 @@ des algorithmes qu'elle étudie, uniquement leur \textbf{terminaison en
 
 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.)
+On s'en fiche.)
 
 \bigskip
 
@@ -324,7 +326,7 @@ Deux approches opposées :
 \bigskip
 
 Le typage est plus élégant, plus satisfaisant, plus proche de
-l'informatique réelle.
+l'informatique réelle, on en reparlera.
 
 \smallskip
 
@@ -368,8 +370,8 @@ définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \t
 
 \bigskip
 
-\itempoint Il sera aussi utile de représenter les \alert{programmes} par des
-entiers.
+\itempoint Il sera aussi utile de représenter même les
+\alert{programmes} par des entiers.
 
 \bigskip
 
@@ -411,8 +413,8 @@ une fonction $D \to \mathbb{N}$ définie sur une partie $D \subseteq
 « $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 écrire $f(n) \simeq g(m)$ pour ça.)
+$g(m)\downarrow$, et $f(n) = g(m)$ si $f(n)\downarrow$ ».
+{\footnotesize (Certains préfèrent écrire $f(n) \simeq g(m)$ pour ça.)}
 
 \medskip
 
@@ -615,8 +617,9 @@ f(x,y,z+1) &= y
 
 \medskip
 
-\itempoint $(u,v) \mapsto \max(u-v,0)$ est p.r. (exercice !)
-ou même $u\% v$.
+\itempoint $u \mapsto \max(u-1,0)$ est p.r. (exercice !), comme $(u,v)
+\mapsto \max(u-v,0)$ ou $(u,v) \mapsto u\% v$ ou $(u,v) \mapsto
+\lfloor u/v\rfloor$.
 
 \end{frame}
 %
@@ -714,7 +717,7 @@ devrait être calculable.  Mais cette définition \alert{n'est pas une
 \bigskip
 
 \itempoint On peut montrer que : si $f \colon \mathbb{N}^k \to
-\mathbb{N}$ est p.r., il existe $r$ tel que
+\mathbb{N}$ est p.r., il existe $r$ ($=r(f)$) tel que
 \[
 f(x_1,\ldots,x_k) \leq A(2,\, (x_1+\cdots+x_k+3),\, r)
 \]
@@ -742,7 +745,7 @@ terminant clairement).
 \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).
+\textbf{code} (source) / « programme ».
 
 \bigskip
 
@@ -810,7 +813,8 @@ induction suivant la déf\textsuperscript{n} de $\mathbf{PR}$
 \bigskip
 
 \itempoint Alors $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est
-p.r. \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \psi_e^{(k)})$.
+p.r. \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \psi_e^{(k)})$
+par définition.
 
 {\tiny P.ex., $e = \dbllangle 4,1,\dbllangle 3,3,\dbllangle
   2\dblrangle,\dbllangle 0,3,2\dblrangle\dblrangle,\dbllangle
@@ -833,7 +837,7 @@ en « langage p.r. ».
 
 \medskip
 
-\itempoint Une fonction p.r. a généralement \alert{beaucoup d'indices} :
+\itempoint Une fonction p.r. donnée a \alert{beaucoup d'indices} :
 $\psi_{e_1}^{(k)} = \psi_{e_2}^{(k)} = \cdots$ (programmes équivalents).
 
 \medskip
@@ -930,17 +934,16 @@ Version formelle de l'astuce de Quine
 (\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = h(e,\underline{x})
 \]
 Plus précisément, il existe $b \colon \mathbb{N}^2 \to \mathbb{N}$
-p.r. telle que
+p.r. telle que $e := b(k,d)$ vérifie
 \[
-(\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x})
-\text{~si~}e := b(k,d)
+(\forall d)\,(\forall\underline{x})\quad \psi^{(k)}_e(\underline{x}) = \psi^{(k+1)}_d(e,\underline{x})
 \]
 
 \bigskip
 
-\underline{Preuve :} soit $s := s_{m,1}$ donné par le théorème s-m-n.
+\underline{Preuve :} soit $s := s_{1,k}$ donné par le théorème s-m-n.
 La fonction $(t,\underline{x}) \mapsto h(s(t,t),\underline{x})$ est
-p.r., disons $= \psi_c^{(k+1)}(\underline{x})$.  Alors
+p.r., disons $= \psi_c^{(k+1)}(t,\underline{x})$.  Alors
 \[
 \psi_{s(c,c)}^{(k)}(\underline{x})
 = \psi_{c}^{(k+1)}(c, \underline{x})
@@ -1072,9 +1075,10 @@ non-terminaisons, donc on doit passer par des \alert{fonctions
 \begin{frame}
 \frametitle{L'opérateur $\mu$ de Kleene}
 
-\textbf{Définition :} $\mu g(\underline{x})$ est le plus petit $z$ tel
-que $g(z,\underline{x}) = 0$ et $g(i,\underline{x})\downarrow$ pour
-$0\leq i<z$, s'il existe.
+\textbf{Définition :} si $g\colon \mathbb{N}^{k+1} \dasharrow
+\mathbb{N}$ et $\underline{x} \in \mathbb{N}^k$, alors $\mu
+g(\underline{x})$ est le plus petit $z$ tel que $g(z,\underline{x}) =
+0$ et $g(i,\underline{x})\downarrow$ pour $0\leq i<z$, s'il existe.
 
 \bigskip
 
@@ -1095,6 +1099,12 @@ Concrètement, penser à $\mu g$ comme la fonction
 
 \itempoint Ceci permet toute sorte de \alert{recherche non bornée}.
 
+\bigskip
+
+\itempoint L'opérateur $\mu$ associe à une fonction $g\colon
+\mathbb{N}^{k+1} \dasharrow \mathbb{N}$ une fonction $\mu g\colon
+\mathbb{N}^k \dasharrow \mathbb{N}$.
+
 \end{frame}
 %
 \begin{frame}
@@ -1125,7 +1135,7 @@ f(\underline{x},z+1) &= h(\underline{x},f(\underline{x},z),z)
 \item est stable par l'opérateur $\mu$ : si $g\colon \mathbb{N}^{k+1}
   \dasharrow \mathbb{N}$ est récursive, alors $\mu g\colon
   \mathbb{N}^k \dasharrow \mathbb{N}$ est récursive
-  (\alert{$\leftarrow$ nouveau !}).
+  \textcolor{teal}{($\leftarrow$ nouveau !)}.
 \end{itemize}
 
 \medskip
@@ -1149,8 +1159,8 @@ Cette fois le langage \alert{permet les boucles non bornées} !
 
 \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).
+récursive, celle \alert{codée} par $e$ ou ayant $e$ comme
+\textbf{code} (source) / « programme ».
 
 \bigskip
 
@@ -1182,7 +1192,7 @@ sens informatique).
 
 \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.).
+(divulgâchis : \alert{oui}, \alert{contrairement} au cas p.r.).
 
 \par}
 
@@ -1221,7 +1231,8 @@ induction suivant la déf\textsuperscript{n} de $\mathbf{R}$
 \bigskip
 
 \itempoint Alors $f\colon \mathbb{N}^k \dasharrow \mathbb{N}$ est
-récursive \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \varphi_e^{(k)})$.
+récursive \alert{ssi} $\exists e \in\mathbb{N}.\,(f = \varphi_e^{(k)})$
+par définition.
 
 \end{frame}
 %
@@ -1282,7 +1293,7 @@ entiers naturels) qui « atteste » que $\varphi_e^{(k)}(\underline{x})
 
 \begin{itemize}
 \item La racine est étiquetée « $\varphi_e^{(k)}(\underline{x}) = y$ »
-  ou plutôt « $\dbllangle e, \dbllangle \underline{x}\dblrangle,
+  codé disons « $\dbllangle e, \dbllangle \underline{x}\dblrangle,
   y\dblrangle$ ».
 \item Le sous-arbre porté par chaque fils de la racine est lui-même un
   arbre de calcul pour une sous-expression utilisée dans le calcul de
@@ -1293,14 +1304,14 @@ entiers naturels) qui « atteste » que $\varphi_e^{(k)}(\underline{x})
   $h(g_1(\underline{x}),\ldots,g_\ell(\underline{x}))$, les fils
   portent des arbres de calcul attestant
   $g_1(\underline{x})=v_1,\ldots,g_\ell(\underline{x})=v_\ell$ et
-  $h(\underline{v})=y$.
+  $h(\underline{v})=y$ (donc $\ell+1$ fils).
 \item Pour la récursion primitive $f(\underline{x},z)$, on a soit un
-  seul fils arbre de calcul attestant $g(\underline{x})=y$ lorsque
-  $z=0$ soit deux fils arbres de calcul attestant
-  $f(\underline{x},z')=v$ et $h(\underline{x},v,z')=y$ lorsque
-  $z=z'+1$.
+  seul fils attestant $g(\underline{x})=y$ lorsque $z=0$ soit deux
+  fils attestant $f(\underline{x},z')=v$ et $h(\underline{x},v,z')=y$
+  lorsque $z=z'+1$ (donc $1$ ou $2$ fils).
 \item Pour $f = \mu g$, on a des fils attestant
-  $g(0,\underline{x})=v_0,\ldots,g(y,\underline{x})=v_y$ où $v_y=0$.
+  $g(0,\underline{x})=v_0,\ldots,g(y,\underline{x})=v_y$ où $v_i>0$ si
+  $0\leq i<y$ et $v_y=0$ (donc $y+1$ fils).
 \end{itemize}
 
 \medskip
@@ -1323,7 +1334,7 @@ Formellement :
   c\dblrangle$ ou $\dbllangle 2\dblrangle$, elle n'a pas de
   fils, et $y$ vaut resp\textsuperscript{t} $x_i$, $c$ ou $x+1$,
 \item soit $e = \dbllangle 3, k, d, c_1,\ldots,c_\ell\dblrangle$ et
-  les fils portent des arbres de calculs attestant
+  les $\ell+1$ fils portent des arbres de calculs attestant
   $\varphi_{c_1}^{(k)}(\underline{x})=v_1$, ...,
   $\varphi_{c_\ell}^{(k)}(\underline{x})=v_\ell$ et
   $\varphi_d^{(\ell)}(\underline{v})=y$.
@@ -1331,11 +1342,11 @@ Formellement :
 \begin{itemize}\footnotesize
 \item soit $x_k = 0$ et l'unique fils porte arbre de calcul attestant
   $\varphi_{c}^{(k')}(x_1,\ldots,x_{k'})=y$,
-\item soit $x_k = z+1$ et les deus fils portent arbres de calcul
+\item soit $x_k = z+1$ et les deux fils portent arbres de calcul
   attestant $\varphi_{e}^{(k'+1)}(x_1,\ldots,x_{k'},z)=v$ et
   $\varphi_{d}^{(k'+2)}(x_1,\ldots,x_{k'},v,z)=y$.
 \end{itemize}
-\item soit $e = \dbllangle 5, k, c\dblrangle$ et les fils portent des
+\item soit $e = \dbllangle 5, k, c\dblrangle$ et les $y+1$ fils portent des
   arbres de calcul attestant $\varphi_{c}^{(k+1)}(0,x_1,\ldots,x_k)=v_0$,
   ..., $\varphi_{c}^{(k+1)}(y,x_1,\ldots,x_k)=v_y$ où $v_y=0$ et
   $v_0,\ldots,v_{y-1} > 0$.
@@ -1347,7 +1358,7 @@ $\operatorname{code}(\mathscr{T}) := \dbllangle n,
 \operatorname{code}(\mathscr{T}_1), \ldots,
 \operatorname{code}(\mathscr{T}_s)\dblrangle$ où $n$ est l'étiquette
 de la racine et $\mathscr{T}_1,\ldots,\mathscr{T}_s$ les codes des
-sous-arbres portés par les fils de celle-ci.
+sous-arbres portés par les $s$ fils de celle-ci.
 
 \end{frame}
 %
@@ -1380,7 +1391,8 @@ $\varphi_e^{(k)}(\underline{x})$ en fonction de $e,\underline{x}$ :
 La boucle non-bornée est précisément ce que permet $\mu$.  Tout le
 reste est p.r.
 
-$\Rightarrow$ Ceci montre l'existence de $u$.
+$\Rightarrow$ Ceci montre l'existence de $u$ (code de l'algorithme
+décrit ci-dessus).
 
 \bigskip
 
@@ -1447,13 +1459,14 @@ Exactement comme la version p.r. :
 
 \bigskip
 
-Noter que $s_{m,n}$ est \alert{p.r.} même si on s'intéresse ici aux
-fonctions générales récursives.
+Noter que $s_{m,n}$ est \alert{primitive récursive} même si on
+s'intéresse ici aux fonctions générales récursives.
 
 \medskip
 
-Les manipulations de programmes sont typiquement p.r. (même si les
-programmes manipulés sont des fonctions générales récursives).
+Les manipulations de programmes sont \textcolor{blue}{typiquement
+  p.r.} (même si les programmes manipulés sont des fonctions générales
+récursives).
 
 \end{frame}
 %
@@ -1525,18 +1538,17 @@ Exactement comme la version p.r. :
 h(e,\underline{x})
 \]
 Plus précisément, il existe $b \colon \mathbb{N}^2 \to \mathbb{N}$
-p.r. telle que
+p.r. telle que $e := b(k,d)$ vérifie
 \[
-(\forall\underline{x})\quad \varphi^{(k)}_e(\underline{x}) = \varphi^{(k+1)}_d(e,\underline{x})
-\text{~si~}e := b(k,d)
+(\forall d)\,(\forall\underline{x})\quad \varphi^{(k)}_e(\underline{x}) = \varphi^{(k+1)}_d(e,\underline{x})
 \]
 
 \bigskip
 
-\underline{Même preuve :} soit $s := s_{m,1}$ donné par le théorème
+\underline{Même preuve :} soit $s := s_{1,k}$ donné par le théorème
 s-m-n.  La fonction $(t,\underline{x}) \mapsto
 h(s(t,t),\underline{x})$ est p.r., disons $=
-\varphi_c^{(k+1)}(\underline{x})$.  Alors
+\varphi_c^{(k+1)}(t,\underline{x})$.  Alors
 \[
 \varphi_{s(c,c)}^{(k)}(\underline{x})
 = \varphi_{c}^{(k+1)}(c, \underline{x})
@@ -1560,8 +1572,8 @@ Reformulation du théorème de récursion utilisant l'universalité :
 \smallskip
 
 \itempoint\textbf{Théorème} (Kleene-Rogers) : si $F \colon \mathbb{N}
-\to \mathbb{N}$ est récursive \emph{totale} et $k\in\mathbb{N}$, il
-existe $e$ tel que
+\dasharrow \mathbb{N}$ est récursive et $k\in\mathbb{N}$, il existe
+$e$ tel que
 \[
 \varphi_e^{(k)} = \varphi_{F(e)}^{(k)}
 \]
@@ -1576,6 +1588,13 @@ théorème de récursion, il existe $e$ tel que
 $\varphi^{(k)}_e(\underline{x}) = h(e,\underline{x}) =
 \varphi_{F(e)}^{(k)}(\underline{x})$.\qed
 
+\bigskip
+
+\textcolor{blue}{\textbf{Moralité :}} quelle que soit la
+transformation $F$ calculable effectuée sur le source d'un programme,
+il y a un programme $e$ qui fait la même chose que son
+transformé $F(e)$.
+
 \end{frame}
 %
 \begin{frame}
@@ -1642,6 +1661,11 @@ return interpret(self, n-1) + interpret(self, n-2);\\
 \textbf{Défi :} trouver explicitement un $e$ tel que $\varphi^{(3)}_e$
 soit la fonction d'Ackermann.
 
+\smallskip
+
+(La fonction d'Ackermann a été définie par des appels récursifs donc
+elle est bien censée être calculable.)
+
 \end{frame}
 %
 \begin{frame}
@@ -1665,6 +1689,13 @@ Cette question est-elle \alert{algorithmique} ?
 
 \textbf{Réponse} de Turing : \alert{non}.
 
+\bigskip
+
+\itempoint \textcolor{blue}{Intuition de la preuve :} supposons que
+j'aie un moyen algorithmique pour savoir si un algorithme termine ou
+pas, je peux lui demander ce que « je » vais faire (astuce de
+Quine !), et faire le contraire, ce qui conduit à un paradoxe.
+
 \end{frame}
 %
 \begin{frame}
@@ -1691,22 +1722,20 @@ v\colon (e,x) \mapsto \left\{
 est générale récursive (tester is $h(e,x)=0$, si oui renvoyer $42$,
 sinon faire une boucle infinie, p.ex. $\mu(x\mapsto 1)$).
 
+\medskip
+
 Par le théorème de récursion de Kleene, il existe $e$ tel que
 $\varphi^{(1)}_e(x) = v(e,x)$.
 
+\medskip
+
 Si $\varphi^{(1)}_e(x)\downarrow$ alors $h(e,x) = 1$ donc
-$v(e,x)\uparrow$ donc $\varphi^{(1)}_e(x)\uparrow$, une contradiction.
+$v(e,x)\uparrow$ donc $\varphi^{(1)}_e(x)\uparrow$, contradiction.
+
 Si $\varphi^{(1)}_e(x)\uparrow$ alors $h(e,x) = 0$ donc
-$v(e,x)\downarrow$ donc $\varphi^{(1)}_e(x)\downarrow$, une
+$v(e,x)\downarrow$ donc $\varphi^{(1)}_e(x)\downarrow$,
 contradiction.\qed
 
-\bigskip
-
-\itempoint Intuition de la preuve : supposons que j'aie un moyen
-algorithmique $h$ pour savoir si un algorithme termine ou pas, je peux
-lui demander ce que « je » vais faire (astuce de Quine), et faire le
-contraire, ce qui conduit à un paradoxe.
-
 \end{frame}
 %
 \begin{frame}
@@ -1744,9 +1773,9 @@ une fonction qui diffère en tout point de la diagonale $c \mapsto
 
 \medskip
 
-Pour les fonctions p.r. (terminent toujours !), le même argument
-diagonal donnait l'inexistence d'un programme universel
-(transp. \ref{primitive-recursive-no-universality}).
+{\footnotesize Pour les fonctions p.r. (qui terminent toujours !), le
+  même argument diagonal donnait l'inexistence d'un programme
+  universel (transp. \ref{primitive-recursive-no-universality}).\par}
 
 \end{frame}
 %
@@ -1892,7 +1921,7 @@ finie ou infinie $C^{(0)},C^{(1)},C^{(2)},\ldots$, où
     s'arrête}, que $C^{(n)}$ est la \textbf{configuration finale}, et
   que l'exécution a duré $n$ \textbf{étapes},
 \item sinon, $C^{(n+1)}$ est la configuration suivante (définie
-  avant).
+  transp. précédent).
 \end{itemize}
 
 \bigskip
@@ -1904,6 +1933,7 @@ tombe dans l'état $0$.
 \end{frame}
 %
 \begin{frame}
+\label{simulation-of-turing-machines-by-recursive-functions}
 \frametitle{Simulation des machines de Turing par les fonctions récursives}
 
 \itempoint On peut coder un programme et/ou une configuration sous
@@ -1962,8 +1992,9 @@ j\leq 1+x_1+x_2$, etc.,
 \item si $f(x_1,\ldots,x_k){\downarrow} = y$, la machine s'arrête avec
   la tête à l'emplacement $0$ (le même qu'au départ), le ruban
   $\beta(j)$ non modifié pour $j<0$, et
-\item les symboles $\beta(j)$ pour $j\geq 0$ du ruban final forment
-  le mot $0 1^y 0$ (suivi d'une inifinité de $0$).
+\item les symboles $\beta(j)$ pour $j\geq 0$ du ruban final forment le
+  mot $0 1^y 0$ (suivi d'une infinité de $0$) {\footnotesize (« codage
+    unaire » de $y$)}.
 \end{itemize}
 
 \end{frame}
@@ -1987,8 +2018,8 @@ primitive, $\mu$-récursion).
 \bigskip
 
 \itempoint Les conventions faites, notamment le fait d'ignorer et de
-ne pas modifier $\beta(j)$ pour $j<0$, permettent à l'induction de
-fonctionner.
+ne pas modifier $\beta(j)$ pour $j<0$, permettent à l'induction dans
+la preuve de fonctionner.
 
 \smallskip
 
@@ -2007,7 +2038,7 @@ fonctionner.
 
 \itempoint Toute fonction générale récursive $\mathbb{N}^k \dasharrow
 \mathbb{N}$ est calculable par machine de Turing (sous les conventions
-données).
+données) : transp. précédent.
 
 \bigskip
 
@@ -2015,7 +2046,8 @@ données).
 \mathbb{N}$ calculable par machine de Turing sous ces conventions est
 générale récursive, car les fonctions récursives peuvent simuler les
 machines de Turing, calculer une configuration initiale convenable, et
-décoder la configuration finale.
+décoder la configuration finale
+(cf. transp. \ref{simulation-of-turing-machines-by-recursive-functions}).
 
 \bigskip
 
@@ -2110,11 +2142,53 @@ jour ».
 \end{frame}
 %
 \begin{frame}
+\label{undecidability-halting-problem-turing-machines-pristine-start}
+\frametitle{Indécidabilité du problème de l'arrêt (départ bande vierge)}
+
+On ne peut même pas tester algorithmiquement si une machine de Turing
+s'arrête à partir d'une bande vierge :
+
+\smallskip
+
+\itempoint\textbf{Indécidabilité du problème de l'arrêt :} la fonction
+qui à $M$ associe $1$ si la machine de Turing s'arrête en partant de
+la configuration vierge $C_0$ (c'est-à-dire celle où $\beta = 0$, état
+initial $1$), et $0$ sinon, \alert{n'est pas calculable}.
+
+\medskip
+
+\underline{Preuve :} Supposons par l'absurde qu'on puisse tester
+algorithmiquement si une machine de Turing s'arrête à partir d'une
+configuration vierge.  On va montrer qu'on peut tester si une machine
+de Turing $M$ s'arrête à partir de $C$ quelconque.
+
+\smallskip
+
+Données $M$ et $C$, on peut algorithmiquement calculer une machine $N$
+qui « prépare » $C$ à partir de la configuration vierge $C_0$, donc
+une machine $M^*$ qui exécute successivement $N$ puis $M$
+\textcolor{teal}{($\leftarrow$ ceci est un théorème s-m-n)}.
+
+\smallskip
+
+Ainsi $M^*$ (calculé algorithmiquement) termine sur $C_0$ ssi $M$
+termine sur $C$.
+
+\smallskip
+
+Donc tester la terminaison de $M^*$ permettrait de tester celle de
+$M$ sur $C$, ce qui n'est pas possible
+\textcolor{teal}{($\leftarrow$ ceci est une preuve « par
+  réduction »)}.\qed
+
+\end{frame}
+%
+\begin{frame}
 \frametitle{Le castor affairé}
 
 \itempoint La fonction \textbf{castor affairé} associe à $m$ le nombre
 maximal $B(m)$ d'étapes d'exécution d'une machine de Turing à $\leq m$
-états \alert{qui termine} (à partir d'une bande vierge : $\beta = 0$).
+états \alert{qui termine} (à partir de la configuration vierge $C_0$).
 
 \medskip
 
@@ -2128,28 +2202,20 @@ maximal $B(m)$ d'étapes d'exécution d'une machine de Turing à $\leq m$
 
 \medskip
 
-{\footnotesize
-
 \underline{Preuve :} supposons au contraire $\forall m\in\mathbb{N}.\;
 (B(m) \leq f(m))$ avec $f\colon\mathbb{N}\to\mathbb{N}$ calculable.
-Donnée une machine de Turing $M$ et une configuration initiale $C$, on
-peut alors algorithmiquement décider si $M$ s'arrête à partir de $C$ :
-\begin{itemize}
-\item fabriquer une machine $M^*$ qui réalise $C$ à partir de la
-  configuration vierge $C_0$ \textcolor{teal}{($\leftarrow$ thm
-    s-m-n ici)}, puis fait ce que fait $M$, donc $M^*$ termine sur
-  $C_0$ ssi $M$ termine sur $C$,
-\item calculer $f(m)$ où $m$ est le nombre d'états de $M^*$,
-\item exécuter $M^*$ à partir de $C_0$ pendant $f(m)$ étapes (ce
-  nombre est $\geq B(m)$ par hypothèse),
-\item si elle a terminé, $M^*$ termine sur $C_0$, donc $M$ sur $C$, et
-  on renvoie « oui » ; sinon, elle ne termine jamais par définition de
+Donnée une machine de Turing $M$, on peut alors algorithmiquement
+décider si $M$ s'arrête à partir de $C_0$ :
+\begin{itemize}
+\item calculer $f(m)$ où $m$ est le nombre d'états de $M$,
+\item exécuter $M$ à partir de $C_0$ pendant $f(m)$ étapes (ce nombre
+  est $\geq B(m)$ par hypothèse),
+\item si elle a terminé en temps imparti, $M$ termine sur $C_0$, et on
+  renvoie « oui » ; sinon, elle ne termine jamais par définition de
   $B(m)$, on renvoie « non ».
 \end{itemize}
 Ceci est impossible donc $f$ n'est pas calculable.\qed
 
-\par}
-
 \end{frame}
 %
 \begin{frame}
@@ -2176,19 +2242,20 @@ calculable :
 
 \underline{Preuve :} soit $f\colon\mathbb{N}\to\mathbb{N}$ calculable.
 Soit $\gamma(r) = A(2,r,r)$ (en fait, $2^r$ doit suffire ; noter
-$\gamma$ croissante).  On considère la machine de Turing $M_r$ qui
+$\gamma$ croissante).  Pour $r \in \mathbb{N}$, on considère la
+machine de Turing $M_r$ qui
 \begin{itemize}
-\item calcule $\gamma(r+1)$ puis $f(0) + f(1) + \cdots +
+\item prépare $r$, calcule $\gamma(r+1)$ puis $f(0) + f(1) + \cdots +
   f(\gamma(r+1)) + 1$,
 \item attend ce nombre-là d'étapes, et termine.
 \end{itemize}
-Par le théorème s-m-n, le nombre d'états de $M_r$ est une fonction
-p.r. $b(r)$ de $r$ (même $b(r) = r + \mathrm{const}$ convient).  Pour
-$r\geq r_0$ on a $b(r) \leq \gamma(r)$.  Soit $m_0 = \gamma(r_0)$.  Si
-$m \geq m_0$, soit $r\geq r_0$ tel que $\gamma(r) \leq m \leq
-\gamma(r+1)$.  Alors $M_r$ calcule $\cdots+f(m)+\cdots+1$, donc attend
-$>f(m)$ étapes.  Donc $B(b(r)) > f(m)$.  Mais $b(r) \leq \gamma(r)
-\leq m$ donc $B(m) > f(m)$.\qed
+Le nombre d'états de $M_r$ est une fonction p.r. $b(r)$ de $r$ (même
+$b(r) = r + \mathrm{const}$ convient).  Pour $r\geq r_0$ on a $b(r)
+\leq \gamma(r)$.  Soit $m_0 = \gamma(r_0)$.  Si $m \geq m_0$, soit
+$r\geq r_0$ tel que $\gamma(r) \leq m \leq \gamma(r+1)$.  Alors $M_r$
+calcule $\cdots+f(m)+\cdots+1$, donc attend $>f(m)$ étapes.  Donc
+$B(b(r)) > f(m)$.  Mais $b(r) \leq \gamma(r) \leq m$ donc $B(m) >
+f(m)$.\qed
 
 \par}
 
@@ -2430,7 +2497,9 @@ $(e,x)$, on peut exécuter $\varphi_e(x)$, et, s'il termine, renvoyer
 \item $\{e\in \mathbb{N} : \varphi_e(e)\downarrow$ n'est pas décidable
   (preuve dans transp. \ref{undecidability-halting-problem-redux})
 \item $\{e\in \mathbb{N} : \varphi_e(0)\downarrow$ n'est pas décidable
-  (théorème s-m-n : $\varphi_e(x) = \varphi_{s(e,x)}(0)$ avec $s$ p.r.)
+  (théorème s-m-n : $\varphi_e(x) = \varphi_{s(e,x)}(0)$ avec $s$
+  p.r. ;
+  cf. transp. \ref{undecidability-halting-problem-turing-machines-pristine-start})
 \end{itemize}
 
 \par}
@@ -2588,7 +2657,7 @@ Alors $h \colon \mathbb{N}^2 \dasharrow \mathbb{N}$ est calculable par
 hypothèse (on peut décider si $e\in \Phi^{-1}(F)$).  Par le théorème
 de récursion de Kleene (transp. \ref{kleene-recursion-theorem}), il
 existe $e$ tel que
-\[\Phi(e) := \varphi^{(1)}_e(x) = h(e,x)\]
+\[\varphi^{(1)}_e(x) = h(e,x)\]
 
 Si $e \in \Phi^{-1}(F)$ alors $h(e,x) = g(x)$ pour tout $x$, donc
 $\Phi(e) = g$ donc $e \not\in \Phi^{-1}(F)$, une contradiction.  Si $e
@@ -2630,7 +2699,7 @@ intuitivement,
 
 \centerline{« $A$ se réduit à $B$ »}
 
-\centerline{$\Longleftrightarrow$}
+\centerline{signifie}
 
 \centerline{« si $B$ est décidable alors $A$ est décidable »}