Fix various mistakes (or notational blunders) noted during lecture on 2023-11-17.

1 files changed, 24 insertions, 21 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 25c78e1..653dfbb 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -2585,10 +2585,10 @@ Les ensembles \textbf{semi-décidables} sont stables par :
 \begin{frame}
 \frametitle{Le théorème de Rice : énoncé}
 
-Soit $\textbf{PR}^{(1)}$ l'ensemble des fonctions partielles
+Soit $\textbf{R}^{(1)}$ l'ensemble des fonctions partielles
 $\mathbb{N} \dasharrow \mathbb{N}$ calculables (= générales
 récursives), et $\Phi \colon e \mapsto \varphi^{(1)}_e$ qui définit
-une surjection $\mathbb{N} \to \textbf{PR}^{(1)}$.
+une surjection $\mathbb{N} \to \textbf{R}^{(1)}$.
 
 \medskip
 
@@ -2599,9 +2599,9 @@ une surjection $\mathbb{N} \to \textbf{PR}^{(1)}$.
 \bigskip
 
 \itempoint\textbf{Théorème} (Rice) : si $F \subseteq
-\textbf{PR}^{(1)}$ est un ensemble de fonctions partielles tel que
+\textbf{R}^{(1)}$ est un ensemble de fonctions partielles tel que
 $\Phi^{-1}(F) := \{e \in \mathbb{N} : \varphi^{(1)}_e \in F\}$ est
-\emph{décidable}, alors $F = \varnothing$ ou $F = \textbf{PR}^{(1)}$.
+\emph{décidable}, alors $F = \varnothing$ ou $F = \textbf{R}^{(1)}$.
 
 \bigskip
 
@@ -2628,15 +2628,15 @@ Exemples :
 \begin{frame}
 \frametitle{Le théorème de Rice : preuve par théorème de récursion}
 
