summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-30 13:42:17 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-30 13:42:17 (GMT)
commitac8bffe7083b4f2a2d3e4a8c66297c1c46da1bf0 (patch)
tree3c5e133507ef1e47fd1836802c3359a3d3d63819 /exercices3.tex
parentb144fa0fb8f49c6a808976a907a91e6c8ab2d53a (diff)
downloadinf105-ac8bffe7083b4f2a2d3e4a8c66297c1c46da1bf0.zip
inf105-ac8bffe7083b4f2a2d3e4a8c66297c1c46da1bf0.tar.gz
inf105-ac8bffe7083b4f2a2d3e4a8c66297c1c46da1bf0.tar.bz2
Clarify statement on busy-beaver function.
Diffstat (limited to 'exercices3.tex')
-rw-r--r--exercices3.tex11
1 files changed, 6 insertions, 5 deletions
diff --git a/exercices3.tex b/exercices3.tex
index 8d5c0ad..c8bee33 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -708,14 +708,15 @@ connaissance de $M$ permet de résoudre le problème de l'arrêt.
Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq
M(k)$ pour tout $k$ n'est calculable. Montrer que même si $M'$
vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est
-pas calculable. Bref, la fonction $M$ croît plus vite que n'importe
-quelle fonction calculable.
+pas calculable.
\emph{Remarque :} La fonction $M$, ou différentes variantes de
celle-ci, s'appelle fonction du « castor affairé ». On peut montrer
-encore plus fort : si $M'(k)\geq M(k)$ pour un nombre infini de
-valeurs de $k$, alors $M'$ n'est pas calculable (Radó, 1962,
-\textit{On Non-Computable Functions}).
+encore plus fort : si $F$ est une fonction calculable quelconque,
+alors il existe $k_0$ tel que $M(k) \geq F(k)$ pour $k\geq k_0$
+(autrement dit, la fonction $M$ finit par dépasser n'importe quelle
+fonction calculable : Radó, 1962, \textit{On Non-Computable
+ Functions}).
\begin{corrige}
Supposons que $M$ soit calculable. On peut alors résoudre le problème