diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 45 |
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 |