前提
チューリングマシンとはなにか、という説明は省きます。
チューリングマシン
次のようなチューリングマシン$M$を考えます。
$M=<Q, \Sigma, \delta, q_{1}, q_{f}>$
- $Q= \{q_{1}, q_{2}, \ldots, q_{n}, q_{f}\}$：状態（状態数は$n+1$）
- $\Sigma = \{0, 1\}$：記号
- $\delta$：動作関数（後で定義します）
- 動作関数は、$\delta=($遷移前の状態$, $ 遷移前に参照している記号$)=($遷移後の状態$, $ 遷移前に書き込まれる記号$, $ テープヘッドの移動方向$)$
の５つ組の対応関係を与える。
- 動作関数は、$\delta=($遷移前の状態$, $ 遷移前に参照している記号$)=($遷移後の状態$, $ 遷移前に書き込まれる記号$, $ テープヘッドの移動方向$)$
- $q_{1}$：初期状態
- $q_{f}$：受理状態
- 初め、テープは$0$で埋められている。
つまり、$n$状態と、それに付け加えて「停止」状態の$q_{f}$という特殊な状態を持ち、２つの記号を持つチューリングマシンを考えます。
「停止」状態に達したときは、マシンは即座に停止し、テープ上の「$1$」の個数を出力するものとします。
このチューリングマシンは、
- 状態数$n$
- 動作関数
を定めることで１つに定まります1。
逆に言えば、状態数$n$を定めても、動作関数を定めないと全く違うチューリングマシンになることがわかるでしょう。
例えば、動作関数によっては停止するもの、しないものが存在します。
$n$を定めたときの異なるチューリングマシンの個数
さて、ここで、$n$を定めたときの動作関数の個数を考えましょう。
動作関数は、冒頭で示した５つ組の組み合わせの個数だけ存在します。
- 遷移前の状態：$n$個（$q_{f}$からは遷移しない）
- 遷移前に参照している記号：$2$種類（$0, 1$）
- 遷移後の状態：$n+1$個（自身に遷移する可能性も、$q_{f}$に遷移する可能性もある）
- 遷移後に書き込まれる記号：$2$種類（$0, 1$）
- テープヘッドの移動方向：$2$通り（$L, R$）
ちょっと$n=2$の場合を見てみましょう。
ここから、$($状態、参照中の記号$)=(q_{1}, 0), (q_{1}, 1), (q_{2}, 0), (q_{2}, 1)$のそれぞれの状況から伸びる矢印（動作関数）を定めます。
このとき、それぞれの矢印の終点の選び方は、
- 遷移先の状態：$q_{1}, q_{2}, q_{f}$の$3$通り
- 書き換え後の記号：$0, 1$の$2$通り
- テープヘッドの移動方向：$L, R$の$2$通り
なので、${(3\cdot 2\cdot 2)}^{2\cdot 2}=20736$通り（！）の矢印の引き方があるわけです。
つまり、ある状況から、動作関数の定め方によって$2\cdot 2\cdot (n+1)$種類の動作があり、この動作関数の設定を、遷移前の状況分の$2n$回だけしなければいけないので、状態数が$n$のチューリングマシンは、$(4(n+1))^{2n}$通りだけ存在することがわかります2。
これは想像以上に多くて、$n=1$のときでも$64$、$n=3$の時点で1600万種類以上あります。てか状態数$1$のマシンってそんないっぱいあるんか……
ビジービーバー・ゲーム
さて、これらのチューリングマシンを用いて、以下の問題（ゲーム）を考えます。
$n$状態のチューリングマシンで、有限のステップで停止するもののうち、出力した数が最大のマシン（このマシンを「ビジービーバー」と呼ぶ）を求めよ。
これがビジービーバー・ゲーム（ビジービーバー問題）です。
そんなもん、チューリングマシンの個数が有限なんだから、全探索してやればいいじゃないか、と思われるかもしれません。これは、実はある意味では正しいです。それがとんでもなく難しいってだけです。
ここで、いくつかの文字を定義しましょう。
- $T_{n}$：$n$状態のチューリングマシンの集合
- $E_{n}$：$T_{n}$に属するマシンのうち、有限時間で停止するマシンの集合
- $\Sigma(n)$：$n$状態の「ビジービーバー」の出力、つまり$n$状態のチューリングマシンが出力できる最大の数（当然、これを与えるマシンは$E_{n}$に属する）
- $S(n)$：$E_{n}$に属するマシンのシフト回数で、最大のもの（停止するまでの動作関数の最多呼び出し回数=最大ステップ数、つまりこれより多く動作したマシンは停止しない）
- $S(n)$を与えるマシンがビジービーバーとは限らない
このときの、$\Sigma(n)$をビジービーバー関数、$S(n)$を最大シフト数関数と呼びます。
ちなみに、$E_{n}\ne\varnothing$、すなわち$\Sigma(n), S(n)$がすべての$n$において定義できることは証明可能です。
このうち、$E_{n}$か$S(n)$のどちらかが求まれば、$\Sigma(n)$を求めることは容易です。
$E_{n}$に属するすべてのマシンをシミュレーションしたり、$T_{n}$のすべてのマシンに対して最大$S(n)$ステップの動作を行って、停止したものの集合を$E_{n}$と考えたりすればいいからです。
じゃあ、何がそんなに難しいのかというと、チューリングマシンが停止するか否かを判定することです。
停止性問題
1936年、停止性問題はアラン・チューリングによって否定的に解決されました。
すごくざっくり言うと、「任意のチューリングマシンが停止するか否かを判定する、『万能な』停止性判定アルゴリズムは存在しない」という結論が得られたのです。
ここで注意しなければいけないのは、この文のとらえ方です。
「停止しないチューリングマシンは、どうあがいても停止しないと判定できない」わけではありません。
「あるアルゴリズムでは、最低でも１つのチューリングマシンが停止するかどうかわからない」が正しいのです。
あるアルゴリズムでは、あるチューリングマシンが無限に停止しないことを示すこともできます。例えば、ある決定性チューリングマシンの状態、テープの様相、テープヘッドの位置が同じ状況になった場合、無限ループに陥って永久に停止しないことは容易に示せるでしょう。
つまり、各々の$n$について、$(4(n+1))^{2n}$通りのチューリングマシンを調べて、停止するものはその出力を求め、しないものはしないと証明ができれば、ビジービーバーも、その出力も求まります。
現在のところ、ビジービーバー問題はn=4まで（追記：$n=5$の値が出たっぽい？）は解けています。
計算不能関数
$\Sigma(n), S(n)$は、どちらも計算不能関数です。
$f$が計算不能関数であるとは、どのような計算可能関数$g$に対しても、$g(n)<f(n)$なる$n$が存在する、ということです（数式じゃ表せない）。
これは、値が求まらない関数、というわけではありません。
増加が著しく速く、どのような「値を求めるアルゴリズムが存在する関数」$g$でも上から抑えられない、という意味でしかありません。
つまり、$\Sigma(n), S(n)$には値を求めるアルゴリズムが存在しないというだけです。
まとめ
ビジービーバー問題の何が難しいのかというと、
- 調べるべきチューリングマシンの個数が、なかなかに多いこと
- チューリングマシンが停止するかどうかを判定する一般的なアルゴリズムがないこと
- 実行ステップ数、出力される記号長が著しく大きいこと（チューリングマシンの個数の比ではない）
- 上に示した３つの性質が、予想ではなく証明された事実だということ
です。
ビジービーバー関数は、通常の数式で表すことができません（確定）。
今後の人類の活躍に期待しましょう。
コメント