One formalization of Turing reduction was wrong: quick fix (to be improved!).

1 files changed, 5 insertions, 5 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 659080f..fec78e3 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -2828,11 +2828,11 @@ 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.
+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.
 
 \end{frame}
 %