Aritalab:Lecture/Automata/TM
m |
|||
Line 9: | Line 9: | ||
DTMのプログラムは以下の4項目から構成されます。 | DTMのプログラムは以下の4項目から構成されます。 | ||
# テープに書ける記号の集合 '''Γ'''<br/> DTMに入力される記号の集合 Σ ⊂ Γ と、空白記号 b ∈ Γ - Σ を含みます。 | # テープに書ける記号の集合 '''Γ'''<br/> DTMに入力される記号の集合 Σ ⊂ Γ と、空白記号 b ∈ Γ - Σ を含みます。 | ||
− | # 状態集合 '''Q''' <br/>ここには初期状態 q<sub>0</sub> と、YES/NO | + | # 状態集合 '''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}. | # 状態遷移関数 '''δ'''<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> です。 | ||
状態遷移関数は | 状態遷移関数は | ||
Line 70: | Line 71: | ||
後者のときは、結果が 0 になるので、残った01の文字を全て b にします。 | 後者のときは、結果が 0 になるので、残った01の文字を全て 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の計算能力と差はありません。 | ||
+ | |||
+ | ===非決定性チューリング機械=== | ||
+ | 非決定性TMの場合、各状態と各テープ記号について動作の選択肢が有限個存在します。 | ||
+ | これら選択肢の最大値を 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の計算能力と差がないことがわかります。 | ||
==クラス P == | ==クラス P == |
Revision as of 16:07, 30 October 2010
Contents |
チューリング機械
計算量理論においてコンピュータのモデルとなるのが、チューリング機械 (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 にします。
多重トラックチューリング機械
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の計算能力と差はありません。
非決定性チューリング機械
非決定性TMの場合、各状態と各テープ記号について動作の選択肢が有限個存在します。 これら選択肢の最大値を 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の計算能力と差がないことがわかります。
クラス 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が受理状態になるのに要するステップ数の最大値 }
と定義します。 ここで非受理状態になる計算は無視している点に注意してください。