From 64deabcf51fe764a0787d200512a0e5c59c68140 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 27 Jan 2017 16:09:56 +0100
Subject: Another exercise on computability (decidable iff range of an
 increasing computable function).

---
 exercices3.tex | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)

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
-- 
cgit v1.2.3