diff options
author | David A. Madore <david+git@madore.org> | 2023-10-19 15:32:40 +0200 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2023-10-19 15:32:40 +0200 |
commit | 817c07aea534f05fccf5980b25a5d86967b108f9 (patch) | |
tree | 70804c26d55ec818075231d9d47be4a0584a06dd | |
parent | 8b97ddfad15877e32f0abc1cf5789260376c5d12 (diff) | |
download | inf110-lfi-817c07aea534f05fccf5980b25a5d86967b108f9.tar.gz inf110-lfi-817c07aea534f05fccf5980b25a5d86967b108f9.tar.bz2 inf110-lfi-817c07aea534f05fccf5980b25a5d86967b108f9.zip |
Busy beaver function.
-rw-r--r-- | transp-inf110-01-calc.tex | 95 |
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} |