The halting game (Turing against Blanche).

1 files changed, 48 insertions, 0 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 9abce3f..a6f6d30 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -874,6 +874,54 @@ chiffres binaires d'un réel commençant par $0.$, de $[0,1]$ : si cet
 n'est jamais nulle).  \emph{Il n'est pas vrai} qu'un des deux joueurs
 possède forcément une stratégie gagnante.
 
+\thingy Considérons le jeu suivant : Turing choisit publiquement une
+machine de Turing (i.e., un programme sur ordinateur) et Blanche (son
+adversaire) doit répondre soit « elle termine en $n$ étapes » où $n$
+est un entier naturel (explicite), soit « elle ne termine pas ».  Dans
+le premier cas, on lance l'exécution de la machine de Turing sur $n$
+étapes, et si elle termine bien dans le temps annoncé, Blanche a
+gagné, sinon c'est Turing qui a gagné.  Dans le second cas (i.e., si
+Blanche a annoncé « elle ne termine pas »), c'est à Turing d'annoncer
+soit « si, elle termine en $m$ étapes » où $m$ est un entier naturel
+(explicite), soit « en effet, elle ne termine pas ».  Dans le premier
+sous-cas, on lance l'exécution de la machine de Turing sur $m$ étapes,
+et si elle termine bien dans le temps annoncé, Turing a gagné, sinon
+c'est Blanche qui a gagné.  Dans le second sous-cas (i.e., si Turing a
+confirmé « en effet, elle ne termine pas »), Blanche a gagné.
+
+Dit de façon plus simple : Turing propose à Blanche de décider l'arrêt
+d'une machine de Turing ; si Blanche prédit l'arrêt, elle doit donner
+le nombre d'étapes et on peut vérifier cette affirmation ; si elle
+prédit le contraire, c'est à Turing de la contredire le cas échéant
+par une affirmation d'arrêt, qui sera elle aussi vérifiée.
+
+La règle du jeu peut être implémentée algorithmiquement : i.e., on
+peut vérifier (sur une machine de Turing !) qui gagne ou qui perd en
+fonction des coups joués (puisque à chaque fois on fait des
+vérifications finies).  Néanmoins, aucun des joueurs n'a de stratégie
+gagnante \emph{algorithmique} (i.e., choisissant un coup
+algorithmiquement en fonction des coups antérieurs).  En fait, Turing
+n'a pas de stratégie gagnante du tout (quelle que soit la machine
+qu'il choisit au premier coup, Blanche \emph{pourrait} répondre
+correctement auquel cas Turing ne gagne pas).  Mais Blanche n'a pas de
+stratégie gagnante algorithmique, car cela reviendrait à résoudre le
+problème de l'arrêt.
+
+Cet exemple illustre le fait qu'on ne peut pas espérer avoir un
+algorithme qui calcule un coup gagnant dans n'importe quel jeu même si
+on se limite aux jeux dont le gain est calculable algorithmiquement.
+
+(On peut remplacer le problème de l'arrêt par n'importe quel problème
+semi-décidable : si $f \colon \mathbb{N} \to \mathbb{N}$ est une
+fonction algorithmiquement calculable dont l'image n'est pas
+décidable, Turing choisit un élément $y$ de $\mathbb{N}$, Blanche doit
+soit répondre « $y=f(n)$ » pour un $n$ explicite soit « $y$ n'est pas
+  dans l'image », auquel cas Turing peut soit rétorquer « si, $y =
+  f(m)$ » soit concéder que $y$ n'est pas dans l'image.  Autre
+exemple : Turing choisit un énoncé mathématique, Blanche doit soit le
+démontrer soit dire que ce n'est pas un théorème, et dans le second
+cas c'est à Turing de le démontrer.)
+
 
 \subsection{Remarques}