From 0829012359e0f07c600a49d0444ab0d4a8300067 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 11 Jan 2024 19:00:56 +0100 Subject: Exercise on the realizability of Plisko's formula. --- exercices-inf110.tex | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 90 insertions(+), 1 deletion(-) 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} + % % -- cgit v1.2.3