diff options
| -rw-r--r-- | exercices3.tex | 60 |
1 files changed, 60 insertions, 0 deletions
diff --git a/exercices3.tex b/exercices3.tex index 9e9a840..2d3d5a5 100644 --- a/exercices3.tex +++ b/exercices3.tex @@ -360,6 +360,66 @@ prouve (1). \exercice +Soit $A \subseteq \mathbb{N}$ un ensemble infini. Montrer qu'il y a +équivalence entre : +\begin{itemize} +\item l'ensemble $A$ est décidable, +\item il existe une fonction calculable \emph{strictement croissante} + $f\colon\mathbb{N}\to\mathbb{N}$ telle que $f(\mathbb{N}) = A$. +\end{itemize} + +\begin{corrige} +Supposons $A$ décidable : on va construire $f$ comme indiqué. Plus +exactement, on va appeler $f(n)$ le $n$-ième élément de $A$ par ordre +croissant (c'est-à-dire que $f(0)$ est le plus petit élément de $A$, +et $f(1)$ le suivant par ordre de taille, et ainsi de suite ; noter +que $A$ est infini donc cette fonction est bien définie). Montrons +que $f$ est calculable : donné un entier $n$, on teste successivement +si $0\in A$ puis $1\in A$ puis $2\in A$ et ainsi de suite, à chaque +fois en utilisant un algorithme décidant $A$ (qui est censé exister +par hypothèse) jusqu'à obtenir $n$ fois la réponse « oui » ; plus +exactement : +\begin{itemize} +\item initialiser $m \leftarrow 0$, +\item pour $k$ allant de $0$ à l'infini, +\begin{itemize} +\item interroger l'algorithme qui décide si $k\in A$, +\item s'il répond « oui » : +\begin{itemize} +\item si $m=n$, terminer et renvoyer $k$, +\item sinon, incrémenter $m$ (c'est-à-dire faire $m \leftarrow m+1$). +\end{itemize} +\end{itemize} +\end{itemize} +La boucle termine car $A$ est infini. + +Réciproquement, supposons $f$ strictement croissante calculable et +posons $A = f(\mathbb{N})$ : on veut montrer que $A$ est décidable. +Or pour décider si $k \in A$, il suffit de calculer successivement +$f(0)$, $f(1)$, $f(2)$ et ainsi de suite, et de terminer si $f(n)$ +atteint ou dépasse le $k$ fixé : s'il l'atteint, on renvoie vrai (on a +trouvé $n$ tel que $f(n)=k$), sinon, on renvoie faux (la valeur $k$ a +été sautée par la fonction $f$ et ne sera donc jamais atteinte). +L'algorithme est donc explicitement : +\begin{itemize} +\item pour $n$ allant de $0$ à l'infini, +\begin{itemize} +\item calculer $f(n)$, +\item si $f(n) = k$, renvoyer vrai, +\item si $f(n) > k$, renvoyer faux. +\end{itemize} +\end{itemize} +La boucle termine car toute fonction strictement croissante +$\mathbb{N}\to\mathbb{N}$ est de limite $+\infty$ en l'infini (donc +$f(n)$ finit forcément par atteindre ou dépasser $k$). +\end{corrige} + +% +% +% + +\exercice + 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 |