S と Σ が計算不能であることの証明

ウィキペディア小見出し辞書

S(n) と Σ(n) が計算不能であることの証明

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/28 03:01 UTC 版)

「ビジービーバー」の記事における「S(n) と Σ(n) が計算不能であることの証明」の解説

S(n) が計算可能関数であると仮定し、S(n) を求めるチューリングマシンを EvalS と呼ぼう。このマシンは n 個の 1 が印字されたテープから処理を開始して、S(n) 個の 1 をテープ上に生成してから停止するものとする。併せて Clean という名のチューリングマシンを用意し、これはあらかじめテープ上に書かれた 1 をすべて消去するマシンとする。もう一つ Double という名のチューリングマシンを用意し、これは n + n を求めるマシンとする。つまり n 個の 1 が書かれたテープから処理を開始して、2n 個の 1 をテープ上に生成したのち停止する。さて、このような状況で、Double | EvalS | Clean という複合マシンを用意して、このマシンの状態個数を n0 と書く。さらに、 Create_n0 という名のチューリングマシンを用意し、これは空テープに対して n0 個の 1 を印字するものとする。このマシンが n0 個の状態を持つようにするのは容易である（i 状態は 1 を印字し、テープヘッドを右に一つ移動し、状態を i + 1 に切り替える。ただし、n0 に達したならば停止する）。n0 と n0 の和 (n0 + n0) を N と書こう。 ここで今度は BadS という名の複合マシンを用意し、この内容は Create_n0 | Double | EvalS | Clean とする。このマシンは N 状態を持つことに注意する。空テープから処理を開始し、まず n0 個の一連の 1 を印字し次にこれを2倍にして、N 個の一連の 1 を生成する。BadS はそれから S(N) 個の 1 をテープに書き、最後に全ての 1 を消去して停止する。しかしながら、この消去処理は少なくとも S(N) ステップだけ動作するので、BadS の動作時間は S(N) よりも厳密に大きいことになり、これは関数 S(n) の定義と矛盾する。 Σ(n) が計算不能であることも同様にして証明できる。上の証明に出てきた EvalS マシンを EvalΣ マシンに替え、Clean を Increment ―テープ上最初に出てくる 0 を探して順次 1 で置き換える単純なチューリングマシン―で代替すればよい。 S(n) が計算不能であることは、停止問題に帰着して証明することも容易である。S(n) は停止するチューリングマシンが実行可能な最大ステップ数なので、それを越えて走り続けるマシンは決して停止しない。したがって、与えられた任意の n 状態チューリングマシンを S(n) ステップだけ走らせてみて、それがいまだ停止しないなら、それはもはや決して停止しない。以上より、S(n) の値が計算できれば停止問題が解けてしまうことになるが、停止問題が計算不能であることは別途証明されているので、S(n) もまた計算不能であることが従う。