Aritalab:Lecture/Automata/TM

Revision as of 00:34, 26 October 2011

チューリング機械

計算量理論においてコンピュータのモデルとなるのが、チューリング機械 (TM: Turing Machine) です。 チューリング機械は無限の長さを持つテープと、テープに読み書きをおこなう有限制御部（ヘッド）から構成されます。 オートマトンとの根本的な違いはテープ上に自由に読み書きができる点です。

決定性１テープチューリング機械

まず、決定性の１テープチューリング機械 (DTM: Deterministic one-tape Turing Machine) を定義しましょう。

DTMのプログラムは以下の4項目から構成されます。

1. テープに書ける記号の集合 Γ
   DTMに入力される記号の集合 Σ ⊂ Γ と、空白記号 b ∈ Γ - Σ を含みます。
2. 状態集合 Q
   ここには初期状態 q₀ と、YES/NO に対応する受理状態 q_Y, q_N が含まれます。
3. 状態遷移関数 δ
   (Q - {q_Y, q_N}) × Γ   →   Q × Γ × {-1, +1}.
4. 入力文字列 x ∈ Σ^*

テープはあらかじめ空白で埋められているとし、初期状態は q₀ です。 状態遷移関数は

δ(q₀, 0) = (q₁, 1, +1) 　[状態、テープ記号、ヘッド位置]

のように与えます。これは状態 q₀ のときにヘッド下に記号 0 があれば、次の状態 q₁ に移動してヘッドの記号を 1 に書き換え、ヘッドを右に 1 だけ移動させるという意味します。これが 1 ステップ分の動作です。 TM のコンディションは現在状態 q 、テープの開始位置から現在のヘッド位置までの内容全て s, 現在のヘッド位置からテープの終了位置までの内容全て t を三つ組みにした (q, s, t) で一意に指定できます。これを様相といいます。 様相 S₁ から　S₂ に1ステップで移動できるとき、S₁ ⇒ S₂ と書きます。 入力列 x に対して、ある受理状態 q_f ∈ F と何らかのテープ記号列 y, z ∈ Γ^* が存在して、(q₀, ε, x) ⇒...⇒ (q_f, y, z) であれば、 x は受理されたといいます。 受理されない語に対して、TM は停止しない場合もありえます。

例：入力された二進数が4の倍数であることを認識するDTM

例として 1...00 と書いてあるテープ上で01列の開始部分（左端）を初期ヘッド位置としてスタートさせます。

1. 初期状態 q₀
   1. テープの入力が0でも1でも、初期状態 q₀ のままヘッドを +1 します
   2. 初期状態で b をみつけたら、状態 q₁ に移動してヘッドを b の左隣に動かします
2. 状態 q₁
   1. ヘッド位置に 0 があれば2桁目を判定するため q₂ に移動してヘッドを b の左隣に動かします
   2. ヘッド位置に 1 や b があれば、受理状態 q_N に移動します
3. 状態 q₂
   1. ヘッド位置に 0 があれば受理状態 q_Y に移動し、それ以外は NO

つまり、10 の入力文字列にかかわらずヘッド位置を +1 させていき、b を見つけた時点で −1 戻ります。戻った位置が 0 なら更にもうひとつ戻り、二つ 0 が続いたときのみ q_Y 状態になります。

例：文字列の長さの差（または引き算）を計算するDTM

プログラム（＝状態遷移関数）を書き下すのは煩雑なので、ヘッドの動きだけで解説します。 二つの文字列の長さだけが 0^m10ⁿ とテープに書かれていると仮定します。

ここで m - n > 0 ならその長さ分の 0 を返し、m - n ≤ 0 なら長さ分の 1 を返すプログラムを考えます。 まずDTMは最初の 0 を b に置き換え、右へ移動して 1 の右隣にある 0 を 1 に変えます。そして、次に左方向に b に出会うまで戻ります。これを繰り返します。 すると最後に

1. m > n の場合： 0^m を n+1 回 b に書き換え、右に 0 を探しにいって空白 b に出会う
2. m ≤ n の場合： 0ⁿ を m 回 1 に書き換え、左に 0 を探しに行って b に出会う

のどちらかに遭遇します。前者のときは、テープに n+1 個の b が書き込まれているので一度左端に戻って最右の b を 0 に書き戻し、0 をこえて右側に移動し、残った 1 を全て b にします。 後者のときは右側に移動し、残った 1 を全て b に、更にその右に残った 0 を全て 1 に変えます。（このとき 0 が残っていない可能性もあり、その時の最終結果は全て b です。）

