From 1cdc71929d53c17035577becf2c88f0650ddf5a7 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 2 Nov 2023 17:08:48 +0100 Subject: A few things about Turing reduction. --- transp-inf110-01-calc.tex | 131 ++++++++++++++++++++++++++++++++++++++++++++-- 1 file 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 @@ -2753,6 +2759,125 @@ décidable, alors $A$ est décidable. \emph{Notamment}, si $\mathscr{H} les classes pour laquelle s'appellent « degrés many-to-one » et sont partiellement ordonnés par $\mathrel{\leq_\mathrm{m}}$.\par} +\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é} -- cgit v1.2.3