La séance précédente j'ai parlé de jeux en forme normale et je crois que j'ai été assez mauvais (confus), par contre, cette semaine j'espère m'en être mieux tiré sur les jeux de Gale-Stewart.
https://twitter.com/gro_tsen/status/1359521918668468224
Un jeu de Gale-Stewart est défini par un ensemble X≠∅ et une partie A⊆X^ℕ: Alice choisit x₀∈X (sans contrainte) puis Bob choisit x₁ (idem) puis Alice choisit x₂, etc., et au bout d'un nombre infini de coups, si la suite formée appartient à A alors Alice gagne, sinon Bob.
La question est: un des joueurs a-t-il forcément une stratégie gagnante? En général la réponse est négative, mais si on fait l'hypothèse que A est ouvert ou bien fermé («détermination ouverte») elle l'est, ou même si A est borélien («détermination borélienne»).
Le théorème de détermination borélienne est assez fascinant, mais dépasse le niveau de mon cours. Ceux qui veulent en lire une preuve pas trop ardue peuvent se référer à la thèse de master de Ross Bryant, itservices.cas.unt.edu/~rdb0003/thesi… “Borel determinacy and metamathematics” (§1) …
… ainsi que les notes de @wtgowers qui commencent ici sur son blog: gowers.wordpress.com/2013/08/23/det…
Dans cette séance, j'ai juste démontré le théorème de détermination ouverte et énoncé celui de détermination borélienne. Ce sont des résultats qui sont à mon avis trop peu connus en-dehors des logiciens, et trop peu enseignés, surtout au niveau où je me place.
Les vidéos sont là: 1re partie peertube.r2.enst.fr/videos/watch/6… et 2e partie peertube.r2.enst.fr/videos/watch/d… (1h30 chacune), et les notes de la séance: perso.telecom-paristech.fr/madore/mitro20…
• • •
Missing some Tweet in this thread? You can try to
force a refresh
