カッコ言語の時間計算量は次のように見積もれます。
入力を読むテープヘッドは逆戻りせず、一回だけ入力を読むので、 O(n) 時間。
1 テープ Turing 機械では閉じカッコを見つけるとそれに対応するカッコを探 すためヘッドが戻り、対応を確認したらもとの閉じカッコの隣へと復帰します。 閉じカッコを発見した時、ヘッドが戻り、復帰する動作にかかるヘッドの移動 距離は高々 2 n 時間。 閉じカッコは高々 n 個あるので、全体の時間計算量は O ( n2 )。
今回は Turing 機械のインタプリタを構成します。 そのためには、Turing 機械自身を Turing 機械で扱えるデータにしなければ なりません。 そのために、Gödel Numbering という符号化を行います。
まず、二つの自然数を一つの自然数で表すことを考えます。 これは、x, y 座標面上の格子点を図のように数えて いくことにより実現します。
つまり、 π(0,0)=0, π(0,1)=1, π(1,0)=2, π(0,2)=3, π(1,1)=4, π(2,0)=5, … が成り立つような関数πを求めます。
この数え上げを実現させるには次のようにπを計算します。
になる。
与えられた値 p から π(x, y) = p を満たす x, y を求 めるアルゴリズムを示しなさい。
任意の自然数の列 ( n1, n2, ... , nk) を一つの自然数に埋め込む方法を考えよう。 効率さえ問われなければ次のようにすることにより可能である。
素数の列を p1 = 2, p2 = 3, p3, …… とする。 その時、 p1n1・ p2n2・ ...・ pknk は一つの数を表すが、素因数分解の一意性から、この数が与えられれば正しく 元の数 ( n1, n2, ... , nk) を復元することができる。Turing 機械は、次の 5 つの組で定義できます。
集合を一つの数にするには、要素を表す文字列を二進数などで表し、それをカ ンマなどの区切り記号で列挙すれば可能です。 但し、状態、アルファベットなど、どんな記号を使うかが本質ではなく単純に 数が分かればいい状態だと、集合の要素数のみで事足ります。 終了状態の集合だけはすべての要素を列挙しなければならないでしょう。 δ関数は(現在の状態, 入力文字1, 入力文字2, ..., 入力文字k, 次の状態, 出力文字1, 出力 文字2, ..., 出力文字k, ヘッドの移動 1, ヘッドの移動2,... , ヘッドの移動 k) を必要な分だけ繰り返すことで表現できます。
結局、Turing 機械の構成は多くの数の組で表現でき、それを前節までで説明 した手法により、一つの数で Turing 機械を定義することができます。
Church の提唱を使えば、Turing 機械のコードを解釈する Turing 機械が存在 することは言えます。 しかし、計算量や Turing 機械のテープ数による能力の違いを議論するため、 ここでは Turing 機械の構成の概略を説明します。
与えられたコードが k 本テープを使用する Turing 機械を表してい るとします。 この Turing 機械をシミュレートする際、 k 本のテープをそのま ま割り当てます。 さらにシミュレートの作業用に何本かのテープを使用します。 はじめに与えられたコードを蓄えるテープを用意します。 また、シミュレートしている Turing 機械の状態などを記憶するテープも用意しま す。 そして、シミュレートしている Turing 機械のテープヘッドの位置を記憶する テープを k 本用意します。
Turing 機械の 1 step のシミュレーションの手順を示します。 まず、現在の状態と、テープの位置の記号から、それに適合するδ関数の値を 読みだします。 これにはコードを解析する必要があります。 一本のテープに素数列を生成します。 これは素朴にエラトステネスのフルイを使用します。 Turing 機械のコードの長さを d とすると必要な素数は高々 2d まで生成すれば良いです。 割算x÷y は、x を始めに記憶しておき、 y を桁をずらしながら引き算が可能かどうかを調べていきます。 結果を入れるテープを含め 3 本のテープを使い、 O(log x log y ) 時間で計算できます。 これを使い、コードから一つのδ関数の割り当てを取り出すためには、素数を 順に生成していき、各素数で割れるだけ割ることになります。 素数の生成に O( 2d ) 時間かかるので、 適合するδ関数の値を読み出すのに、c を定数とすると、 O( 2c d )程度の時間がかかります。 また、テープは数本(5〜6本)余分に使用します。 そして、読み出したδ関数の値に従い、各テープに記号を書き、移動させます。 結局、シミュレーションに使用するテープは数本で、かかる時間は O( 2c d )程度になります。 但し、d があらかじめ与えられた定数だとすると、もともとの Turing 機械の定数倍の時間だけかかると言えます。
前節のシミュレーションでは、与えられた Turing 機械のコードに対して、さ らにテープを追加してシミュレーションしました。 ここでは一つ Turing 機械を固定してあらゆる Turing 機械をシミュレートす ることを考えます。 そのため、与えられた時間計算量 T(n) の k テープ Turing 機械を O(T(n)2) 時間でシミュレー トする 1 テープ Turing 機械を構成します。
1 テープ Turing 機械で k テープ Turing 機械を 1 step シミュ レーションするにはテープを次のように使います。
各テープの内容は 2k ます毎に書かれます。 各テープは 2 マスを対にし、一マスはテープの内容を、もう一マスはテープ ヘッドがなければ 0 、あれば 1 を記入します。 そして、シミュレーションでは毎回各テープのヘッドの位置を読み込みます。 各テープのヘッドの記号を覚えておくため、kマスのテープ領域は あらかじめ用意しておきます。 そしてδ関数を計算します。 得られた値を元に、各テープのテープヘッドの位置に目的の記号を書いてヘッ ドを動かすことをシミュレートします。 一回に一つのテープだけを対象にすることで、書き込む記号の種類は有限個に なります。 したがって、テープヘッドを検索してヘッド位置に記号を書き、ヘッドを移動 する処理を行うために、書き込む記号ヘッドの移動方向ごとに異なるラベ ルを使用すれば、あらたなテープ上の記憶は必要ありません。 結局、 1 step のシミュレーションで必要なのは、各テープヘッドが読み書きす る記号を保存する k マスの領域と、ヘッドの検索時間と書き込む 時間になります。 もともとの Turing 機械の時間計算量が T(n) であれ ば、その時間内に使用できるテープのマスの最大値はやはり T(n) ですので、一回の検索にかかる時間は高々 O(T(n))時間でできます。 これを 1 step のシミュレーションで定数回行います。 最終的にこのシミュレーションは T(n) 回行うので、時間計算量は O(T(n)2) になります。
なお、最初の状態では入力の値が一マス毎に書かれている状態なので、シミュ レーションの準備をしなければなりません。 しかし、これは、テープの最初に k マスの領域をとり、その後、 2k マス毎に入力の値をコピーします。 これにかかる時間は入力の長さnに比例します。
2 テープ Turing 機械だと O(T(n) log T(n)) 時間でシミュレートできることが知られていま す。
万能 Turing 機械のコードの長さ d に対して、シミュレーション が d の多項式時間でできるようにするにはどうすれば良いか?
計算不能な問題を取り上げます。