例：文字列の長さの和（または足し算）を計算するDTM

二つの文字列の長さだけが 0^m10ⁿ とテープに書かれていると仮定します。 引き算に比較すると足し算は楽です。左端から 0^m を 1 まで読み飛ばし、1 の位置に 0 を書き込みます。その次に、 0^m を b まで読み飛ばし、b を見つけたら左隣に 1 マス戻って b を書き込んで終了します。

多重トラックチューリング機械

DTMにおいて各状態が記号を有限個記憶しておける、と仮定してもDTMの定義から外れません。 状態 q ∈ Q にたとえば記号 a ∈ Σ を記録できるとするなら、 (q, a) という二つ組みを新しい状態集合とみなせばよいだけです。

またテープに複数の（有限の）トラックがあり、ヘッドが複数の記号を書けるとしても定義から外れません。もともとテープを左右に1マスずつ動かしていたところを、nマスのブロック毎に移動させるだけです。従って、多重トラックDTM、記憶領域つきDTMの計算能力は、もとのDTMの計算能力と差はありません。

多テープチューリング機械

複数のテープを持ち、制御部（ヘッド）も各テープ毎に持っているチューリング機械を考えましょう。 状態遷移関数における制御部の移動先は、 +1, -1 に加えて 0 （動かない）という項を追加します。これは各制御部の位置を自由に設定するのに必要です。

この多テープTMが、もとのDTMと計算能力に差がないことを示しましょう。 テープが n 本あるTMなら、2n トラックをもち、i　個の記号を記憶できるDTMで模倣します。テープ i に対応する2トラックには、テープ i のヘッド位置マーカーとテープ i の中身全体が記録されています。 複数ヘッドを持つ多テープTMの1ステップは、2n トラックDTMのヘッドがテープ全体を一往復することで模倣できます。 まず、往路において各テープ i から読んでいる記号をヘッドの記憶部分に記録します。合計 n 個の記号を記憶し、多テープTMの状態を把握します。 復路において、各位置マーカーが読んでいる部分のテープ記号を更新し、ヘッド位置マーカーを移動させます。

結果として、多テープTMの計算能力は、もとのDTMの計算能力と差はありません。

非決定性チューリング機械

非決定性チューリングマシン (NDTM: Non-deterministic Turing Machine) の場合、各状態と各テープ記号について動作の選択肢が有限個存在します。 これら選択肢の最大値を r とし、これら選択肢を 1 から r までの数字で表現します。

三重トラックチューリング機械を用意し、第 1 トラックに入力列が書かれているとします。 第 2 トラックは、1からrで構成される数字の列を記録するスタック記憶域として利用します。 第 3 トラックは、第 1 トラックから入力を丸々写し取って非決定性TMの動きをシミュレートするヒープ領域として利用します。 そして入力列から生成される選択肢全てを順番に試していきます。もしも選択肢のいずれかの結果、受理状態に至ったら受理とし、それ以外は入力を受理しないとします。

結果として、非決定性TMの計算能力は、もとのDTMの計算能力と差はありません。

万能チューリング機械

記憶域つき多テープ多重トラックTMが現在の計算機のモデルになることは、容易に想像できると思います。ここでは、様々なバリエーションの計算能力が、もとの決定性TMの計算能力と変わらないことを一般化して、いかなるTMでもシミュレートできる万能チューリング機械 (UTM: Universal Turing Machine) を考えましょう。

チューリング機械の本質は、テープ記号、状態集合、状態遷移関数、入力文字列でした。 以上の情報は、状態や入力文字の符号化を定めてやれば01の列として表現できます。 従って、TMの構成を01列の「プログラム｣とみなして動作をシミュレートすればOKです。

模倣するには3テープのTMを利用します。テープ1には模倣したいTMの構造を01の列として記述しておき、テープ2に、模倣するTMの入力文字列をセットします。 テープ3は処理用で、ヘッドの現在状態とテープ2のヘッドが読んでいる入力文字列を毎回コピーしてきます。テープ3に書かれた情報をテープ1の中にある状態遷移関数と照らし合わせて次状態を探し、それをテープ2と3に上書きします。

結果として、UTMの計算能力でさえ、もとのDTMの計算能力と差がないことがわかります。