diff options
| -rw-r--r-- | notes-mitro206.tex | 48 |
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} |