Aritalab:Lecture/Automata/TM
m (Aritalab:Lecture/Basic/DTM moved to Aritalab:Lecture/Basic/TM) |
|||
Line 1: | Line 1: | ||
==チューリング機械== | ==チューリング機械== | ||
− | + | 計算量理論においてコンピュータのモデルとなるのが、チューリング機械 (TM: Turing Machine) です。 | |
チューリング機械は無限の長さを持つテープと、テープに読み書きをおこなう有限制御部(ヘッド)から構成されます。 | チューリング機械は無限の長さを持つテープと、テープに読み書きをおこなう有限制御部(ヘッド)から構成されます。 | ||
オートマトンとの根本的な違いはテープ上に自由に読み書きができる点です。 | オートマトンとの根本的な違いはテープ上に自由に読み書きができる点です。 | ||
Line 8: | Line 8: | ||
DTMのプログラムは以下の4項目から構成されます。 | DTMのプログラムは以下の4項目から構成されます。 | ||
− | # テープに書ける記号の集合 Γ | + | # テープに書ける記号の集合 '''Γ'''<br/> DTMに入力される記号の集合 Σ ⊂ Γ と、空白記号 b ∈ Γ - Σ を含みます。 |
− | # 状態集合 Q | + | # 状態集合 '''Q''' <br/>ここには初期状態 q<sub>0</sub> と、YES/NO に対応する終了状態 q<sub>Y</sub>, q<sub>N</sub> が含まれます。 |
− | # 状態遷移関数 δ | + | # 状態遷移関数 '''δ'''<br/>(Q - {q<sub>Y</sub>, q<sub>N</sub>}) × Γ → Q × Γ × {-1, +1}. |
− | # 入力文字列 x ∈ Σ<sup>*</sup> | + | # 入力文字列 '''x''' ∈ Σ<sup>*</sup> |
テープはあらかじめ空白で埋められているとし、初期状態は q<sub>0</sub> です。 | テープはあらかじめ空白で埋められているとし、初期状態は q<sub>0</sub> です。 | ||
状態遷移関数は | 状態遷移関数は | ||
: δ(q<sub>0</sub>, 0) = (q<sub>1</sub>, 0, +1) | : δ(q<sub>0</sub>, 0) = (q<sub>1</sub>, 0, +1) | ||
のように与えます。これは状態 q<sub>0</sub> のときにヘッド下に記号 0 があれば、次の状態 q<sub>1</sub> に移動してヘッドの記号を 1 に書き換え、ヘッドを右に 1 だけ移動させるという意味します。これが 1 ステップ分の動作です。 | のように与えます。これは状態 q<sub>0</sub> のときにヘッド下に記号 0 があれば、次の状態 q<sub>1</sub> に移動してヘッドの記号を 1 に書き換え、ヘッドを右に 1 だけ移動させるという意味します。これが 1 ステップ分の動作です。 | ||
+ | TM のコンディションは現在状態 q 、テープの開始位置から現在のヘッド位置までの内容全て s, 現在のヘッド位置からテープの終了位置までの内容全て t を三つ組みにした (q, s, t) で一意に指定できます。これを様相といいます。 | ||
+ | 様相 S<sub>1</sub> から S<sub>2</sub> に1ステップで移動できるとき、S<sub>1</sub> ⇒ S<sub>2</sub> と書きます。 | ||
+ | 入力列 x に対して、ある受理状態 f ∈ F と何らかのテープ記号列 y, z ∈ Γ<sup>*</sup> が存在して、(q<sub>0</sub>, ε, x) ⇒...⇒ (q, y, z) であれば、 x は受理されたといいます。 | ||
+ | 受理されない語に対して、TM は停止しない場合もありえます。 | ||
;入力された二進数が4の倍数であることを認識するDTM | ;入力された二進数が4の倍数であることを認識するDTM | ||
− | |||
<center> | <center> | ||
Γ = { 0, 1, b }, Σ = {0, 1}<br/> | Γ = { 0, 1, b }, Σ = {0, 1}<br/> | ||
Line 52: | Line 55: | ||
; 文字列の長さの差を計算するDTM | ; 文字列の長さの差を計算するDTM | ||
+ | <center> | ||
+ | Γ = { 0, 1, $, b }, Σ = {0, 1}<br/> | ||
+ | Q = { ちょっと複雑 } | ||
+ | </center> | ||
プログラムを書き下すのは煩雑なので、ヘッドの動きだけで解説します。 | プログラムを書き下すのは煩雑なので、ヘッドの動きだけで解説します。 |
Revision as of 14:27, 30 October 2010
チューリング機械
計算量理論においてコンピュータのモデルとなるのが、チューリング機械 (TM: Turing Machine) です。 チューリング機械は無限の長さを持つテープと、テープに読み書きをおこなう有限制御部(ヘッド)から構成されます。 オートマトンとの根本的な違いはテープ上に自由に読み書きができる点です。
まず、決定性の1テープチューリング機械 (DTM: Deterministic one-tape Turing Machine) を定義しましょう。
DTMのプログラムは以下の4項目から構成されます。
- テープに書ける記号の集合 Γ
DTMに入力される記号の集合 Σ ⊂ Γ と、空白記号 b ∈ Γ - Σ を含みます。 - 状態集合 Q
ここには初期状態 q0 と、YES/NO に対応する終了状態 qY, qN が含まれます。 - 状態遷移関数 δ
(Q - {qY, qN}) × Γ → Q × Γ × {-1, +1}. - 入力文字列 x ∈ Σ*
テープはあらかじめ空白で埋められているとし、初期状態は q0 です。 状態遷移関数は
- δ(q0, 0) = (q1, 0, +1)
のように与えます。これは状態 q0 のときにヘッド下に記号 0 があれば、次の状態 q1 に移動してヘッドの記号を 1 に書き換え、ヘッドを右に 1 だけ移動させるという意味します。これが 1 ステップ分の動作です。 TM のコンディションは現在状態 q 、テープの開始位置から現在のヘッド位置までの内容全て s, 現在のヘッド位置からテープの終了位置までの内容全て t を三つ組みにした (q, s, t) で一意に指定できます。これを様相といいます。 様相 S1 から S2 に1ステップで移動できるとき、S1 ⇒ S2 と書きます。 入力列 x に対して、ある受理状態 f ∈ F と何らかのテープ記号列 y, z ∈ Γ* が存在して、(q0, ε, x) ⇒...⇒ (q, y, z) であれば、 x は受理されたといいます。 受理されない語に対して、TM は停止しない場合もありえます。
- 入力された二進数が4の倍数であることを認識するDTM
Γ = { 0, 1, b }, Σ = {0, 1}
Q = {q0, q1, q2,
q3, qY, qN}
q | 0 | 1 | b |
q0 | (q0, 0, +1) | (q0, 1, +1) | (q1, b, -1) |
q1 | (q2, b, -1) | (q3, b, -1) | (qN, b, -1) |
q2 | (qY, b, -1) | (qN, b, -1) | (qN, b, -1) |
q3 | (qN, b, -1) | (qN, b, -1) | (qN, b, -1) |
このDTMを ... b b b 01の列 b b b ... と書いてあるテープ上で01列の開始部分を初期ヘッド位置としてスタートさせましょう。 すると10の入力にかかわらずヘッド位置を +1 させていき、b を見つけた時点で -1 移動して戻ります。戻った位置が 0 なら更にもうひとつ戻り、二つ 0 が続いたときのみ qY 状態になります。
- 文字列の長さの差を計算するDTM
Γ = { 0, 1, $, b }, Σ = {0, 1}
Q = { ちょっと複雑 }
プログラムを書き下すのは煩雑なので、ヘッドの動きだけで解説します。 二つの文字列の長さだけが 0m10n とテープに書かれていると仮定します。 ここで m - n ≤ 0 ならその長さ分の0, m - n < 0 なら0を返すプログラムを考えます。 まずDTMは最初の 0 を $ に置き換え、右へ移動して 1 の右隣にある 0 を 1 に変えます。そして、次に左方向に $ に出会うまで戻ります。これを繰り返します。 すると最後に
- 0n が全て 1 に書き換わり、右に 0 を探しに行って空白に出会う
- 0m が全て 1 に書き換わり、左に 0 を探しに行って $ に出会う
のどちらかに遭遇します。前者のときは、テープに n+1 個の $ が書き込まれているので右端の $ を 0 に書き換え、残った 1 を全て b にします。 後者のときは、結果が 0 になるので、残った01の文字を全て b にします。
クラス P
DTMのプログラムが、あらゆる入力 x ∈ Σ* (|x| = n) に対して要するステップ数を考えるため、時間計算量の関数 TM(n) を用意します。
- TM(n) = { 長さ n の入力に対してプログラムMが要するステップ数の最大値 }
この値が、ある多項式 p を用いて TM(n) ≤ p(n) と書けるなら、M はDTMの多項式時間プログラムであると言います。
また、多項式時間で問題を解くDTMが存在する問題の集合をクラス P と言います。
クラス NP
ここでは簡単な概念を説明します。クラスNPは Nondeterministic polynomial の略で、NDTMという、DTMに「ヤマ張り」モジュールを追加したチューリングマシンを考えます。 NDTMは通常のヘッドに加え、NPは「ヤマ張りヘッド」を持っており、以下の手順で作動します。
- テープに長さ |x| の入力が与えられる。
- ヤマ張りヘッドが、入力文字列を壊さないようにテープに何らかの文字列 (∈ Σ*)を書き込みます。長さは何でもよく、書き込み続けて停止しなくてもOKです。
- ヤマ張りヘッドが停止する場合に限り、DTMと同様に通常のヘッドが起動して計算をおこないます。
- 状態が qY, qN にきたら停止します。このうち、 qY を受理状態とし、 qN または停止しない場合は非受理状態とします。
こうすると、入力 x に対する計算のバリエーションは無限通り存在します。 そのうちいくつかが受理状態に到達すると仮定します。受理状態に到達する過程のなかで最小ステップ数のものが、計算時間に相当します。 時間計算量の関数は
- TM(n) = { 長さ n の入力に対してプログラムMが受理状態になるのに要するステップ数の最大値 }
と定義します。 ここで非受理状態になる計算は無視している点に注意してください。