diff options
| -rw-r--r-- | exercices-inf110.tex | 129 |
1 files changed, 129 insertions, 0 deletions
diff --git a/exercices-inf110.tex b/exercices-inf110.tex index ec141fe..d43d56f 100644 --- a/exercices-inf110.tex +++ b/exercices-inf110.tex @@ -1030,6 +1030,135 @@ générale récursive, est elle-même calculable, i.e., générale récursive.) \end{corrige} +% + +\exercice\ (${\star}{\star}$)\par\nobreak + +On dira que deux parties $L,M$ de $\mathbb{N}$ disjointes +(c'est-à-dire $L\cap M = \varnothing$) sont \textbf{calculablement + séparables} lorsqu'il existe un $E \subseteq \mathbb{N}$ décidable +tel que $L \subseteq E$ et $M \subseteq \complement E$ (où +$\complement E$ désigne le complémentaire de $E$) ; dans le cas +contraire, on les dit \textbf{calculablement inséparables}. + +\textbf{(1)} Expliquer pourquoi deux ensembles $L,M \subseteq +\mathbb{N}$ disjoints sont calculablement séparables si et seulement +s'il existe un algorithme qui, prenant en entrée un élément $x$ +de $\mathbb{N}$ : +\begin{itemize} +\item termine toujours en temps fini, +\item répond « vrai » si $x\in L$ et « faux » si $x \in M$ (rien n'est + imposé si $x\not\in L\cup M$). +\end{itemize} + +\textbf{(2)} Expliquer pourquoi deux ensembles \emph{décidables} +disjoints sont toujours calculablement séparables. + +On cherche maintenant à montrer qu'il existe deux ensembles $L,M +\subseteq \mathbb{N}$ \emph{semi-décidables} disjoints et +calculablement \emph{in}séparables. + +Pour cela, on appelle $L := \{\langle e,x\rangle : +\varphi_e(x){\downarrow} = 1\}$ l'ensemble des codes des couples +$\langle e,x\rangle$ formés d'un programme (=algorithme) $e$ et d'une +entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$ +termine en temps fini et renvoie la valeur $1$ ; et $M := \{\langle +e,x\rangle : \varphi_e(x){\downarrow} = 2\}$ l'ensemble défini de la +même manière mais avec la valeur $2$. + +\textbf{(3)} Pourquoi $L$ et $M$ sont-ils disjoints ? + +\textbf{(4)} Pourquoi $L$ et $M$ sont-ils semi-décidables ? + +\textbf{(5)} En imitant la démonstration du théorème de Turing sur +l'indécidabilité du problème de l'arrêt, ou bien en utilisant le +théorème de récursion de Kleene, montrer qu'il n'existe aucun +algorithme qui, prenant en entrée le code d'un couple $\langle +e,x\rangle$, termine toujours en temps fini et répond « vrai » si +$\langle e,x\rangle\in L$ et « faux » si $\langle e,x\rangle \in M$ +(\emph{indication :} si un tel algorithme existait, on pourrait s'en +servir pour faire le contraire de ce qu'il prédit). + +\textbf{(6)} Conclure. + +\begin{corrige} +\textbf{(1)} Si $E$ est décidable tel que $L \subseteq E$ et $M +\subseteq \complement E$, alors un algorithme qui décide $E$ +(c'est-à-dire, quand on lui fournit l'entrée $x$, répond « vrai » si +$x\in E$, et « faux » si $x \not\in E$) répond bien aux critères +demandés. Réciproquement, donné un algorithme qui répond aux critères +demandés, si $E$ est l'ensemble des $x$ sur lesquels il répond +« vrai », alors $E$ est bien décidable (on peut toujours modifier +l'algorithme si nécessaire pour qu'il ne réponde que « vrai » ou +« faux »), et on a $L \subseteq E$ et $M \subseteq \complement E$. + +\textbf{(2)} Si $L,M$ sont décidables disjoints, on peut poser $E = +L$, qui est décidable et vérifie à la fois $L \subseteq E$ +(trivialement) et $M \subseteq \complement E$ (c'est une reformulation +du fait que $M$ est disjoint de $E=L$). + +\textbf{(3)} Comme $L$ est l'ensemble des codes des couples $\langle +e,x\rangle$ tels que $\varphi_e(x) = 1$ et $M$ l'ensemble des codes +des couples $\langle e,x\rangle$ tels que $\varphi_e(x) = 2$, aucun +élément ne peut appartenir aux deux, c'est-à-dire qu'ils sont +disjoints. + +\textbf{(4)} Pour semi-décider si le code d'un couple $\langle +e,x\rangle$ appartient à $L$, il suffit de lancer l'exécution du +programme $e$ sur l'entrée $x$ et, si elle termine en retournant $1$, +renvoyer « vrai », tandis que si elle termine en renvoyant n'importe +quelle autre valeur, faire une boucle infinie (bien sûr, si le +programme $e$ ne termine jamais sur l'entrée $x$, on ne termine pas +non plus). Ceci montre que $L$ est semi-décidable. Le même +raisonnement s'applique pour $M$. + +\textbf{(5)} Supposons par l'absurde qu'il existe un algorithme $g$ +comme annoncé (i.e., qui prend $\langle e,x\rangle$ en entrée, termine +toujours, et renvoie « vrai » si $\langle e,x\rangle\in L$ et « faux » +si $\langle e,x\rangle \in M$). Définissons un nouvel algorithme qui, +donné un entier $e$, effectue les calculs suivants : (1º) interroger +l'algorithme $g$ supposé exister en lui fournissant le code du couple +$\langle e,e\rangle$ comme entrée, et ensuite (2º) si $g$ répond vrai, +renvoyer la valeur $2$, tandis que si $g$ répond n'importe quoi +d'autre, renvoyer la valeur $1$. L'algorithme qui vient d'être décrit +aurait un certain numéro, disons, $c$, et la description de +l'algorithme fait qu'il termine toujours, que la valeur $\varphi_c(e)$ +qu'il renvoie vaut toujours soit $1$ soit $2$, et qu'elle vaut $2$ si +$\langle e,e\rangle \in L$ (c'est-à-dire si $\varphi_e(e) = 1$) et $1$ +si $\langle e,e\rangle \in M$ (c'est-à-dire si $\varphi_e(e) = 2$). +En particulier, en prenant $e=c$, on voit que $\varphi_c(c)$ doit +valoir $1$ ou $2$, doit valoir $2$ si $\varphi_c(c) = 1$ et $1$ si +$\varphi_c(c) = 2$, ce qui est une contradiction. + +\emph{Variante :} La preuve ci-dessus a été rédigée en explicitant +l'argument diagonal. On peut aussi, si on préfère, utiliser le +théorème de récursion de Kleene. L'argument est alors le suivant. +Supposons par l'absurde qu'il existe un algorithme $g$ comme annoncé +(i.e., qui prend $\langle e,x\rangle$ en entrée, termine toujours, et +renvoie « vrai » si $\langle e,x\rangle\in L$ et « faux » si $\langle +e,x\rangle \in M$). Définissons un nouvel algorithme qui, donné un +couple $(e,x)$, effectue les calculs suivants : (1º) interroger +l'algorithme $g$ supposé exister en lui fournissant le code $\langle +e,x\rangle$ comme entrée, et ensuite (2º) si $g$ répond vrai, renvoyer +la valeur $2$, tandis que si $g$ répond n'importe quoi d'autre, +renvoyer la valeur $1$. On obtient ainsi une fonction $h$ calculable +totale $\mathbb{N}^2 \to \{1,2\}$ telle que $h(e,x) = 2$ lorsque +$\langle e,x\rangle\in L$ et $h(e,x) = 1$ lorsque $\langle +e,x\rangle\in M$. Le théorème de récursion de Kleene assure qu'il +existe $e$ tel que $\varphi_e(x) = h(e,x)$ pour tout $x$, et +notamment, quelle que soit $x$ la valeur $\varphi_e(x)$ et définie et +vaut soit $1$ soit $2$, et elle vaut $2$ si $\langle e,x\rangle \in L$ +(c'est-à-dire si $\varphi_e(x) = 1$) et $1$ si $\langle e,x\rangle \in +M$ (c'est-à-dire si $\varphi_e(x) = 2$). Ceci est une contradiction. + +\textbf{(6)} La question (5) montre (compte tenu de la question (1)) +que $L$ et $M$ ne sont pas calculablement séparables, i.e.., sont +calculablement inséparables, tandis que (3) et (4) montrent que +$L$ et $M$ sont disjoints et semi-décidables. On a donc bien montré +l'existence d'ensembles semi-décidables disjoints et calculablement +inséparables. +\end{corrige} + % % |