Another exercice on decidability.

1 files changed, 69 insertions, 2 deletions

diff --git a/exercices3.tex b/exercices3.tex
index f9e4917..9e9a840 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -94,6 +94,73 @@ Git: \input{vcline.tex}
 
 \exercice
 
+(1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  L'ensemble $L
+= \{u^k : u\in\Sigma^*, k\geq 2\}$ des mots qui sont une puissance
+$k$-ième pour un $k\geq 2$ est-il décidable ?  Semi-décidable ?
+
+(2) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
+programme (ou, si on préfère, de la $e$-ième machine de Turing),
+exécuté sur l'entrée $42$, termine en au plus $10^{1000+e}$ étapes
+est-il décidable ?  Semi-décidable ?
+
+(3) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
+programme (ou, si on préfère, de la $e$-ième machine de Turing),
+exécuté sur l'entrée $42$, termine en temps fini est-il décidable ?
+Semi-décidable ?  (On pourra montrer qu'on peut y ramener le problème
+de l'arrêt.)
+
+\begin{corrige}
+(1) Si $w = u^k$ pour un certain $u\neq\varepsilon$, alors
+  nécessairement $k\leq |w|$ puisque $|w|=k\cdot|u|$.  On dispose donc
+  de l'algorithme suivant pour décider si $w\in L$ : si
+  $w=\varepsilon$, retourner vrai immédiatement ; sinon, pour $k$
+  allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$
+  facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour
+  $0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$
+  commençant à la position $\ell i$) : s'ils sont tous égaux, renvoyer
+  vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne,
+  renvoyer faux.  Le langage proposé est donc décidable (et \textit{a
+    fortiori} semi-décidable).
+
+(2) Donné un $e \in \mathbb{N}$, la fonction $10^{1000+e}$ est
+  évidemment calculable.  On peut ensuite lancer l'exécution du
+  $e$-ième programme, sur l'entrée $42$, pour au plus ce nombre
+  d'étapes (en utilisant la machine universelle, c'est-à-dire, par
+  exemple, en simulant la $e$-ième machine de Turing sur une machine
+  de Turing).  Si l'exécution termine en le temps imparti, on renvoie
+  vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé
+  est bien décidable (et \textit{a fortiori} semi-décidable).
+
+(3) L'ensemble $A$ proposé est « presque » le problème de l'arrêt.  La
+  différence est que le problème de l'arrêt est l'ensemble des couples
+  $(e,n)$ tels que le $e$-ième programme termine sur l'entrée $n$
+  alors qu'ici on a fixé l'entrée à $42$.  Il s'agit donc de montrer
+  que cette limitation ne rend pas pour autant calculable l'ensemble
+  considéré.  Or donnés deux entiers $(e,n)$, on peut fabriquer un
+  programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette
+  valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus
+  un tel $e'$ se calcule algorithmiquement à partir de $e$ et $n$.
+  L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle
+  autre entrée) se comporte donc comme l'exécution du programme $e$
+  sur l'entrée $n$, et notamment, termine si et seulement si elle
+  termine.  Autrement dit, $e'$ appartient à l'ensemble $A$ considéré
+  dans cette question si et seulement si $(e,n)$ appartient au
+  problème de l'arrêt.  Comme on vient de dire qu'on peut calculer
+  $e'$ algorithmiquement à partir de $(e,n)$, si l'ensemble $A$ était
+  décidable, le problème de l'arrêt le serait, ce qui n'est pas le
+  cas.  Donc $A$ n'est pas décidable.  En revanche, $A$ est
+  semi-décidable : il suffit de lancer l'exécution du programme $e$
+  sur l'entrée $42$ et renvoyer vrai si ele termine (si elle ne
+  termine pas, on ne termine pas).
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
 Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  On s'intéresse à
 des langages sur $\Sigma$.
 
@@ -293,7 +360,7 @@ prouve (1).
 
 \exercice
 
-Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième algorithme
+Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième programme
 (ou, si on préfère, de la $e$-ième machine de Turing) quand on lui
 fournit le nombre $n$ en entrée, à supposer que cette exécution
 termine ; sinon, $S(e,n)$ n'est pas défini.
@@ -301,7 +368,7 @@ termine ; sinon, $S(e,n)$ n'est pas défini.
 Soit par ailleurs $M(k)$ le maximum des $S(e,n)$ pour $0\leq e\leq k$
 et $0\leq n\leq k$ qui soient définis (et $0$ si aucun d'eux n'est
 défini).  Autrement dit, il s'agit du plus petit entier supérieur ou
-égal au nombre d'étapes de l'exécution de l'un des algorithmes $0\leq
+égal au nombre d'étapes de l'exécution de l'un des programmes $0\leq
 e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils
 terminent.