Busy beaver function.

1 files changed, 65 insertions, 0 deletions

diff --git a/exercices3.tex b/exercices3.tex
index 4964c05..f9e4917 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -287,6 +287,71 @@ L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui
 prouve (1).
 \end{corrige}
 
+%
+%
+%
+
+\exercice
+
+Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième algorithme
+(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.
+
+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
+e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils
+terminent.
+
+Montrer que la fonction $M$ n'est pas calculable (i.e., n'est pas
+calculable par un algorithme) : on pourra pour cela montrer que la
+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.
+
+\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}).
+
+\begin{corrige}
+Supposons que $M$ soit calculable.  On peut alors résoudre le problème
+de l'arrêt de la manière suivante : donné un algorithme $T$, de
+numéro $e$, et une entrée $n$ à fournir à cet algorithme, pour savoir
+si $T$ s'arrête, on calcule $M(k)$ où $k = \max(e,n)$, on exécute
+ensuite l'algorithme $T$ pendant au plus $M(k)$ étapes : s'il termine
+dans le temps imparti, on répond vrai (il a terminé), sinon, on répond
+faux (il ne terminera jamais).  Cette résolution du problème de
+l'arrêt est correcte, car si $T$ termine sur l'entrée $n$, il prendra
+par définition $S(e,n)$ étapes, avec $0\leq e\leq k$ et $0\leq n\leq
+k$ par définition de $k$, donc $S(e,n) \leq M(k)$ par définition de
+$M(k)$ : ceci signifie précisément que si $T$ n'a pas terminé en
+$M(k)$ étapes, il ne terminera jamais.
+
+Exactement le même argument montre que $M'$ n'est pas calculable sous
+l'hypothèse que $M'(k) \geq M(k)$ pour tout $k$ : s'il l'était, on
+pourrait exécuter l'algorithme $T$ pendant au plus $M'(k)$ étapes, et
+comme on a $S(e,n) \leq M(k) \leq M'(k)$, la même démonstration
+convient.
+
+Enfin, si on suppose seulement $M'(k)\geq M(k)$ pour $k\geq k_0$, la
+fonction $M'$ n'est toujours pas calculable : en effet, si on suppose
+par l'absurde qu'elle l'est, la fonction $M''$ qui à $k$ associe
+$M'(k)$ si $k\geq k_0$ et $M(k)$ sinon, serait encore calculable
+puisqu'elle ne diffère de $M'$ qu'en un nombre fini de valeurs, or
+changer la valeur en un point d'une fonction calculable donne toujours
+une fonction calculable (même si on « ne connaît pas » la valeur à
+changer, elle existe, donc l'algorithme modifié existe).  Mais d'après
+le paragraphe précédent, $M''$ n'est pas calculable puisqu'elle est
+partout supérieure ou égale à $M$.
+\end{corrige}
+
 
 %
 %