-{\footnotesize $\textbf{PR}^{(1)} = \{f \colon
+{\footnotesize $\textbf{R}^{(1)} = \{f \colon
   \mathbb{N}\dasharrow\mathbb{N} : f\text{~calculable}\}$\par}
 
 \smallskip
 
 \itempoint\textbf{Théorème} (Rice) : si $F \subseteq
-\textbf{PR}^{(1)}$ est un ensemble de fonctions partielles tel que
+\textbf{R}^{(1)}$ est un ensemble de fonctions partielles tel que
 $\Phi^{-1}(F) := \{e \in \mathbb{N} : \varphi^{(1)}_e \in F\}$ est
-\emph{décidable}, alors $F = \varnothing$ ou $F = \textbf{PR}^{(1)}$.
+\emph{décidable}, alors $F = \varnothing$ ou $F = \textbf{R}^{(1)}$.
 
 \bigskip
 
@@ -2645,9 +2645,9 @@ $\Phi^{-1}(F) := \{e \in \mathbb{N} : \varphi^{(1)}_e \in F\}$ est
 
 \smallskip
 
-\underline{Preuve :} Supposons par l'absurde $F$ décidable avec $F
-\neq \varnothing$ et $F \neq \textbf{PR}^{(1)}$.  Soient $f \in F$ et
-$g \not\in F$.  Soit
+\underline{Preuve :} Supposons par l'absurde $\Phi^{-1}(F)$ décidable
+avec $F \neq \varnothing$ et $F \neq \textbf{R}^{(1)}$.  Soient $f \in
+F$ et $g \not\in F$.  Soit
 \[
 h(e,x) := \left\{
 \begin{array}{ll}
@@ -2713,20 +2713,20 @@ intuitivement,
 \begin{frame}
 \frametitle{Le théorème de Rice : preuve par réduction (1/2)}
 
-{\footnotesize $\textbf{PR}^{(1)} = \{f \colon
+{\footnotesize $\textbf{R}^{(1)} = \{f \colon
   \mathbb{N}\dasharrow\mathbb{N} : f\text{~calculable}\}$\par}
 
 \smallskip
 
 \itempoint\textbf{Théorème} (Rice) : si $F \subseteq
-\textbf{PR}^{(1)}$ est tel que $F \neq \varnothing$ et $F \neq
-\textbf{PR}^{(1)}$, alors $\Phi^{-1}(F) := \{e \in \mathbb{N} :
+\textbf{R}^{(1)}$ est tel que $F \neq \varnothing$ et $F \neq
+\textbf{R}^{(1)}$, alors $\Phi^{-1}(F) := \{e \in \mathbb{N} :
 \varphi^{(1)}_e \in F\}$ \emph{n'est pas décidable}.
 
 \bigskip
 
-\underline{Preuve :} Soit $F \subseteq \textbf{PR}^{(1)}$ avec $F \neq
-\varnothing$ et $F \neq \textbf{PR}^{(1)}$.  Quitte à remplacer $F$
+\underline{Preuve :} Soit $F \subseteq \textbf{R}^{(1)}$ avec $F \neq
+\varnothing$ et $F \neq \textbf{R}^{(1)}$.  Quitte à remplacer $F$
 par $\complement F$, o.p.s. ${\uparrow} \not\in F$ où $\uparrow$ est
 la fonction nulle part définie.  Soit $f\in F$ où $f =
 \varphi^{(1)}_a$.
@@ -2756,9 +2756,9 @@ notamment $\varphi^{(1)}_{b(e,x)} \in F$ ssi $\varphi^{(1)}_e(x)\downarrow$
 \begin{frame}
 \frametitle{Le théorème de Rice : preuve par réduction (2/2)}
 
-{\footnotesize $\textbf{PR}^{(1)} = \{f \colon
+{\footnotesize $\textbf{R}^{(1)} = \{f \colon
   \mathbb{N}\dasharrow\mathbb{N} : f\text{~calculable}\}$ ; on a
-  supposé $F \subseteq \textbf{PR}^{(1)}$ avec ${\uparrow}\not\in F$
+  supposé $F \subseteq \textbf{R}^{(1)}$ avec ${\uparrow}\not\in F$
   et $f \in F$\par}
 
 \smallskip
@@ -2808,7 +2808,7 @@ On dit qu'on a \alert{réduit le problème de l'arrêt} à $\Phi^{-1}(F)$
 
 \textcolor{blue}{\textbf{Intuitivement :}} si j'ai un gadget qui
 répond à la question “$n \in B$ ?”, je peux répondre à la question “$m
-\in A$ ?” en transformant $m$ en $\rho(n)$ et en utilisant le gadget
+\in A$ ?” en transformant $m$ en $\rho(m) =: n$ et en utilisant le gadget
 {\footnotesize (une seule fois, à la fin)}.
 
 \bigskip
@@ -2949,7 +2949,10 @@ $\mathrel{\equiv_\mathrm{m}}$).
 
 Les parties décidables de $\mathbb{N}$ forment le plus petit degré de
 Turing, souvent noté $\mathbf{0}$.  Le degré de Turing de
-$\mathscr{H}$ est noté $\mathbf{0'}$.
+$\mathscr{H}$ est noté $\mathbf{0'}$.  (Il existe des ensembles de
+degré strictement compris entre $\mathbf{0}$ et $\mathbf{0'}$, même
+des ensembles semi-décidables, mais il semble qu'aucun n'apparaît
+naturellement.)
 
 \par}
 
@@ -3171,8 +3174,8 @@ Pour \alert{éviter} ce théorème, on va faire un choix simple de redex
 \itempoint On appelle \textbf{redex extérieur gauche} d'un
 $\lambda$-terme le redex dont le $\lambda$ est \alert{le plus à
   gauche}.  Exemples : $\lambda x.x(\textcolor{purple}{(\lambda
-  y.y)x})$ ; $\lambda x.(\textcolor{purple}{\lambda y.(\lambda
-  z.z)y})x$.
+  y.y)x})$ ; $\lambda x.\textcolor{purple}{(\lambda y.(\lambda
+  z.z)y)x}$.
 
 \medskip