オートマトンとチューリング機械 - HAGIYA Laboratory

オートマトンとチューリング機械
有限オートマトン
有限オートマトン
• 有限個の状態
– 現在の状態
– 初期状態
– 受理状態
• 入力文字列
– 有限個の文字 … アルファベット
• 状態遷移
– 入力文字と現在の状態に従って、
現在の状態をかえる。
状態遷移図
0
初期状態
二進数を、0と1から
成る文字列として入力し、
3の余りを計算する
有限オートマトン
1
1
0
0
1
言語
• アルファベット
– 有限個の文字の集合
– Σなどで表す。例：Σ={0,1}
• 文字列（語）
– アルファベットに属する文字の有限列
– 例：0, 00, 1100, 0101
– 空列も文字列。εやλで表す。
– 文字列の全体をΣ* で表す。
• 言語（形式言語）
– 文字列の集合、すなわちΣ* の部分集合。
– 例：3で割り切れる二進数の全体
言語の認識装置としての
有限オートマトン
• 状態のいくつかを受理状態とする。
– 受理状態は複数あってもよい。
• 与えられた文字列に従って、
初期状態からはじめて状態遷移を繰り返す。
– 初期状態は一つ。
• 文字列を読み終わった直後の状態が
受理状態ならば、その文字列を受理。
• 有限オートマトンMが受理する
文字列の全体をL(M)と書く。
• L(M)をMの受理言語という。
有限オートマトン
0
初期状態
3で割り切れる二進数の
全体を受理する
有限オートマトン
受理状態でもある。
1
1
0
0
1
有限オートマトン
初期状態
0
0
1
1
1
0
0
1
0と1を
奇数個ずつ
含む文字列を
受理する
オートマトン
正則表現
• 言語を表す記法
• 文字列のパターンを表す。
• 例：0(10)*1
– 0で始まり10が繰り返されて1で終わる文字列
– そういう文字列からなる言語
• 例：0(11+00)1
– 0の次に11または00が来て、1で終わる文字列
• 例：0(11+00)*1
正則表現から有限オートマトンへ
• 正則表現⇒有限オートマトン
– 任意の正則表現に対して、その言語を受理する
非決定的な有限オートマトンが存在する。
• 決定化
– 非決定的な有限オートマトンは、受理言語が同じ
決定的なオートマトンに変換できる。
• 最小化
– 決定的なオートマトンは、
受理言語をかえずに状態数が最小化できる。
• 有限オートマトン⇒正則表現
• 正則言語
非決定的な有限オートマトン
ε遷移：
文字を入力せずに
遷移できる。
ε
初期状態
0
0
0
1
1
1
非決定的な有限オートマトン
受理状態に至る遷移のしかたが
一つでもあればよい。
0
初期状態
0
0
0
1
1
1
1
決定的な有限オートマトン
初期状態
0
0
0
0
1
1
1
決定的な有限オートマトン
初期状態
0
0
0
0
1
1
1
1
0
0
1
1
状態数最小の有限オートマトン
0
初期状態
0
0
1
1
1
1
0
0
1
有限オートマトンの性質
• 受理言語の合併、交わり、補集合、連接、
閉包などに関して閉じている。
– 任意のM1とM2に対して、
L(M1)∪L(M2)=L(M)となるMが存在する。
• 二つのオートマトンが受理する言語が同じか
どうかを判定することができる。
• 数を数えられない：有限オートマトンの限界
– 例えば、0と1を同じ数だけ含む文字列のみを
受理する有限オートマトンは存在しない。
チューリング機械
チューリング機械
ヘッド
テープ
有限状態制御部
チューリング機械の動作
• 有限状態制御部の状態と、
ヘッド上の文字の各組み合わせに対して、
– ヘッドが書き込む文字（同じ文字をかけば無変化）
– 次の状態
– （文字を書いた後に）ヘッドを
左右のどちらに動かすか、
動かさないか。
という動作を定義。
• 動作が一通りに定まらないものは、
非決定的なチューリング機械
チューリング機械の停止
• 停止状態を定めることもある。
• 次の動作が定義されなかったら停止。
• 場合によっては、停止しないこともある。
言語の認識装置としての
チューリング機械
• 入力文字列をテープ上に書き込み、
– 書き込む前は空白文字が埋まっている。
– テープには、入力文字列に現れる文字以外の
文字を書き込んでもよい。
– 入力アルファベット ⊂ テープ・アルファベット
•
•
•
•
ヘッドを最初の文字の上におき、
状態を初期状態にセットして、
機械を走らせる。
停止したら、その文字列を受理。
– 受理状態において停止したら、
とすることもある。
チューリング機械と計算可能性
言語の認識装置として
• 入力アルファベット上の言語Lが、
チューリング機械Mによって
認識できるとき、その言語を
帰納的に可算という。
• Mを用いれば、与えられた文字列が
– Lに属しているとき、
有限時間内にそのことがわかる。
– Lに属していないときは、
Mは止まらないかもしれないので、
そのことはいつまでたっても
わからないかもしれない。
• 以上のような認識が、
計算の限界である。
– チャーチのテーゼ
w∈L
入力文字列w
0 1 1 0 1
チューリング
機械
M
受理or不受理
（or非停止）
w∈L
帰納的に可算 vs. 帰納的
• 入力アルファベット上の言語Lが、
常に停止するチューリング機械
Mによって認識できるとき、
その言語を帰納的いう。
• Mを用いれば、与えられた文字列が
– Lに属しているとき、
有限時間内にそのことがわかる。
– Lに属していないときも、
有限時間内にそのことがわかる。
• 言語Lとその補集合がどちらも
帰納的に可算ならば、
L（およびその補集合）は
帰納的になる。
w∈L
Mへの入力
0 1 1 0 1
チューリング
機械
M
受理or不受理
（常に停止する）
w∈L
関数の実現機構として
• チューリング機械を用いて、
文字列をもらって文字列を返す関数を実現できる。
– 入力文字列をテープ上に書き込み、
チューリング機械を走らせる。
– 停止したら、テープ上の文字列を返す。
• 空白は無視する。
• チューリング機械は止まらないかもしれないので、
いつも出力が得られるとは限らない。
– 部分関数
• このような関数を部分帰納的関数という。
• 常に出力が得られるときは、帰納的関数という。
– チューリング機械が常に止まる場合。
決定性と非決定性
• 計算可能性に関して（言語の認識装置として）、
決定的なチューリング機械と
非決定的なチューリング機械に
能力の差はない。
– 非決定的なチューリング機械が入力文字列を
受理するとは、入力文字列をテープ上に書き込み、
非決定的な動作を適切に選べば、
（受理状態で）停止すること。
– 任意の非決定的なチューリング機械に対して、
同じ言語を受理する決定的なチューリング機械が
存在する。
0 1 1 0 1
チューリング
機械
非決定的な
チューリング機械
M
1 1 1 0 1
0 1 1 0 1
チューリング
機械
チューリング
機械
M
M
1 0 1 0 1
1 1 1 0 1
チューリング
機械
チューリング
機械
M
M
分身を作ると
思えばよい。
分身の一つが
受理すればよい。
万能チューリング機械
Mへの入力
Mのプログラム
Mへの入力
0 1 1 0 1
s c z k q b
0 1 1 0 1
チューリング
機械
M
受理or不受理（or非停止）
万能
チューリング
機械
受理or不受理（or非停止）
万能チューリング機械と停止問題
• 万能チューリング機械は、
任意のチューリング機械Mのプログラムと
Mへの入力に対して、Mをシミュレートできる。
– Mが停止しないときは、
万能チューリング機械も停止しない。
• Mが停止しないときも停止して、
Mの非停止を判定できるような
万能チューリング機械は存在するか。
– プログラムが停止しないことを、
プログラムを実行せずに判定できるか？
• 答えは否。
チューリング機械と計算量
言語の認識の計算量
• 帰納的な言語を考える。
– それを受理するチューリング機械は、
任意の文字列に対して必ず停止する。
• 入力文字列に対して、
チューリング機械が停止するまでの
動作ステップ数が、入力文字列の長さに
どのように依存するか。
– 特に、入力文字列の長さnの「多項式」に比例した
ステップ数（以下）で停止するか。
例えば、n2, n3...
Ｐ：多項式時間
• 帰納的な言語に対して、
それを受理する決定的な（常に停止する）
チューリング機械で、
停止するまでの動作ステップ数が
入力文字列の長さの多項式で
抑えられるものが存在するとき、
その言語をＰという。
– もしくは、そのような言語のクラス（集まり）を
Ｐという。
ＮＰ：非決定的多項式時間
• 帰納的な言語に対して、
それを受理する非決定的な（常に停止する）
チューリング機械で、
停止するまでの動作ステップ数が
入力文字列の長さの多項式で
抑えられるものが存在するとき、
その言語をＮＰという。
• 動作の選び方をうまく選んだとき、
受理状態で停止するならば、
その入力文字列は受理されたとする。
ＰとＮＰ
• もちろん、ＰはＮＰに含まれる。
– Ｐである言語はＮＰでもある。
• ＰとＮＰは等しいか？
– クレイ数学研究所が2000年に提示した
七つのミレニアム問題の一つ
（賞金１００万ドル）
ＮＰ完全
• ＰとＮＰが等しいかどうかはわからないが、
ＰとＮＰが等しくないと仮定すると、
ＮＰ－Ｐに含まれることを示せる問題がある。
– ＮＰのうちで最も難しい問題
– ＮＰに属する任意の問題は、
多項式ステップでそのような問題に還元できる。
– そのような問題をＮＰ完全という。
– 逆に、ＮＰ完全の問題がＰに属するならば、
ＮＰに属するすべての問題がＰに属する。
ＮＰ完全問題
• ハミルトン経路問題
– グラフにハミルトン経路が存在するか。
• 指定された点から始まり指定された点に終わり、
すべての点をちょうど一回ずつ訪れる経路があるか。
• グラフを適当なアルファベットの文字列として表現する。
• ブール式の充足可能性問題
– ブール式は充足可能か。
• ブール変数の真偽を適当に定めると
ブール式全体を真にできるか。
• ブール式を適当なアルファベットの文字列として表現する。
関数の計算量
• ハミルトン経路問題はＮＰ完全である。
• では、与えられたグラフに対して
ハミルトン経路を求める問題は
どのくらい難しいか？
– もし、ハミルトン経路が
決定的なチューリング機械により、
多項式時間で計算できるならば、
ハミルトン経路があるかどうかが
多項式時間で判定できてしまう。
– 従って、ハミルトン経路の計算も、
多項式ではできないはず。
ＰＳＰＡＣＥ：多項式空間
• 帰納的な言語を認識するチューリング機械が、
停止するまでに、入力文字列の長さの
多項式で抑えられる空間（テープの量）しか
消費しないとき、その言語をＰＳＰＡＣＥという。
• 決定的でも非決定的でも差はない。
• ＮＰを含む。
（真に含むかどうかはわからない。）
Ｐ⊆ＮＰ⊆ＰＳＰＡＣＥ

Download Report