Répondre

Yassine · 25-05-2016 20:55:01

Bon, ça n'a pas l'air d'inspirer grand monde !
Sniff...

Yassine · 24-05-2016 08:57:23

Pour appuyer mon propos initial concernant mon incompréhension de l'explication sur le savoir mutuel récursif, je donne une interprétation différente du problème :

Je considère une zone contaminée et je suppose qu'on a des robots qui nettoient la zone. Chacun des robot dispose de plusieurs capteurs. Un premier capteur lui permettant de connaitre le nombre total de robots, et les autres lui permettent de savoir si les autres robots fonctionnent correctement. Pour des raisons de fiabilité, on ne dote pas le robot d'un capteur lui permettant un auto-diagnostic (la panne pourrait toucher le capteur lui même). On dote également le robot d'une commande lui donnant l'ordre de quitter la zone (cette opération prend un certain temps, qu'on appellera par la suite 'jour'). Le robot peut héberger un programme Python avec les verbes suivants : NombreTotalRobots(t), MarcheAutreRobot(numRobot), SeRetirer(t).
La question est : Peut-on concevoir un programme qui fera se retirer les robots défectueux, et uniquement eux ?

Pour moi, la réponse est 'non' en toute généralité et 'oui' si on sait qu'il y a au moins un robot défectueux. Dans ce cas, c'est le programme qui exécute l'axiome que j'ai appelé 'Canard boiteux' : "Si au bout de n jours, je vois toujours tous les robots et que je n'en compte que n défectueux, je me retire".

Avec cette interprétation, on se débarrasse de l’ambiguïté qui plaçait les villageois à la fois dans la position de robots et dans la position du concepteur du programme.

Pour revenir à ma tentative d'explication, la théorie, ce sont l'ensemble des programme que je peux écrire pour les robots, et le modèle est une zone contaminée particulière.

Yassine · 23-05-2016 22:27:25

Bonjour à tous,
Je repost après une longue période d'absence.

J'ai eu une une discussion récente avec un collègue sur une vielle énigme postée dans la rubrique "Enigmes" par Barbichu (lien). La discussion portait sur une variante de ce problème : on suppose maintenant que le chef n'annonce pas qu'il existe au moins un cocu. Alors, même après 22 jours, il ne se passera rien (la récurrence ne peut pas démarrer). Après 100 jours (ou 103 si on veut ;-) ), le tyran dit à tous "ah au fait, on m'a rapporté qu'il y a au moins un cocu parmi vous". 22 jours plus tard, les premiers assassinats sont publiés.
Le "paradoxe" est que le deuxième discours ne semble apporter aucune information (chacun des villageois savait qu'il y avait au moins 21 cocus) !
Mon collègue m'a expliqué que le prof qui a écrit le livre où ce sujet était traité, donnait comme explication que le deuxième discours apportait, un savoir "mutuellement récursif" : je sais, je sais que tu sais, tu sais que je sais, je sais que tu sais que je sais, ...

Je ne suis pas entièrement convaincu par cette explication. Mais comme le gars qui l'a donné est prof de math à l'X, je pense que je me trompe. Mon argument est le suivant : Ce truc du savoir "mutuellement récursif" était déjà présent avant le deuxième discours. Chacun savait qu'il y avait soit 21, soit 22 cocus. Il savait également que les autres devaient connaitre soit 21 soit 22 cocus et que donc il savaient qu'il y en avait au moins 1, et ainsi de suite.
J'ai essayé sans succès d'adopter une approche avec la théorie des modèles (je suis débutant sur ce sujet). Mon idée est la suivante : formaliser le problème avec des prédicats du premier ordre. Montrer qu'avec ce langage et un set d'axiomes bien choisis, on peut construire une théorie qui puisse montrer : "s'il existe au moins un cocu et que la première publication a lieu le jour j, alors il y a j cocus". La "connaissance commune" des villageois seraient donc matérialisée par les théorèmes démontrables dans cette théorie. Le deuxième discours permet donc juste de dire que les villageois sont dans un modèle (au sens de la théorie des modèles) dans lequel il peuvent utiliser le théorème dont j'ai parlé.
Pour les spécialiste, ça peut paraître confus, je m'en excuse d'avance.

Voila ce que j'ai tenté :

Dans mon langage, je définis les prédicats suivants :
[tex]C(x)[/tex] : [tex]x[/tex] est cocu
[tex]S(x,y)[/tex] : [tex]x[/tex] voit que [tex]y[/tex] est cocu
[tex]D(t,x)[/tex] : à l'instant [tex]t[/tex], [tex]x[/tex] "découvre" qu'il est cocu
[tex]P(t,x)[/tex] : à l'instant [tex]t[/tex], il est publié dans le journal que [tex]x[/tex] a tué sa femme.

Je définie également les expressions suivantes :
[tex]|e|[/tex] cardinal de l'ensemble [tex]e[/tex]
[tex]\alpha:=|{\{z | C(z)\}}|[/tex] cardinal de l'ensemble des cocus
[tex]v(x) := \{z | S(x,z)\}[/tex] ensemble des cocus que voit [tex]x[/tex]
[tex]\tau := \inf\{n\ |\ \exists x \ P(n,x)\}[/tex] instant de la première publication

Par convention, [tex]\tau = +\infty[/tex] s'il n'y a aucune publication.

Je définis ensuite les axiomes de ma théorie :
[tex]\begin{align}
& \exists x\ \neg C(x) & \textrm{ Il y en a au moins un non cocu} \\
& \forall x\ \neg S(x,x) & \textrm{ Aucun cocu ne voit qu'il l'est} \\
& \forall x\ C(x) \implies \left(\forall y \ S(y,x) \vee x=y\right) & \textrm{ ça se voit} \\
& \forall x\ \forall y\ \ S(x,y) \implies C(y) & \textrm{ pas cocu, pas vu} \\
& \forall x\ \forall n D(n,x) \implies C(x) & \textrm{ on ne découvre pas le faux} \\
& \forall x\ \forall n D(n,x) \Leftrightarrow P(n+1,x) & \textrm{ la découverte entraîne le meurtre et la publication} \\
& \forall x\ \neg P(0,x) & \textrm{ Rien n'est publié le premier jour} \\
& \forall x\ \forall n \left(\exists y\ C(y) \wedge \tau > n \wedge |v(x)|=n\right) \implies D(n,x) & \textrm{Canard boiteux}
\end{align}[/tex]

Mon dernier axiome est un peu boiteux. J'ai essayé de le limiter au seul cas zéro (si je ne voit aucun cocu et que je sais qu'il y en a au moins un, alors c'est moi), mais ça ne m'a pas permis de montrer la récurrence. Du coup, il est trop fort est ne fait pas vraiment partie des données du problème. Je ne fais que cacher le problème sous le tapis.

Est-ce que quelqu'un a un avis éclairé sur mes tentatives ?
Est-ce voué à l'échec (nécessite les prédicats du deuxième ordre) ?

En tout cas, tout conseil est le bienvenu. A vous lire.

Cordialement

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Pied de page des forums