diff options
-rw-r--r-- | exercices-inf110.tex | 71 |
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 |