From e78546b7ac68ad194e59a19f5b66dee7fc17bd34 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 17 Nov 2023 13:47:29 +0100
Subject: Fix various mistakes (or notational blunders) noted during lecture on
2023-11-17.
---
transp-inf110-01-calc.tex | 45 ++++++++++++++++++++++++---------------------
1 file 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
--
cgit v1.2.3