Exercise on computable inseparability.

(Taken from INF105 test from 2018-02-06, slightly rewritten.)

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}
+
 
 %
 %