図1
図2
線形加速定理は、一ステップに処理する情報量を何倍にもして計算速度を速く するというものです。 ここでは与えられた Turing 機械 M を 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)。
そこで、両隣の大きなマスの内容を収集し、 c ステップシミュレーショ ンをすると、中央のマスの内容とどちらか隣の大きなマスの内容が書き変わる ことになります。
ところで、両隣の大きな 3 マス分のテープの内容をあらかじめあらゆる状況 を想定しておけます。そして、それを読んで c ス テップ M の内容をシミュレートするのもあらかじめやっておくこ とができます。 つまり、(M のヘッドの位置)と(大きな 3 マス分のテープ内容) から (M を c ステップシミュレートした結果の状態、 ヘッド位置、テープ内容) はあらかじめ関数として計算できるわけで、M' はこれをδ関数と して取り込むことができます。 つまり、このシミュレーション自体は 1 step で可能なわけです。
結局まとめると M の c ステップは次の 6 ステップ でシミュレーションできます。
なお、加速定理と呼ばれるものもあります (証明は難しいけど、実用上意味がないので割愛します)。 以下のように、いくらでも加速できる(つまり最適なアルゴリズムの存在しな い)関数が存在すると言うものです。
次の条件を満たす計算可能関数 f(x) が存在します。
どんな増加関数g(n)に対しても、 有限の場合を除き、 g(|x|)ステップ以内に f(x) を計算する Turing 機械が構成できる。
ここでは計算時間をかけないと解けない問題が存在することを示します。 はじめにこれに必要な補題をまとめます。
これは万能 Turing 機械の構成で証明の概略を説明しました。 さらに 2 テープ Turing 機械を使うと次のことが示せます。
この証明は基本的には 1 テープ Turing 機械で構成した万能 Turing 機 械と同内容です。 テープの使い方にテクニックが必要です。 証明については笠井琢美 「コンピュータサイエンス大学講座 17 計算量の理論」近代科学社 (1987) に譲ります。
さらに同じ関数を計算するプログラムが無限に存在するという次の補題 を使用します。
これはプログラムの先頭などに、何もしない動作を埋め込むことで簡単に示す ことができます。 一方、次の補題は参考文献において階層定理を証明するのに使われています。
この補題に関しては、参考文献では Turing 機械のコードの頭に 0 を埋め込 むことをゆるすことで示しています。 しかしこれを許すか許さないかはコンピュータのモデル化やコード化に依存し そうです。 但し、こちらを認めた方が良い結果が得られます。
関数のオーダーとして O の表記を使用してきました。 が、ここでは付け加えて o の表記を定義します。 f(n)=o(g(n)) は、fの増え方はgよりも真に少ないことを意味し、ある意味 f<g のような意味を持ちます。 この記号の厳密な定義は次の通りです。
「どのような定数 c>0 に対しても
ある数 N0 が存在し、全
ての N0 より大きい数 N に対して
f(N)≦cg(N)
が成り立つ」。
なお、これは一階述語論理式では次のように書けます。
(∀ c>0)
(∃ N0)
( ∀ N≧N0)
[f(N)≦cg(N)]
なお、 f(n)=o(g(n)) と g(n)≠ O( f(n)) は同値ではありません。
これらの補題を組み合わせることで次の階層定理が主張できます。
T1(n) が時間構成可能関数だと仮定する。 また T2(n) 2 = o(T1(n)) とする。 その時、 どんな時間計算量 T2(n) の Turing 機械 にも計算でき ない、時間計算量 T1(n) で計算できる関数f(x)が存在する。
T1(n) が時間構成可能関数だと仮定する。 また T1(n)≠ O(T2(n)2) とする。 その時、 どんな時間計算量 T2(n) の Turing 機械 にも計算でき ない、時間計算量 T1(n) で計算できる関数f(x)が存在する。
T1(n) が時間構成可能関数だと仮定する。 また T2(n) log T2(n) = o(T1(n)) とする。 その時、 どんな時間計算量 T2(n) の Turing 機械 にも計算でき ない、時間計算量 T1(n) で計算できる関数f(x)が存在する。
T1(n) が時間構成可能関数だと仮定する。 また T1(n)≠ O(T2(n) log T2(n)) とする。 その時、 どんな時間計算量 T2(n) の Turing 機械 にも計算でき ない、時間計算量 T1(n) で計算できる関数f(x)が存在する。
ここでは 6-1-b, 6-2-a を使用したものに対して証明することにします。
註: この f(n) が時間構成可能とは、 与えられた n に対して、f(n) step ちょ うどで停止する Turing 機械を構成できると言うことです。 通常の増加関数はほぼ可能です。
関数 f は入力x に対して次の処理をします。
この関数を計算するのに T1(|x|) ステップかかるのは明らかです。 一方、 f(x) が O(T2(|x|)) ステップで計算で きないことを示します。 f(x) を T2(|x|) ステップで計算する Turing 機械 M が存在すると仮定して矛盾を 導きます。 もし M が存在するのであれば、そのコード y が存在 します。そのとき g(y) を考えます。 T1(|y|)≧ T2(|y|) log T2(|y|) が成り立てば、 f(y) の計算においてシミュレートさ れ、値を出すことになり、対角線論法により矛盾を導けます。 しかし、与えられた条件はこれを満たすほど強力ではないため、この条件は満 たされる保証がありません。
ところが、補題 6-2-a により、f(x) が計算可能であ る場合、それを計算する Turing 機械は無限個存在しますので、そのコードを y1, y2, y3, ... とします。 T2(n) log T2(n) =o(T1(n)) が成り立つ時、どんな係数 c に対しても有限の場合を除きすべて の yi において次が成り立ちます。
したがって、これを満たすような yi において、シ ミュレーションが最後まで実行できるため、対角線論法により矛盾が導けます。
いままで Turing 機械の計算ステップに関して、いろいろ議論してきましたが、 これらのことはテープの消費量に関しても同様になりたちます。 これを領域計算量と言います。
領域計算量 S(n) の k テープ Turing 機 械を万能 Turing 機械でシミュレートする時、 O(S(n)) の領域計算量で計算できます。
線形加速定理に対して、同様の証明で領域節約定理が成り立ちます。 但し、領域節約定理では実際に使用するテープのマスは減っても処理に必要な ビット数は変わりません。
階層定理は次が成り立ちます。
ここで領域構成可能関数とは、与えられた関数 g(n) に対して、すべてのパラメータ n に対し、ちょうど g(n) マスだけ使用して停止する Turing 機械を構成 できることを言います。
但しこれを証明するには、新しい概念と、補題が必要になります。 様相(Configuration) とは、Turing 機械の状態とテープヘッドの 位置と一回でも使用したテープの内容の組を指します。 テープの長さは無限を仮定していますが、有限時間内に使用するテープの量は 有限ですので、様相の長さは有限になります。 一方、δ関数により、ある様相から 1 ステップで行ける様相を 定義することが出来るます。すると、様相の集合を考えた時、計算を様相から 様相への移り替わりの列と定義することが出来、また、様相を頂点とすると、 δ関数で遷移できると言う関係を辺で表す有効グラフを定義できます。 今回、様相を用いることで使用するのは次の補題です。
Turing 機械 M の領域の使用量が S で抑えられてい るとする。 その時、 2cS 時間で M が停止するかしないかを決定できるような定数 c が存在する。
領域が S で抑えられている時、様相の表現の長さも S の定数倍 cS で抑えることが出来ます。 ここで、一般性を失わず、様相が 0, 1 だけで表現されていると仮定できます。 すると、表現可能な様相全ては高々 2cS 個だけにな ります。
Turing 機械 M の計算を考えると、初期様相からスタートし、δ 関数に従って、様相を移り替わりながら計算をします。 さて、M の計算が 2cS+1 時間続いたとし ます。 M の様相の列 c1, c2, c3, ..., c2cS+1 を考えると、 c2cS+1 は、時刻 1 から 2cS の間に、少なくと一回は出現し ているはずです。 ここで、ある様相から次の様相は一意に定まることに注意すると、結局、 M は無限ループに入っていることになります。 従って、 M が 2cS 時間で計算を終了し ない時は、停止しないと判断できることになります。Q.E.D.
次を証明しなさい。
g(n)≠ O( f(n)) かつ f(n)≠o(g(n)) となる f(n), g(n)) はどちらも単調非減少関数としても見つかります。 そのような例を一つ挙げなさい。
次回は計算時間の下限が示されている問題を紹介します。