第 6 回線形加速定理、階層定理

本日の内容

6-1. 線形加速定理
6-2. 階層定理
6-3. 領域計算量
6-4. 宿題
6-5. 次週の予告

6-1. 線形加速定理

線形加速定理は、一ステップに処理する情報量を何倍にもして計算速度を速くするというものです。ここでは与えられた Turing 機械 $M$ を $\frac{c}{6}$ 倍速く計算する Turing 機械 $M'$ を作ることを考えます。以下、そのような Turing 機械の構成を示しますが、簡単のため 1 テープ Turing 機械の構成のみを示します。

新しく作る Turing 機械 $M'$ では $M$ の $c$ ステップの計算を 6 ステップで行うようにします。そのためにまず必要なのは、テープの一マスに書き込める記号の数を、 $M$ の $c$ 乗とし、 $M$ のテープ $c$ マス分の情報を 1 マスに書けるようにします。これを以下大きいマスと呼ぶことにします。

さて、テープをこのように $c$ マス分を 1 マス分に書くようにしておいて、 $M$ の $c$ ステップを 6 ステップでシミュレートすることを考えます。 6 ステップの内訳は、最初の 4 ステップで現在のヘッドの位置の両隣の大きなマスの内容を収集して、次の 2 ステップで $c$ ステップ分の大きなマスの内容の変化を書き込みます。

$c$ マス分のテープの内容が 1 マスに書かれていますが、このうちもともと $M$ のヘッドがどこを読んでいたかは $c$ 個のラベル(状態)で記憶しておきます。さて、 $c$ ステップ後にテープはどのようになっているかを考えます。高々 $c$ マスしか動かないので、現在のヘッドの位置から左右に $c$ マスが最大の移動距離になります。しかし、 $c$ マス分を 1 マスに書いた時、シミュレートしている $M$ のヘッドは最大でも隣の $c$ マスの中までしか到達しません(図1)。またヘッドが動く経路を考えると両隣のマスに $c$ ステップ内に訪れることはできず、現在の大きな 1 マスとどちらかの隣の大きな 1 マスだけを訪れることができます(図2)。

図1

図2

そこで、両隣の大きなマスの内容を収集し、 $c$ ステップシミュレーションをすると、中央のマスの内容とどちらか隣の大きなマスの内容が書き変わることになります。

ところで、両隣の大きな 3 マス分のテープの内容をあらかじめあらゆる状況を想定しておけます。そして、それを読んで $c$ ステップ $M$ の内容をシミュレートするのもあらかじめやっておくことができます。つまり、 ( $M$ のヘッドの位置)と(大きな 3 マス分のテープ内容) から ( $M$ を $c$ ステップシミュレートした結果の状態、ヘッド位置、テープ内容) はあらかじめ関数として計算できるわけで、 $M'$ はこれをδ関数として取り込むことができます。つまり、このシミュレーション自体は 1 step で可能なわけです。

結局まとめると $M$ の $c$ ステップは次の 6 ステップでシミュレーションできます。

現在のヘッド位置の $c$ マス分を読む。ヘッドを左へ
左側の $c$ マス分を読む。ヘッドを右へ
ヘッドを右へ
右側の $c$ マスを読み、 $M$ の $c$ ステップ後の状況を計算する。ヘッドを左へ
$c$ ステップ後に書かれるべき現在のヘッド位置の内容を $c$ マス分書き込む。 $M$ のシミュレーションの状況により、ヘッドを右または左またはそのままに
$c$ ステップ後に書かれるべき隣のヘッド位置の内容を $c$ マス分書き込む。 $M$ のシミュレーションの状況により、ヘッドをもとに戻すかまたはそのままに

なお、加速定理と呼ばれるものもあります (証明は難しいけど、実用上意味がないので割愛します)。以下のように、いくらでも加速できる(つまり最適なアルゴリズムの存在しない)関数が存在すると言うものです。

加速定理

次の条件を満たす計算可能関数 $f (x)$ が存在します。

どんな増加関数 $g (n)$ に対しても、有限の場合を除き、 $g (| x |)$ ステップ以内に $f (x)$ を計算する Turing 機械が構成できる。

6-2. 階層定理

ここでは計算時間をかけないと解けない問題が存在することを示します。はじめにこれに必要な補題をまとめます。

補題6-1-a

時間計算量 $f (n)$ の任意の Turing 機械のコードを $O ({f (n)}^{2})$ でシミュレートする万能 1 テープ Turing 機械が存在する。

これは万能 Turing 機械の構成で証明の概略を説明しました。さらに 2 テープ Turing 機械では、次が言えました。

補題6-1-b

時間計算量 $f (n)$ の任意の Turing 機械のコードを $O (f (n) log f (n))$ でシミュレートする万能 2 テープ Turing 機械が存在する。

