Busy beaver function.

1 files changed, 95 insertions, 0 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 93d2a11..ce5467f 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -1999,6 +1999,101 @@ jour ».
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Le castor affairé}
+
+\itempoint La fonction \textbf{castor affairé} associe à $m$ le nombre
+maximal $B(m)$ d'étapes d'exécution d'une machine de Turing à $\leq m$
+états \alert{qui termine} (à partir d'une bande vierge : $\beta = 0$).
+
+\medskip
+
+\itempoint La fonction $B$ croît \alert{trop vite pour être
+  calculable} :
+\[
+\forall f\colon\mathbb{N}\to\mathbb{N}\text{~calculable}.\quad
+\exists m\in\mathbb{N}.\quad
+(B(m) > f(m))
+\]
+
+\medskip
+
+{\footnotesize
+
+\underline{Preuve :} supposons au contraire $\forall m\in\mathbb{N}.\;
+(B(m) \leq f(m))$ avec $f\colon\mathbb{N}\to\mathbb{N}$ calculable.
+Donnée une machine de Turing $M$ et une configuration initiale $C$, on
+peut alors algorithmiquement décider si $M$ s'arrête à partir de $C$ :
+\begin{itemize}
+\item fabriquer une machine $M^*$ qui réalise $C$ à partir de la
+  configuration vierge $C_0$, puis fait ce que fait $M$
+  \textcolor{teal}{($\leftarrow$ théorème s-m-n ici)},
+  donc $M^*$ termine sur $C_0$ ssi $M$ termine sur $C$,
+\item calculer $f(m)$ où $m$ est le nombre d'états de $M^*$,
+\item exécuter $M^*$ à partir de $C_0$ pendant $f(m)$ étapes (ce
+  nombre est $\geq B(m)$ par hypothèse),
+\item si elle a terminé, $M^*$ termine sur $C_0$, donc $M$ sur $C$, et
+  on renvoie « oui » ; sinon, elle ne termine jamais par définition de
+  $B(m)$, on renvoie « non ».
+\end{itemize}
+Ceci est impossible donc $f$ n'est pas calculable.\qed
+
+\par}
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Le castor affairé (amélioration)}
+
+{\footnotesize $B(m)=$ nombre maximal d'étapes d'exécution d'une
+  machine de Turing à $\leq m$ états \alert{qui termine} à partir
+  d'une bande vierge.\par}
+
+\medskip
+
+\itempoint On peut faire mieux : $B$ \alert{domine} toute fonction
+calculable :
+\[
+\forall f\colon\mathbb{N}\to\mathbb{N}\text{~calculable}.\quad
+\exists m_0\in\mathbb{N}.\quad
+\forall m\geq m_0.\quad
+(B(m) > f(m))
+\]
+
+\medskip
+
+{\footnotesize
+
+\underline{Preuve :} soit $f\colon\mathbb{N}\to\mathbb{N}$ calculable.
+Soit $\gamma(r) = A(2,2,r)$ (en fait, $2^r$ doit suffire ; noter
+$\gamma$ croissante).  On considère la machine de Turing $M_r$ qui
+\begin{itemize}
+\item calcule $\gamma(r+1)$ puis $f(0) + f(1) + \cdots +
+  f(\gamma(r+1)) + 1$,
+\item attend ce nombre-là d'étapes, et termine.
+\end{itemize}
+Par le théorème s-m-n, le nombre d'états de $M_r$ est une fonction
+p.r. $b(r)$ de $r$ (même $b(r) = r + \mathrm{const}$ convient).  Pour
+$r\geq r_0$ on a $b(r) \leq \gamma(r)$.  Soit $m_0 = \gamma(r_0)$.  Si
+$m \geq m_0$, soit $r\geq r_0$ tel que $\gamma(r) \leq m \leq
+\gamma(r+1)$.  Alors $M_r$ calcule $\cdots+f(m)+\cdots+1$, donc attend
+$>f(m)$ étapes.  Donc $B(b(r)) > f(m)$.  Mais $b(r) \leq \gamma(r)
+\leq m$ donc $B(m) > f(m)$.\qed
+
+\par}
+
+\medskip
+
+\centerline{*}
+
+\medskip
+
+\itempoint Variations du castor affairé : nombre de symboles écrits
+sur la bande, $n \mapsto \max\{\varphi_e(e) : 0\leq e\leq
+n\text{~et~}\varphi_e(e)\downarrow\}$ (mêmes propriétés).
+
+\end{frame}
+%
 \section{Décidabilité et semi-décidabilité}
 \begin{frame}
 \frametitle{Terminologie calculable/décidable}