巨大数研究 Wiki
Advertisement
巨大数研究 Wiki
ビジービーバー関数
計算不可能


ビジービーバー関数またはラドのシグマ関数は、計算可能性理論に於ける計算不能な関数である。

概要

ビジービーバー関数は \( \Sigma( n ) \) あるいは \( \mathrm{BB} ( n ) \) と書かれ、 n-状態 2-記号チューリングマシンを使い、空のテープから処理を開始して、停止するまでにテープに出力できる最も多くの 1 の数である[1][2]。数学の専門家が作った関数の中では、最も増加速度が速い関数の1つである。巨大数論では、この関数を越える重要な関数は数えるほどしかない。そのような関数は、例えばラヨ関数クサイ関数である。またふぃっしゅ数バージョン4はビジービーバー関数の概念が導入された巨大数である。

このような数を出力するチューリング機械をビジービーバーと言う。

ラドは、この関数はいかなる計算可能関数よりも急速に増大することを示し、この関数が有限時間内に計算不能である、すなわち、あるチューリングマシンがビジービーバーであるかどうかを知るためには、無限の計算時間が必要となるということを示した。すなわち、有限の計算ステップで任意の \(n\) に対して \(\Sigma(n)\) の計算が終了するようなアルゴリズムは存在しない、ということである。ラドのシグマ関数は、古典的な巨大数論の基本であった再帰関数の限界を定義している。

値と近似式

正確な値が知られているのは \(\Sigma(n)\) の内 \(n\leq4\) の場合のみである。ここで \(G\) はグラハム数であり、\(\Sigma(18)\) はグラハム数より遥かに大きい。

\(\begin{align*} \Sigma(1) &= 1 \\ \Sigma(2) &= 4 \\ \Sigma(3) &= 6 \\ \Sigma(4) &= 13 \\ \Sigma(5) &\geq 4098 \\ \Sigma(6) &\geq \frac{25\times4^{30341}+23}{9} \approx 3.514 \cdot 10^{18267} \\ \Sigma(7) &> 10^{10^{10^{10^{18705352}}}} \\ \Sigma(8) &\gg 3\uparrow\uparrow3 = 3^{3^{3}} = 7625597484987 \\ \Sigma(10) &\gg 3\uparrow\uparrow\uparrow3 \\ \Sigma(12) &\gg 6\times(4096\uparrow\uparrow)^{166}4 \\ \Sigma(14) &\gg 3\uparrow\uparrow\uparrow\uparrow\uparrow3 \\ \Sigma(15) &\gg f_{\omega}(2046) \\ \Sigma(16) &\gg f_{\omega}^2(5) \\ \Sigma(17) &\gg f_{\omega+1}(10) \\ \Sigma(18) &\gg f_{\omega+1}(7\times10^{57}) > G \\ \Sigma(19) &\gg f_{\omega+1}^3(9)\ \\ \Sigma(20) &\gg f_{\omega+1}^4(7\times10^{57}) \\ \Sigma(21) &\gg f_{\omega+2}(f_{\omega+1}^2(4)) \\ \Sigma(22) &\gg f_{\omega+2}^3(f_{\omega+1}(4))  \\ \Sigma(38) &\gg f_{\omega2}(167) \\ \Sigma(64) &\gg f_{\omega^2}(4098) \\ \Sigma(85) &\gg f_{\varepsilon_0}(1907) \\ \end{align*}\)

なお、\(k\geq2\) とした場合において、非常に大雑把な大小関係となるが、下限を得られる式が知られている。ここで \(\text{hyper}\) はハイパー演算子、\(\uparrow\) は矢印表記、\(A\) はアッカーマン関数である。[3]

\(\Sigma(2k)\gg\text{hyper}(3,k-2,3)=3\uparrow^{k-2}3>A(k-2,k-2)\)

テープの状態変化

下に \( n = 2, 3, 4 \) のビジービーバーと \( n = 5 \) のビジービーバー候補の挙動を示す。横軸はテープの状態で、縦軸は時間軸、上から下に向かって進み、一番下で停止し、一番下の段の黒の数がビジービーバー関数の出力に当たる。

証明不能性

\(\mathsf{ZFC}\) の健全性を仮定すれば \(\mathrm{BB}(n)\) の値がわからないような \(n\) が存在する (但しここでは \(\mathrm{BB}(n)\) を最大シフト関数とする)。もっと一般に 任意の再帰的可算かつ \(\Sigma_2\)-健全な理論 \(T\) に対して、ある \(n_T\in\mathbb{N}\) が存在して任意の \(n\geq n_T\) 、 \(k\in\mathbb{N}\) に対して \(\mathrm{BB}(\overline{n})=\overline{k}\) が証明できないようなものが存在する。ここで \(\overline{n}\) は自然数 \(n\) に対応する数項を表す。特に \(\mathrm{ZFC}\) の健全性の仮定のもとで \(\mathrm{BB}(748)\) は \(\mathrm{ZFC}\) で値が分からないことが証明されている。また \(\mathrm{BB}(20)\) も値が分からないだろうと予想されている[4]

出典

  1. Busy Beaver -- from Wolfram MathWorld
  2. Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.
  3. Milton W. Green. (1964) "A lower bound on Rado's sigma function for binary Turing machines." 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design. 91–94.
  4. Aaronson, Scott. "The Busy Beaver Frontier." ACM SIGACT News 51.3 (2020): 32–54.

参考サイト

Advertisement