summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-03-07 11:27:11 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-03-07 11:27:11 (GMT)
commit5b4c945a004b75181008c9a91f7684d1e09fc479 (patch)
tree0379884249024f52c2e0997075b70aed947500d9 /notes-mitro206.tex
parent29d20620ab74ca332afc4efa778718fd1e39f4a8 (diff)
downloadmitro206-5b4c945a004b75181008c9a91f7684d1e09fc479.zip
mitro206-5b4c945a004b75181008c9a91f7684d1e09fc479.tar.gz
mitro206-5b4c945a004b75181008c9a91f7684d1e09fc479.tar.bz2
The halting game (Turing against Blanche).
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex48
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}