さらに同じ関数を計算するプログラムが無限に存在するという次の補題を使用します。

補題6-2-a

一つの計算可能な関数に対して、それを計算する Turing 機械は無限個存在する。

これはプログラムの先頭などに、何もしない動作を埋め込むことで簡単に示すことができます。一方、次の補題は参考文献において階層定理を証明するのに使われています。

補題6-2-b

計算可能な関数を Turing 機械で実現するとき、有限の場合を除いて任意の長さのコードを作ることができる。

この補題に関しては、参考文献では Turing 機械のコードの頭に 0 を埋め込むことをゆるすことで示しています。しかしこれを許すか許さないかはコンピュータのモデル化やコード化に依存しそうです。但し、こちらを認めた方が良い結果が得られます。

関数のオーダーとして $O$ の表記を使用してきました。が、ここでは付け加えて $o$ の表記を定義します。 $f (n) = o (g (n))$ は、 $f$ の増え方は $g$ よりも真に少ないことを意味し、ある意味 $f < g$ のような意味を持ちます。この記号の厳密な定義は次の通りです。

「どのような定数 $c > 0$ に対してもある数 $N_{0}$ が存在し、全ての $N_{0}$ より大きい数 $n$ に対して $f (n) \leq c g (n)$ が成り立つ」。なお、これは一階述語論理式では次のように書けます。

(\forall c > 0) (\exists N_{0}) (\forall n \geq N_{0}) [f (n) \leq c g (n)]

なお、 $f (n) = o (g (n))$ と $g (n) \neq O (f (n))$ は同値ではありません。

f (n) = n

