FANDOM


ビジービーバー関数
計算不可能
急増加関数 \(f_{\omega_1^\text{CK}}(n)\)

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

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

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

\begin{eqnarray} \Sigma(1) &=& 1 \\ \Sigma(2) &=& 4 \\ \Sigma(3) &=& 6 \\ \Sigma(4) &=& 13 \\ \Sigma(5) &\geq& 4098 \\ \Sigma(6) &\geq& 3.514 \cdot 10^{18267} \\ \Sigma(7) &>& 10^{10^{10^{10^{18705352}}}} \\ \Sigma(10) &\gg& 3 \uparrow^{3} 3 \\ \Sigma(12) &\gg& 3 \uparrow^{4} 3 \\ \Sigma(14) &\gg& 3 \uparrow^{5} 3 \\ \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\cdot10^{57}) > G \\ \Sigma(19) &\gg& f_{\omega+1}^3(9)\ \\ \Sigma(20) &\gg& f_{\omega+1}^4(7\cdot10^{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{eqnarray}

テープの偏移編集

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



出典 編集

  1. Busy Beaver -- from Wolfram MathWorld
  2. Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.

参考サイト 編集

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki