ビジービーバー Σ の計算不能性

ウィキペディア

ビジービーバー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/07 05:45 UTC 版)

Σ の計算不能性

ラドーは続けて、Σ を押さえ込むような計算可能関数は存在しないことを証明した。つまり、任意の計算可能関数 f に対して、f(n) < Σ(n) を満たすような n が存在することを証明した。

Σを押さえ込む計算可能関数は存在しないことから、特に Σ 自身が計算不能であることがわかる。これは、与えられた候補がビジービーバーであるかを判定する一般的なアルゴリズムが存在しないことを意味する。なぜなら、もしそのようなアルゴリズムがあれば、全ての候補マシンを並べてテストするだけで Σ の値を容易に決定できてしまうからである。

入力として n を受け取り Σ(n) を計算するような単一のアルゴリズム A は存在しないものの、n までの全ての自然数について Σ(n) を「計算」するようなアルゴリズム A_n は、Σ(n) が決定可能である限り存在する（計算可能関数#例を参照のこと）。さらに、n が十分に小さいならば、ビジービーバー関数の特殊値を実用的に計算することもできる。例えば、Σ(0) = 0, Σ(1) = 1 を示すのは難しくないし、次第に困難にはなるが、Σ(2) = 4 と Σ(3) = 6 と Σ(4) = 13 (オンライン整数列大辞典の数列 A028444) を示すこともできる。n > 4 についての Σ(n) は未算出だが、4098 と $10^{18267}$ いう下限値がそれぞれ n = 5 と n = 6 について得られている。n = 12 については、Dewdney[1984] は次のいささか大きな下限を紹介している：

$\Sigma (12)\ \ \geq \ \ 6\ \cdot \ 4096^{4096^{4096^{~.~^{~.~^{~.~^{4096^{4}}}}}}}=6\cdot \left(4096\uparrow \right)^{166}4>4096\uparrow \uparrow 166$

ここで指数の塔には 4096 が 166 回出現し、指数の塔の頂上に 4 が乗る。