Σの計算不能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/28 03:01 UTC 版)
ラドーは続けて、Σ を押さえ込むような計算可能関数は存在しないことを証明した。つまり、全ての計算可能関数 f について、f(n) < Σ(n) を満たす、何らかの n が存在する（証明は後述。実は無限個の n があることを示せる）。特に、Σ自身は計算不能である。 加えてこのことは、与えられた候補がビジービーバーであるかを判定する一般的なアルゴリズムが存在しないことを意味する。なぜなら、もしそのようなアルゴリズムがあれば、全ての候補マシンを並べてテストするだけで Σ の値を容易に決定できてしまうからである。 入力として n を受け取り Σ(n) を計算するような単一のアルゴリズム A は存在しない（Σは計算不能なので）ものの、n までの全ての自然数について Σ(n) を「計算」するようなアルゴリズム An は存在する（計算可能関数#例を参照のこと）。さらに、n が十分に小さいならば、ビジービーバー関数の特殊値を実用的に計算することもできる。例えば、Σ(0) = 0, Σ(1) = 1 を示すのは難しくないし、次第に困難にはなるが、Σ(2) = 4 と Σ(3) = 6 と Σ(4) = 13 (オンライン整数列大辞典の数列 A028444) を示すこともできる。n > 4 についての Σ(n) は未算出だが、4098 と 10 18267 {\displaystyle 10^{18267}} いう下限値がそれぞれ n = 5 と n = 6 について得られている。n = 12 については、Dewdney[1984] は次のいささか大きな下限を紹介している： Σ ( 12 ) ≥ 6 ⋅ 4096 4096 4096 . . . 4096 4 = 6 ⋅ ( 4096 ↑↑ ) 166 4 > 4096 ↑↑ 166 {\displaystyle \Sigma (12)\ \ \geq \ \ 6\ \cdot \ 4096^{4096^{4096^{~.~^{~.~^{~.~^{4096^{4}}}}}}}=6\cdot \left(4096\uparrow \uparrow \right)^{166}4>4096\uparrow \uparrow 166} ここで指数の塔には 4096 が 166 回出現し、指数の塔の頂上に 4 が乗る。
※この「Σの計算不能性」の解説は、「ビジービーバー」の解説の一部です。
「Σの計算不能性」を含む「ビジービーバー」の記事については、「ビジービーバー」の概要を参照ください。
- Σの計算不能性のページへのリンク
