Exercise on the realizability of Plisko's formula.

1 files changed, 90 insertions, 1 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index 9e32802..93f7afe 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -3008,7 +3008,7 @@ sémantique des ouverts) elle ne peut pas être démontrable.
 
 \section{Divers}
 
-\exercice\ (${\star}{\star}{\star}{\star}{\star}$)\par\nobreak
+\exercice\label{exercise-dragon-riddle}\ (${\star}{\star}{\star}{\star}{\star}$)\par\nobreak
 
 Vous êtes dans un donjon.  Devant vous se trouvent trois portes,
 étiquetées $A,B,C$.  Derrière l'une de ces trois portes, mais vous ne
@@ -3108,6 +3108,95 @@ trois termine et renvoie une étiquette dans $\{A,B,C\}$, et, quand ça
 se produit, ouvrir la porte en question.
 \end{corrige}
 
+%
+
+\exercice\ (${\star}{\star}{\star}{\star}{\star}$)\par\nobreak
+
+On considère la formule propositionnelle suivante (due à V. Plisko) :
+\[
+\begin{aligned}
+&\Big((\neg\neg A \Leftrightarrow \neg B\land \neg C)
+\land (\neg\neg B \Leftrightarrow \neg C\land \neg A)
+\land (\neg\neg C \Leftrightarrow \neg A\land \neg B)
+\\
+& \quad \land \big((\neg A \Rightarrow (\neg B\lor \neg C)) \Rightarrow (\neg B\lor \neg C)\big) \\
+& \quad \land \big((\neg B \Rightarrow (\neg C\lor \neg A)) \Rightarrow (\neg C\lor \neg A)\big) \\
+& \quad \land \big((\neg C \Rightarrow (\neg A\lor \neg B)) \Rightarrow (\neg A\lor \neg B)\big) \Big) \\
+\Rightarrow\;& \big(\neg A \lor \neg B \lor \neg C\big)
+\end{aligned}
+\]
+(on notera la symétrie entre $A,B,C$ qui rend la formule moins
+complexe qu'elle n'en a l'air).
+
+Déduire de l'exercice \ref{exercise-dragon-riddle} que cette formule
+est réalisable mais (d'après la question subsidiaire de cet exercice)
+pas Medvedev-valide.
+
+(\emph{Indication :} comme $A,B,C$ n'apparaissent qu'avec une négation
+partout dans cette formule, leur contenu n'a pas d'importance, la
+seule chose qui importe est qu'ils aient ou non des éléments — ou dans
+le cas des problèmes finis, des solutions ; il s'agit alors de
+reconnaître que la formule reflète exactement les termes de l'énigme.)
+
+\begin{corrige}
+Rappelons que, pour la réalisabilité propositionnelle, $\dottedneg P$
+vaut $\mathbb{N}$ lorsque $P$ est vide, et $\varnothing$ lorsque $P$
+n'est pas vide (et symétriquement, $\dottedneg\dottedneg P$ vaut
+$\varnothing$ lorsque $P$ est vide, et $\mathbb{N}$ lorsque $P$ n'est
+pas vide).
+
+Montrons que la formule est réalisable : pour ça, on va chercher à en
+produire un réalisateur $r$ (qui doit être le même quelles que soient
+$A,B,C \subseteq \mathbb{N}$).  Ce réalisateur est un programme
+prenant six entrées.  Les trois premiers sont des réalisateurs de
+$(\dottedneg\dottedneg A \dottedlimp \dottedneg B\dottedland
+\dottedneg C)$ et symétriquement, et ne nous intéresseront pas pour
+leurs valeurs, ce sont simplement des promesses que si $A$ est
+non-vide alors $B$ et $C$ sont vides et symétriquement : on retient
+simplement de ces trois entrées la garantie qu'exactement une des
+trois parties $A,B,C$ est non-vide (« a un dragon »).  On va appeler
+$p_A,p_B,p_C$ les trois autres entrées (quitte à les modifier un tout
+petit peu comme on va l'expliquer).  Par exemple, $p_A$ doit réaliser
+$((\dottedneg A \dottedlimp (\dottedneg B\dottedlor \dottedneg C))
+\dottedlimp (\dottedneg B\dottedlor \dottedneg C)$, c'est-à-dire que
+si on lui passe en argument un réalisateur $q$ de $\dottedneg A
+\dottedlimp (\dottedneg B\dottedlor \dottedneg C)$ il doit terminer et
+renvoyer un réalisateur de $\dottedneg B\dottedlor \dottedneg C$ ; or
+un réalisateur de $\dottedneg B\dottedlor \dottedneg C$ est la donnée
+d'un élément de $\dottedneg B$ ou de $\dottedneg C$ ainsi que
+l'information duquel on a pris : mais cela revient simplement à donner
+l'étiquette d'un des deux ensembles $B$ ou $C$ qui est vide (« n'a pas
+de dragon »).  Donc la contrainte sur $q$ est que si $A$ est vide il
+renvoie l'étiquette d'un des deux ensembles $B$ ou $C$ qui est vide
+(et si $A$ n'est pas vide, n'y a aucune contrainte sur $q$) ; et la
+contrainte sur $p_A$ est que si on lui passe un tel $q$, il renvoie
+lui-même l'étiquette d'un des deux ensembles $B$ ou $C$ qui est vide.
+Et au final, notre programme $r$ doit renvoyer l'étiquette d'un des
+trois ensembles $A,B,C$ qui est vide.
+
+Ce sont donc exactement les termes de l'énigme de
+l'exercice \ref{exercise-dragon-riddle} : le réalisateur $r$ recherché
+pour la formule est le programme qui prend $p_A,p_B,p_C$ comme on l'a
+dit, qui effectue le calcul décrit dans la solution
+de \ref{exercise-dragon-riddle}, et renvoie l'étiquette qu'il a
+trouvé.  La formule de Plisko est bien réalisable.
+
+Néanmoins, cette formule n'est pas Medvedev-valide : en effet,
+appelons $A,B,C$ trois problèmes finis ayant chacun un candidat et
+dont un seul a une solution (« un dragon »).  Le problème décrit par
+l'ensemble de la formule consiste toujours à trouver une solution de
+l'énigme mais cette fois en interprétant les programmes comme des
+tableaux finis (fonctions entre ensembles finis).  Or on a expliqué
+dans la question subsidiaire de
+l'exercice \ref{exercise-dragon-riddle} que l'énigme n'avait pas de
+solution dans ces conditions : c'est dire que la formule n'est pas
+Medvedev-valide.
+
+(Notamment, la formule de Plisko n'est pas démontrable en calcul
+propositionnel intuitionniste, par \emph{correction} de la sémantique
+de Medvedev.)
+\end{corrige}
+
 
 %
 %