ビジービーバー関数


ビジービーバー関数
型	計算不可能
急増加関数	\(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^{18276} \\ \Sigma(7) &\ge& 10^{10^{10^{10^{18705353}}}} \\ \Sigma(10) &\ge& 3 \uparrow^{3} 3 \\ \Sigma(12) &\ge& 3 \uparrow^{4} 3 \\ \Sigma(14) &\ge& 3 \uparrow^{5} 3 \\ \Sigma(16) &\ge& 3 \uparrow^{6} 3 \\ \Sigma(18) &\ge& 2 \uparrow^{2046} 4 \\ \Sigma(19) &\ge& 2 \uparrow^{1.75 \cdot 10^{18276}} 4 \\ \Sigma(21) &\ge& f_{\omega+1}(8) \\ \Sigma(23) &\ge& f_{\omega+1}^2(9) &\gg& G& \end{eqnarray}