ビジービーバーが計算不可能であることの証明

前提

以下に出てくるチューリングマシンが扱う文字集合は$ \{0,1,X\}のみとする

状態の名前のみが異なり、状態遷移図が同じチューリングマシン同士は同一視する

準備

集合$ B_n

「状態数が$ n以下で、空列を入力して動作開始するといつかは停止するチューリングマシン」をすべて集めた集合

$ B_nは、$ B_{n-1}を包含することがわかるmrsekut.icon

この定義から、各$ nについて、$ B_nは空でないことがわかる

関数$ \mathrm{beaver}(n)

$ B_nの要素(チューリングマシン)の中で、空列を入力して動作開始して停止した時に、

最も多くの文字をテープに書き残しているものが、書き残した文字の個数

ただし、beaver(0) = 0とする

各$ nについて、$ B_nは空でないので、

beaver(n)の値は確定している

つまり、beaverは全域関数

また、$ m\le n\Rightarrow \mathrm{beaver}(m)\le \mathrm{beaver}(n)①

証明

beaverが計算可能であると仮定して矛盾を導く

仮定などから、beaverを計算するチューリングマシン$ Qが存在する

また、$ Qの存在とは無関係に、2つのチューリングマシン$ P_n,Rが存在する

$ P_n

空入力で動作開始すると、$ n個の連続した1を書いて、

ヘッドを左端の1に置いて停止するチューリングマシン

状態数は、$ n+1

$ R　

自然数の2進数表記を入力して動作開始すると、

その自然数の値に1を足した個数の連続した$ Xを出力して停止するチューリングマシン

状態数を、$ rとする

この時、$ Qが存在する仮定して、その状態数を$ qとし、$ q,rに対して$ nを十分大きく取ると

$ n+1+q+r\le 2^n-1とすることができる②

このような$ nを使って、$ P_n,Q,Rが連続に動作するように結合したチューリングマシンを$ Mとする

上の議論により、$ Mの状態数は$ n+1+q+rである

$ Mを空入力で動作開始すると次のように動く

テープに$ n個の1を書く

$ P_nにより。

これは$ 2^n-1の2進数表記なので、次に$ \mathrm{beaver}(2^n-1)を計算してその答えをテープに2進数で書き込む

$ Qにより。

$ \mathrm{beaver}(2^n-1)+1の個数だけ、$ Xを書いて停止する

$ Rにより。

$ Mの状態数は$ n+1+q+rだが、これだけの状態数のチューリングマシンが、空入力で動作開始して$ \mathrm{beaver}(2^n-1)+q個の$ Xをテープに書き残して停止するのは矛盾である

なぜならbeaverの定義により、状態数$ n+1+q+rの機械が書き残す文字数は$ \mathrm{beaver}(n+1+q+r)以下のはずだが、

①②より、$ \mathrm{beaver}(n+1+q+r)\lt \mathrm{beaver}(2^n-1)+1だから

つまり、$ Mは少なくとも、$ 2^n-1個の状態数が無いとおかしいが、ソレ以下になっている

故に、ビジービーバーは計算不可能である

参考