| ビジービーバー関数 | |
|---|---|
| 型 | 計算不可能
|
ビジービーバー関数(busy beaver function)またはラドのシグマ関数(Radó's sigma function)は、計算可能性理論に於ける計算不能な関数である。
概要[]
ビジービーバー関数は \( \Sigma( n ) \) あるいは \( \mathrm{BB} ( n ) \) と書かれ、 n-状態 2-記号チューリングマシンを使い、空のテープから処理を開始して、停止するまでにテープに出力できる最も多くの 1 の数である[1][2]。
このような数を出力するチューリング機械をビジービーバーと言う。
ラドは、この関数はいかなる計算可能関数よりも急速に増大することを示し、この関数が有限時間内に計算不能である、すなわち、あるチューリングマシンがビジービーバーであるかどうかを知るためには、無限の計算時間が必要となるということを示した。すなわち、有限の計算ステップで任意の \(n\) に対して \(\Sigma(n)\) の計算が終了するようなアルゴリズムは存在しない、ということである。ラドのシグマ関数は、古典的な巨大数論の基本であった再帰関数の限界を定義している。
ビジービーバー関数の概念が導入された巨大数として、ふぃっしゅ数バージョン4がある。
値と近似式[]
正確な値が知られているのは \(\Sigma(n)\) の内 \(n\leq4\) の場合のみである。ここで \(G\) はグラハム数であり、\(\Sigma(18)\) はグラハム数より遥かに大きい。
| \(n\) | \(\Sigma(n)\) |
|---|---|
| 1 | \(= 1\) |
| 2 | \(= 4\) [3] |
| 3 | \(= 6\) [3] |
| 4 | \(= 13\) [3] |
| 5 | \(\geq 4098\) [3] |
| 6 | \(\geq 10\uparrow\uparrow15\) [3] |
| 7 | \(> 10^{10^{10^{10^{18705352}}}}\) [3][4] |
| 8 | \(\gg 3\uparrow\uparrow3 = 3^{3^{3}} = 7625597484987\) |
| 9 | \(\gg 10\uparrow\uparrow28\) |
| 10 | \(\gg 3\uparrow\uparrow\uparrow3\) |
| 11 | \(\gg 3\uparrow\uparrow\uparrow720618962331271\) |
| 12 | \(\gg 6\times(4096\uparrow\uparrow)^{166}4\) |
| 14 | \(\gg 3\uparrow\uparrow\uparrow\uparrow\uparrow3\) |
| 15 | \(\gg f_{\omega}(2046)\) |
| 16 | \(\gg f_{\omega}^2(5)\) |
| 17 | \(\gg f_{\omega+1}(10)\) |
| 18 | \(\gg f_{\omega+1}(7\times10^{57}) > G\) |
| 19 | \(\gg f_{\omega+1}^3(9)\) |
| 20 | \(\gg f_{\omega+1}^4(7\times10^{57})\) |
| 21 | \(\gg f_{\omega+2}(f_{\omega+1}^2(4))\) |
| 22 | \(\gg f_{\omega+2}^3(f_{\omega+1}(4))\) |
| 38 | \(\gg f_{\omega2}(167)\) |
| 64 | \(\gg f_{\omega^2}(4098)\) |
| 85 | \(\gg f_{\varepsilon_0}(1907)\) |
なお、\(k\geq2\) とした場合において、非常に大雑把な大小関係となるが、下限を得られる式が知られている。ここで \(\text{hyper}\) はハイパー演算子、\(\uparrow\) は矢印表記、\(A\) はアッカーマン関数である。[5]
\(\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)\) も値が分からないだろうと予想されている[6]。
出典[]
- ↑ Busy Beaver -- from Wolfram MathWorld
- ↑ Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.
- ↑ 3.0 3.1 3.2 3.3 3.4 3.5 Michel, Pascal. The Busy Beaver Competitions. Retrieved 2023-04-15.
- ↑ \(\Sigma(7)>\Sigma(6)\)より\(\Sigma(7)>10\uparrow\uparrow15\)であることが\(\Sigma(6)\)の下界よりわかるが、7状態で特別にそれより大きくなるようなものは知られていない。
- ↑ 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.
- ↑ Aaronson, Scott. "The Busy Beaver Frontier." ACM SIGACT News 51.3 (2020): 32–54.
参考サイト[]
- このサイトの英語版 - Rado's sigma function
- Wikipedia 日本語版 - ビジービーバー