既知の値
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/28 03:01 UTC 版)
Σ(n) と S(n) の正確な値が判明しているのは n < 5 である場合に限られる。5-状態ビジービーバーについては、現時点で知られている優勝候補は 4,098 個の 1 を 47,176,870 ステップで出力するが（Heiner Marxen と Jurgen Buntrock、1989年）、他に約40個の非正則な振る舞いをするチューリングマシンが残されている。これらは停止しないと信じられているが、停止しないことの証明がいまだ得られていない。6-状態ビジービーバーの現時点における候補は 1018267 を超える 1 を 1036534 を超えるステップにて出力する（Pavel Kropitz、2010年）。前述したように、これらのビジービーバーはすべて2-記号チューリングマシンである。 Milton Greenは、1964年の論文 "A Lower Bound on Rado's Sigma Function for Binary Turing Machines" の中で、ある種のマシンの集合を構成し次のことを示した。 Σ ( 2 k + 4 ) = Σ ( 2 ( k + 2 ) ) > 3 ↑ k 3 = hyper ( 3 , k + 2 , 3 ) = 3 ↑ k + 1 2 > A ( k , k ) = 2 ↑ k − 2 ( k + 3 ) − 3 {\displaystyle \Sigma (2k+4)=\Sigma \left(2(k+2)\right)>3\ \uparrow ^{k}3=\operatorname {hyper} (3,k+2,3)=3\ \uparrow ^{k+1}2>A\left(k,k\right)=2\uparrow ^{k-2}\left(k+3\right)-3} ( ↑ {\displaystyle \uparrow } は クヌースの矢印表記 、 hyper {\displaystyle \operatorname {hyper} } は ハイパー演算子 であり、A は アッカーマン関数) すなわち、 Σ ( 2 k ) > hyper ( 3 , k , 3 ) > A ( k − 2 , k − 2 ) = 2 ↑ k − 4 ( k + 1 ) − 3 {\displaystyle \Sigma \left(2k\right)>\operatorname {hyper} (3,k,3)>A\left(k-2,k-2\right)=2\uparrow ^{k-4}\left(k+1\right)-3} 従って、 Σ ( 10 ) > 3 ↑↑↑ 3 = 3 ↑↑ 3 3 3 = 3 3 3 ⋅ ⋅ ⋅ 3 {\displaystyle \Sigma (10)>3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3^{3^{3}}=3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}} (高さは 3 27 = 27 9 = 7 , 625 , 597 , 484 , 987 {\displaystyle 3^{27}={27}^{9}=7,625,597,484,987} )、 先程のΣ(12) は Σ ( 12 ) > 3 ↑↑↑↑ 3 = 3 ↑↑↑ 3 ↑↑↑ 3 = 3 ↑↑↑ 3 ↑↑ 3 3 3 = 3 ↑↑↑ 3 ↑↑ 7 , 625 , 597 , 484 , 987 ≫ 6 ⋅ ( 4096 ↑↑ ) 166 4 ≫ 2 ↑ 4 − 2 ( 4 + 3 ) − 3 = 2 ↑ 2 7 − 3 = 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 − 3 = 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 4 − 3 = 2 2 2 2 2 4 − 3 = 2 2 2 2 16 − 3 = 2 2 2 65536 − 3 {\displaystyle \Sigma (12)>3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow 3\uparrow \uparrow 3^{3^{3}}=3\uparrow \uparrow \uparrow 3\uparrow \uparrow 7,625,597,484,987\gg 6\cdot \left(4096\uparrow \uparrow \right)^{166}4\gg 2\uparrow ^{4-2}\left(4+3\right)-3=2\uparrow ^{2}7-3=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 2-3=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 4-3=2^{2^{2^{2^{2^{4}}}}}-3=2^{2^{2^{2^{16}}}}-3=2^{2^{2^{65536}}}-3} これに対して、現在知られている Σ(6) の限界値は 10 18267 < 3 3 3 3 = 3 ↑↑ 4 {\displaystyle 10^{18267}<3^{3^{3^{3}}}=3\uparrow \uparrow 4} であり、比較上大変小さい。
※この「既知の値」の解説は、「ビジービーバー」の解説の一部です。
「既知の値」を含む「ビジービーバー」の記事については、「ビジービーバー」の概要を参照ください。
- 既知の値のページへのリンク
