diff options
| -rw-r--r-- | transp-inf110-01-calc.tex | 44 |
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} % |