Exercise on looping Turing machines.

1 files changed, 71 insertions, 0 deletions

diff --git a/exercices-inf110.tex b/exercices-inf110.tex
index 6a91072..76130f0 100644
--- a/exercices-inf110.tex
+++ b/exercices-inf110.tex
@@ -661,6 +661,77 @@ essentiellement identique.)
 
 %
 
+\exercice\ (${\star}$)
+
+On rappelle que le mot « configuration », dans le contexte de
+l'exécution d'une machine de Turing, désigne la donnée de l'état
+interne de la machine, de la position de la tête de lecture, et de la
+totalité de la bande.  (Et la « configuration vierge » est la
+configuration où l'état est $1$, la tête est à la position $0$, et la
+bande est entièrement remplie de $0$.)
+
+On considère l'ensemble $\mathscr{F}$ des machines de Turing $M$ dont
+l'exécution, à partir de la configuration vierge $C_0$, conduit à un
+nombre fini de configurations distinctes (i.e., si on appelle
+$C^{(n)}$ la configuration atteinte au bout de $n$ étapes d'exécution
+en démarrant sur $C_0$, on demande que l'ensemble $\{C^{(n)} : n\in
+\mathbb{N}\}$ soit fini).
+
+\textbf{(1)} Montrer que $\mathscr{F}$ est semi-décidable.
+(\emph{Indication :} on pourra commencer par remarquer, en le
+justifiant, que « passer par un nombre fini de configurations
+distinctes » équivaut à « terminer ou revenir à une configuration déjà
+atteinte ».)
+
+\textbf{(2)} Montrer que $\mathscr{F}$ n'est pas décidable.
+(\emph{Indication :} si on savait décider $\mathscr{F}$ on saurait
+décider le problème de l'arrêt.)
+
+\begin{corrige}
+\textbf{(1)} Commençons par remarquer que « passer par un nombre fini
+de configurations distinctes » équivaut à « terminer ou revenir à une
+configuration déjà atteinte ».  En effet, dans un sens, si l'exécution
+termine (i.e., termine en temps fini), il est évident qu'elle n'a
+parcouru qu'un nombre fini de configurations distinctes ; mais si elle
+revient à une configuration déjà atteinte, la machine boucle
+indéfiniment à partir de cet état puisque l'exécution est déterministe
+(la configuration contient toute l'information nécessaire à
+l'exécution de la machine $M$) : si $C^{(i)} = C^{(j)}$ avec $i<j$
+alors $C^{(i+k)} = C^{(j+k)}$ pour tout $k$, et donc toute
+configuration atteinte est une de $C^{(0)}, \ldots, C^{(j)}$) Dans
+l'autre sens, si la machine ne passe que par un nombre fini de
+configurations distinctes et ne s'arrête pas, par le principe des
+tiroirs, il y aura forcément une configuration atteinte plusieurs
+fois, c'est-à-dire $C^{(i)} = C^{(j)}$ avec $i<j$.  Ceci montre
+l'équivalence affirmée.
+
+Pour semi-décider $\mathscr{F}$, il suffit de lancer l'exécution à
+partir de $C_0$, en enregistrant chaque configuration atteinte (on
+rappelle qu'une configuration est une donnée finie puisqu'il n'y a, à
+un instant donné, qu'un nombre fini de $1$ sur la bande), et la
+comparer à toutes les configurations précédemment atteintes.  Si on
+repasse dans une configuration déjà atteinte, on termine et répond
+« oui », sinon on continue l'exécution.  D'après ce qui vient d'être
+dit, ceci semi-décide $\mathscr{F}$.
+
+\textbf{(2)} Supposons par l'absurde qu'on soit capable de décider
+$\mathscr{F}$ et montrons que ceci permettrait de décider le problème
+de l'arrêt à partir de la configuration vierge (dont on a vu en cours
+qu'il est indécidable).  En effet, donné $M$, on commence par tester
+(grâce à notre hypothèse) si $M \in \mathscr{F}$ : si ce n'est pas le
+cas, on sait déjà que $M$ ne terminera pas et on répond « non » ; si
+c'est le cas, on sait que l'exécution de $M$ à partir de la
+configuration vierge conduira soit à l'arrêt soit à retomber sur une
+configuration déjà atteinte : il suffit de simuler cette exécution en
+enregistrant chaque configuration atteinte, et, si on tombe sur une
+configuration déjà atteinte on répond « non », tandis que si on
+s'arrête on répond « oui ».  Cet algorithme termine toujours et décide
+le problème de l'arrêt, ce qui est impossible : c'est donc que
+$\mathscr{F}$ n'était pas décidable.
+\end{corrige}
+
+%
+
 \exercice\ (${\star}{\star}$)
 
 Soit $f \colon\mathbb{N} \to \mathbb{N}$ une fonction calculable par