summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-27 14:54:17 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-27 14:54:17 (GMT)
commit0d239e7124017215ef9fd52344064b4b7c4f40fa (patch)
treeaa24411a0036761246d33dbdc473a1fdbeff2480 /exercices3.tex
parent7544d7953f8da049710844c96156401978062b74 (diff)
downloadinf105-0d239e7124017215ef9fd52344064b4b7c4f40fa.zip
inf105-0d239e7124017215ef9fd52344064b4b7c4f40fa.tar.gz
inf105-0d239e7124017215ef9fd52344064b4b7c4f40fa.tar.bz2
Another exercice on decidability.
Diffstat (limited to 'exercices3.tex')
-rw-r--r--exercices3.tex71
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.