A few things about Turing reduction.

1 files changed, 128 insertions, 3 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 6eaf10d..659080f 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -2735,13 +2735,19 @@ 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(n)$ et en utilisant le gadget
+{\footnotesize (une seule fois, à la fin)}.
 
 \bigskip
 
 \textbf{Clairement}, si $A \mathrel{\leq_\mathrm{m}} B$ avec $B$
-décidable, alors $A$ est décidable.  \emph{Notamment}, si $\mathscr{H}
-\mathrel{\leq_\mathrm{m}} D$ alors $D$ \emph{n'est pas} décidable.
+décidable (resp. semi-décidable), alors $A$ est décidable
+(resp. semi-décidable).
+
+\smallskip
+
+\emph{Notamment}, si $\mathscr{H} \mathrel{\leq_\mathrm{m}} D$ alors
+$D$ \emph{n'est pas} décidable.
 
 \bigskip
 
@@ -2755,6 +2761,125 @@ décidable, alors $A$ est décidable.  \emph{Notamment}, si $\mathscr{H}
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Réduction de Turing : présentation informelle}
+
+\textbf{Informellement :} Si $A,B\subseteq\mathbb{N}$, on note $A
+\mathrel{\leq_\mathrm{T}} B$ s'il existe un algorithme qui
+\begin{itemize}
+\item prend en entrée $m \in \mathbb{N}$,
+\item peut à tout moment demander à savoir si $n \in B$
+  (\textcolor{teal}{« interroger l'oracle »}),
+\item termine en temps fini,
+\item et renvoie « oui » si $m \in A$, et « non » si $m \not\in A$.
+\end{itemize}
+
+\bigskip
+
+\textcolor{blue}{\textbf{Intuitivement :}} à la différence de la
+réduction many-to-one où on ne peut poser la question “$n \in B$ ?”
+que sur une seule valeur $\rho(n)$ à la fin du calcul, ici on peut
+interroger l'oracle de façon libre et illimitée (mais finie !) au
+cours de l'algorithme.
+
+\bigskip
+
+La relation $A \mathrel{\leq_\mathrm{T}} B$ est beaucoup plus faible
+que $A \mathrel{\leq_\mathrm{m}} B$.
+
+\smallskip
+
+{\footnotesize Par exemple, $(\complement B) \mathrel{\leq_\mathrm{T}}
+  B$ pour tout $B\subseteq\mathbb{N}$ (savoir décider “$n \in B$ ?”
+  permet évidemment de décider “$n \not\in B$ ?”), alors que
+  $(\complement \mathscr{H}) \mathrel{\not\leq_\mathrm{m}}
+  \mathscr{H}$ car $\complement \mathscr{H}$ n'est pas
+  semi-décidable.\par}
+
+\bigskip
+
+\textcolor{brown}{Mais comment formaliser cette « interrogation » ?}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Réduction de Turing : formalisation(s) possible(s)}
+
+Comment définir $A \mathrel{\leq_\mathrm{T}} B$ pour $A, B \subseteq
+\mathbb{N}$ ?
+
+\bigskip
+
+\textbf{Formalisation 1 :} la fonction indicatrice de $A$ appartient à
+la plus petite classe de fonctions qui contient les projections, les
+constantes, la fonction successeur \alert{et la fonction indicatrice
+  de $B$} et stable par composition, récursion primitive et
+opérateur $\mu$.
+
+\bigskip
+
+\textbf{Formalisation 2 :} la fonction indicatrice de $A$ est
+calculable par une machine de Turing modifiée qui, quand elle passe
+dans un état spécial « interroger l'oracle », remplace la valeur $n$
+écrite en unaire à droite de la tête de lecture, par $1$ ou $0$ selon
+que $n\in B$ ou $n\not\in B$ et passe dans un état spécial « réponse
+de l'oracle ».
+
+\bigskip
+
+\textbf{Formalisation 3 :} il existe une fonction calculable (usuelle)
+qui, pour $m\in \mathbb{N}$, calcule un « arbre de décision » binaire
+fini dont les nœuds sont étiquetées par des questions “$n \in B$ ?”
+(pour divers $n$), les fils par les réponses oui/non à cette quesion,
+et les feuilles par des réponses oui/non à la question “$m \in A$ ?”,
+donnant la réponse correcte sur la bonne branche.
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Réduction de Turing : quelques propriétés}
+
+\textbf{Clairement}, si $A \mathrel{\leq_\mathrm{T}} B$ avec $B$
+décidable, alors $A$ est décidable.
+
+{\footnotesize (Ceci \alert{ne vaut pas} pour
+  « semi-décidable ».)\par}
+
+\smallskip
+
+\emph{Notamment}, si $\mathscr{H} \mathrel{\leq_\mathrm{T}} D$ alors
+$D$ \emph{n'est pas} décidable.
+
+\bigskip
+
+{\footnotesize
+
+La relation $\mathrel{\leq_\mathrm{T}}$ est réflexive et transitive
+(c'est un « préordre ») ; la relation $\mathrel{\equiv_\mathrm{T}}$
+définie par $A \mathrel{\equiv_\mathrm{T}} B$ ssi $A
+\mathrel{\leq_\mathrm{T}} B$ et $B \mathrel{\leq_\mathrm{T}} A$ est
+une relation d'équivalence, les classes pour laquelle s'appellent
+« degrés de Turing » et sont partiellement ordonnés par
+$\mathrel{\leq_\mathrm{T}}$.
+
+\medskip
+
+Comme $A \mathrel{\leq_\mathrm{m}} B$ implique $A
+\mathrel{\leq_\mathrm{T}} B$, chaque degré de Turing est une réunion
+de degrés many-to-one (la relation d'équivalence
+$\mathrel{\equiv_\mathrm{T}}$ est plus grossière que
+$\mathrel{\equiv_\mathrm{m}}$).
+
+\medskip
+
+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'}$.
+
+\par}
+
+\end{frame}
+%
 \section{Le \texorpdfstring{$\lambda$}{lambda}-calcul non typé}
 \begin{frame}
 \frametitle{Le $\lambda$-calcul : aperçu}