Reformulate formalizations of Turing reduction.

(Still not happy about this.)

1 files changed, 23 insertions, 21 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index eb34f62..8bad0a5 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -2806,33 +2806,35 @@ que $A \mathrel{\leq_\mathrm{m}} B$.
 \frametitle{Réduction de Turing : formalisation(s) possible(s)}
 
 Comment définir $A \mathrel{\leq_\mathrm{T}} B$ pour $A, B \subseteq
-\mathbb{N}$ ?
+\mathbb{N}$ ?  {\footnotesize (I.e., « $A$ est calculable en
+  utilisant $B$ ».)}
 
 \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$.
+\textbf{Formalisation 1 :} la fonction indicatrice $\mathbf{1}_A$
+de $A$ appartient à la plus petite classe de fonctions qui contient
+les projections, les constantes, la fonction successeur \alert{et la
+  fonction indicatrice $\mathbf{1}_B$ 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}$, énumère un « arbre de décision » binaire
-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
-sur la bonne branche la réponse correcte en temps fini.
+\textbf{Formalisation 2 :} il existe une fonction calculable qui prend
+en entrée $m \in \mathbb{N}$ et une liste $\dbllangle \langle n_0,
+\mathbf{1}_B(n_0)\rangle, \ldots, \langle n_k,
+\mathbf{1}_B(n_k)\rangle \dblrangle$ de réponses à des questions “$n
+\in B$ ?”, et qui (si ces réponses cont correctes !) termine et renvoie
+\begin{itemize}
+\item soit une réponse finale à la question “$m \in A$ ?” (disons
+  encodée comme $\langle 0, \mathbf{1}_A(m)\rangle$),
+\item soit une nouvelle interrogation “$n \in B$ ?” (disons encodée
+  comme $\langle 1, n\rangle$),
+\end{itemize}
+de sorte que si on commence par $k=0$ et qu'on ajoute à chaque fois la
+réponse correcte $\langle n_{k+1}, \mathbf{1}_B(n_{k+1})\rangle$ à
+l'interrogation $\langle 1, n_{k+1}\rangle$ posée, alors la fonction
+finit par produite la réponse finale correcte ($\langle 0,
+\mathbf{1}_A(m)\rangle$).
 
 \end{frame}
 %