summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-27 15:09:56 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-27 15:09:56 (GMT)
commit64deabcf51fe764a0787d200512a0e5c59c68140 (patch)
tree4d9842886e1eab8310218cf7c679e280fcfbedb9 /exercices3.tex
parent0d239e7124017215ef9fd52344064b4b7c4f40fa (diff)
downloadinf105-64deabcf51fe764a0787d200512a0e5c59c68140.zip
inf105-64deabcf51fe764a0787d200512a0e5c59c68140.tar.gz
inf105-64deabcf51fe764a0787d200512a0e5c59c68140.tar.bz2
Another exercise on computability (decidable iff range of an increasing computable function).
Diffstat (limited to 'exercices3.tex')
-rw-r--r--exercices3.tex60
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