Aritalab:Lecture/Automata/TM

Revision as of 15:28, 26 October 2010

チューリング機械

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

まず、決定性の１テープチューリング機械 (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₁, 0, +1)

のように与えます。これは状態 q₀ のときにヘッド下に記号 0 があれば、次の状態 q₁ に移動してヘッドの記号を 1 に書き換え、ヘッドを右に 1 だけ移動させるという意味します。これが 1 ステップ分の動作です。

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

このDTMを ... b b b 01の列 b b b ... と書いてあるテープ上で01列の開始部分を初期ヘッド位置としてスタートさせましょう。 すると10の入力にかかわらずヘッド位置を +1 させていき、b を見つけた時点で -1 移動して戻ります。戻った位置が 0 なら更にもうひとつ戻り、二つ 0 が続いたときのみ q_Y 状態になります。

文字列の長さの差を計算するDTM

プログラムを書き下すのは煩雑なので、ヘッドの動きだけで解説します。 二つの文字列の長さだけが 0^m10ⁿ とテープに書かれていると仮定します。 ここで m - n ≤ 0 ならその長さ分の0, m - n < 0 なら0を返すプログラムを考えます。 まずDTMは最初の 0 を $ に置き換え、右へ移動して 1 の右隣にある 0 を 1 に変えます。そして、次に左方向に $ に出会うまで戻ります。これを繰り返します。 すると最後に

1. 0ⁿ が全て 1 に書き換わり、右に 0 を探しに行って空白に出会う
2. 0^m が全て 1 に書き換わり、左に 0 を探しに行って $ に出会う

のどちらかに遭遇します。前者のときは、テープに n+1 個の $ が書き込まれているので右端の $　を 0 に書き換え、残った 1 を全て b にします。 後者のときは、結果が 0 になるので、残った01の文字を全て b にします。

クラス P

DTMのプログラムが、あらゆる入力 x ∈ Σ^* (|x| = n) に対して要するステップ数を考えるため、時間計算量の関数 T_M(n) を用意します。

T_M(n) = { 長さ n の入力に対してプログラムMが要するステップ数の最大値 }

この値が、ある多項式 p を用いて T_M(n) ≤ p(n) と書けるなら、M はDTMの多項式時間プログラムであると言います。

また、多項式時間で問題を解くDTMが存在する問題の集合をクラス P と言います。

クラス NP

ここでは簡単な概念を説明します。クラスNPは Nondeterministic polynomial の略で、NDTMという、DTMに「ヤマ張り」モジュールを追加したチューリングマシンを考えます。 NDTMは通常のヘッドに加え、NPは「ヤマ張りヘッド」を持っており、以下の手順で作動します。

1. テープに長さ |x| の入力が与えられる。
2. ヤマ張りヘッドが、入力文字列を壊さないようにテープに何らかの文字列 (∈ Σ^*)を書き込みます。長さは何でもよく、書き込み続けて停止しなくてもOKです。
3. 　ヤマ張りヘッドが停止する場合に限り、DTMと同様に通常のヘッドが起動して計算をおこないます。
4. 状態が q_Y, q_N にきたら停止します。このうち、 q_Y を受理状態とし、 q_N または停止しない場合は非受理状態とします。

こうすると、入力 x に対する計算のバリエーションは無限通り存在します。 そのうちいくつかが受理状態に到達すると仮定します。受理状態に到達する過程のなかで最小ステップ数のものが、計算時間に相当します。 時間計算量の関数は

TM(n) = { 長さ n の入力に対してプログラムMが受理状態になるのに要するステップ数の最大値 }

と定義します。 ここで非受理状態になる計算は無視している点に注意してください。