diff options
Diffstat (limited to 'exercices3.tex')
| -rw-r--r-- | exercices3.tex | 71 |
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. |