From f190c1e5960589c31bb6ce489080b39595c52a74 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 2 Nov 2023 19:19:21 +0100 Subject: One formalization of Turing reduction was wrong: quick fix (to be improved!). --- transp-inf110-01-calc.tex | 10 +++++----- 1 file 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} % -- cgit v1.2.3