g (n) = {\begin{matrix} n^{2} & if n is even \\ 0 & o.w. \end{matrix}

とすると、

g (n) \neq O (f (n))

となりますが、

f (n) \neq o (g (n))

です。

これらの補題を組み合わせることで次の階層定理が主張できます。

6-1-a, 6-2-a を使ったもの

$T_{1} (n)$ が時間構成可能関数だと仮定する。また ${T_{2} (n)}^{2} = o (T_{1} (n))$ とする。その時、どんな時間計算量 $T_{2} (n)$ の Turing 機械にも計算できない、時間計算量 $T_{1} (n)$ で計算できる関数 $f (x)$ が存在する。

6-1-a, 6-2-b を使ったもの

$T_{1} (n)$ が時間構成可能関数だと仮定する。また $T_{1} (n) \neq O ({T_{2} (n)}^{2})$ とする。その時、どんな時間計算量 $T_{2} (n)$ の Turing 機械にも計算できない、時間計算量 $T_{1} (n)$ で計算できる関数 $f (x)$ が存在する。

6-1-b, 6-2-a を使ったもの

$T_{1} (n)$ が時間構成可能関数だと仮定する。また $T_{2} (n) log T_{2} (n) = o (T_{1} (n))$ とする。その時、どんな時間計算量 $T_{2} (n)$ の Turing 機械にも計算できない、時間計算量 $T_{1} (n)$ で計算できる関数 $f (x)$ が存在する。

6-1-b, 6-2-b を使ったもの

$T_{1} (n)$ が時間構成可能関数だと仮定する。また $T_{1} (n) \neq O (T_{2} (n) log T_{2} (n))$ とする。その時、どんな時間計算量 $T_{2} (n)$ の Turing 機械にも計算できない、時間計算量 $T_{1} (n)$ で計算できる関数 $f (x)$ が存在する。

ここでは 6-1-b, 6-2-a を使用したものに対して証明することにします。

註: この $f (n)$ が時間構成可能とは、与えられた $n$ に対して、 $f (n)$ step ちょうどで停止する Turing 機械を構成できると言うことです。通常の増加関数はほぼ可能です。

証明

関数 $f$ は入力 $x$ に対して次の処理をします。

万能 Turing 機械に $x$ と $x$ を入力として与え、コード $x$ の Turing 機械に $x$ を入力したものをシミュレートします。
これを $T_{1} (| x |)$ ステップシミュレートします。
その結果 1 を出力した場合は $f (x)$ の値を 0 とします。それ以外の場合は(計算が終らず途中で打ち切った時も含め) $f (x)$ の値を 1 とします。

この関数を計算するのに $T_{1} (| x |)$ ステップかかるのは明らかです。一方、 $f (x)$ が $T_{2} (| x |)$ ステップで計算できないことを示します。 $f (x)$ を $T_{2} (| x |)$ ステップで計算する Turing 機械 $M$ が存在すると仮定して矛盾を導きます。もし $M$ が存在するのであれば、そのコード $y$ が存在します。そのとき $f (y)$ を考えます。 $T_{1} (| y |) \geq T_{2} (| y |) log T_{2} (| y |)$ が成り立てば、 $f (y)$ の計算においてシミュレートされ、値を出すことになり、対角線論法により矛盾を導けます。しかし、与えられた条件はこれを満たすほど強力ではないため、この条件は満たされる保証がありません。

ところが、補題 6-2-a により、 $f (x)$ が計算可能である場合、それを計算する Turing 機械は無限個存在しますので、そのコードを $y_{1}, y_{2}, y_{3}, ...$ とします。 $T_{2} (n) log T_{2} (n) = o (T_{1} (n))$ が成り立つ時、どんな係数 $c$ に対しても有限の場合を除きすべての $y_{i}$ において次が成り立ちます。

T_{2} (| y_{i} |) log T_{2} (| y_{i} |) \leq c T_{1} (| y_{i} |)

したがって、これを満たすような $y_{i}$ において、シミュレーションが最後まで実行できるため、対角線論法により矛盾が導けます。

6-3. 領域計算量

いままで Turing 機械の計算ステップに関して、いろいろ議論してきましたが、これらのことはテープの消費量に関しても同様になりたちます。これを領域計算量と言います。

領域計算量 $S (n)$ の $k$ テープ Turing 機械を万能 Turing 機械でシミュレートする時、 $O (S (n))$ の領域計算量で計算できます。

線形加速定理に対して、同様の証明で領域節約定理が成り立ちます。但し、領域節約定理では実際に使用するテープのマスは減っても処理に必要なビット数は変わりません。

階層定理は次が成り立ちます。

$S_{1} (n)$ が領域構成可能関数だと仮定する。また $S_{1} (n) \neq O (S_{2} (n))$ とする。その時、どんな領域計算量 $S_{2} (n)$ の Turing 機械にも計算できない、領域計算量 $S_{1} (n)$ で計算できる関数 $f (x)$ が存在する。

ここで領域構成可能関数とは、与えられた関数 $f (n)$ に対して、すべてのパラメータ $n$ に対し、ちょうど $f (n)$ マスだけ使用して停止する Turing 機械を構成できることを言います。

但しこれを証明するには、新しい概念と、補題が必要になります。様相(Configuration) とは、Turing 機械の状態とテープヘッドの位置と一回でも使用したテープの内容の組を指します。テープの長さは無限を仮定していますが、有限時間内に使用するテープの量は有限ですので、様相の長さは有限になります。一方、δ関数により、ある様相から 1 ステップで行ける様相を定義することが出来るます。すると、様相の集合を考えた時、計算を様相から様相への移り替わりの列と定義することが出来、また、様相を頂点とすると、 δ関数で遷移できると言う関係を辺で表す有効グラフを定義できます。今回、様相を用いることで使用するのは次の補題です。

補題

Turing 機械 $M$ の領域の使用量が $S$ で抑えられているとする。その時、 $2^{c S}$ 時間で $M$ が停止するかしないかを決定できるような定数 $c$ が存在する。

証明

領域が $S$ で抑えられている時、様相の表現の長さも $S$ の定数倍 $c S$ で抑えることが出来ます。ここで、一般性を失わず、様相が 0, 1 だけで表現されていると仮定できます。すると、表現可能な様相全ては高々 $2^{c S}$ 個だけになります。

Turing 機械 $M$ の計算を考えると、初期様相からスタートし、δ 関数に従って、様相を移り替わりながら計算をします。さて、 $M$ の計算が $2^{c S} + 1$ 時間続いたとします。 $M$ の様相の列 $c_{1}, c_{2}, c_{3}, ..., c_{2^{c S} + 1}$ を考えると、 $c_{2^{c S} + 1}$ は、時刻 1 から $2^{c S}$ の間に、少なくと一回は出現しているはずです。ここで、ある様相から次の様相は一意に定まることに注意すると、結局、 $M$ は無限ループに入っていることになります。従って、 $M$ が $2^{c S}$ 時間で計算を終了しない時は、停止しないと判断できることになります。Q.E.D.

6-4. 宿題

1

次を証明しなさい。

$S_{1} (n)$ が領域構成可能関数だと仮定する。また $S_{2} (n) = o (S_{1} (n))$ とする。その時、どんな領域計算量 $S_{2} (n)$ の Turing 機械にも計算できない、領域計算量 $S_{1} (n)$ で計算できる関数 $f (x)$ が存在する。

2

$g (n) \neq O (f (n))$ かつ $f (n) \neq o (g (n))$ となる $f (n), g (n)$ はどちらも単調非減少関数としても見つかります。そのような例を一つ挙げなさい。

6-5. 次週の予告

次回は計算時間の下限が示されている問題を紹介します。

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 6 回 線形加速定理、階層定理