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

有限オートマトン

有限オートマトン 有限個の状態 入力文字列 状態遷移 現在の状態 初期状態 受理状態 有限個の文字 … アルファベット 入力文字と現在の状態に従って、 現在の状態をかえる。

状態遷移図 二進数を、0と1から 成る文字列として入力し、 3の余りを計算する 有限オートマトン 初期状態 1 1 1

言語 アルファベット 文字列（語） 言語（形式言語） 有限個の文字の集合 Σなどで表す。例：Σ={0,1} アルファベットに属する文字の有限列 例：0, 00, 1100, 0101 空列も文字列。εやλで表す。 文字列の全体をΣ* で表す。 言語（形式言語） 文字列の集合、すなわちΣ* の部分集合。 例：3で割り切れる二進数の全体

言語の認識装置としての 有限オートマトン 状態のいくつかを受理状態とする。 与えられた文字列に従って、 受理状態は複数あってもよい。 与えられた文字列に従って、 初期状態からはじめて状態遷移を繰り返す。 初期状態は一つ。 文字列を読み終わった直後の状態が 受理状態ならば、その文字列を受理。 有限オートマトンMが受理する 文字列の全体をL(M)と書く。 L(M)をMの受理言語という。

有限オートマトン 3で割り切れる二進数の 全体を受理する 有限オートマトン 初期状態 受理状態でもある。 1 1 1

有限オートマトン 初期状態 0と1を 奇数個ずつ 含む文字列を 受理する オートマトン 1 1 1 1

正則表現 言語を表す記法 文字列のパターンを表す。 例：0(10)*1 例：0(11+00)1 例：0(11+00)*1 0で始まり10が繰り返されて1で終わる文字列 そういう文字列からなる言語 例：0(11+00)1 0の次に11または00が来て、1で終わる文字列 例：0(11+00)*1

正則表現から有限オートマトンへ 正則表現⇒有限オートマトン 決定化 最小化 有限オートマトン⇒正則表現 正則言語 任意の正則表現に対して、その言語を受理する 非決定的な有限オートマトンが存在する。 決定化 非決定的な有限オートマトンは、受理言語が同じ 決定的なオートマトンに変換できる。 最小化 決定的なオートマトンは、 受理言語をかえずに状態数が最小化できる。 有限オートマトン⇒正則表現 正則言語

非決定的な有限オートマトン ε遷移： 文字を入力せずに 遷移できる。 ε 初期状態 1 1 1

非決定的な有限オートマトン 受理状態に至る遷移のしかたが 一つでもあればよい。 初期状態 1 1 1 1

決定的な有限オートマトン 初期状態 1 1 1

決定的な有限オートマトン 初期状態 1 1 1 1 1 1

状態数最小の有限オートマトン 初期状態 1 1 1 1 1

有限オートマトンの性質 受理言語の合併、交わり、補集合、連接、 閉包などに関して閉じている。 二つのオートマトンが受理する言語が同じか 任意のM1とM2に対して、 L(M1)∪L(M2)=L(M)となるMが存在する。 二つのオートマトンが受理する言語が同じか どうかを判定することができる。 数を数えられない：有限オートマトンの限界 例えば、0と1を同じ数だけ含む文字列のみを 受理する有限オートマトンは存在しない。

チューリング機械

チューリング機械 ヘッド テープ 有限状態制御部

チューリング機械の動作 有限状態制御部の状態と、 ヘッド上の文字の各組み合わせに対して、 という動作を定義。 ヘッドが書き込む文字（同じ文字をかけば無変化） 次の状態 （文字を書いた後に）ヘッドを 左右のどちらに動かすか、 動かさないか。 という動作を定義。 動作が一通りに定まらないものは、 非決定的なチューリング機械

チューリング機械の停止 停止状態を定めることもある。 次の動作が定義されなかったら停止。 場合によっては、停止しないこともある。

言語の認識装置としての チューリング機械 入力文字列をテープ上に書き込み、 ヘッドを最初の文字の上におき、 状態を初期状態にセットして、 書き込む前は空白文字が埋まっている。 テープには、入力文字列に現れる文字以外の 文字を書き込んでもよい。 入力アルファベット ⊂ テープ・アルファベット ヘッドを最初の文字の上におき、 状態を初期状態にセットして、 機械を走らせる。 停止したら、その文字列を受理。 受理状態において停止したら、 とすることもある。

int[][] nextstate = ...; int[][] chartowrite = ... int[][] nextmove = ...; int[] tape = ...; int state = ...; int head = ...; while (nextstate[state][tape[head]] >= 0) { int c = tape[head]; int s = state; state = nextstate[s][c]; tape[head] = chartowrite[s][c]; head += nextmove[s][c]; }

演習 0と1が同じ数だけ含む文字列のみを 受理するチューリング機械を定義せよ。 そのチューリング機械を、 Javaプログラムによって走らせてみよ。

チューリング機械と計算可能性

言語の認識装置として 入力アルファベット上の言語Lが、 チューリング機械Mによって 認識できるとき、その言語を 帰納的に可算という。 有限時間内にそのことがわかる。 Lに属していないときは、 Mは止まらないかもしれないので、 そのことはいつまでたっても わからないかもしれない。 以上のような認識が、 計算の限界である。 チャーチのテーゼ 入力文字列w 0 1 1 0 1 チューリング 機械 M 受理or不受理 （or非停止） w∈L w∈L

帰納的に可算 vs. 帰納的 入力アルファベット上の言語Lが、 常に停止するチューリング機械 Mによって認識できるとき、 その言語を帰納的いう。 Mを用いれば、与えられた文字列が Lに属しているとき、 有限時間内にそのことがわかる。 Lに属していないときも、 言語Lとその補集合がどちらも 帰納的に可算ならば、 L（およびその補集合）は 帰納的になる。 Mへの入力 0 1 1 0 1 チューリング 機械 M 受理or不受理 （常に停止する） w∈L w∈L

関数の実現機構として チューリング機械を用いて、 文字列をもらって文字列を返す関数を実現できる。 入力文字列をテープ上に書き込み、 チューリング機械を走らせる。 停止したら、テープ上の文字列を返す。 空白は無視する。 チューリング機械は止まらないかもしれないので、 いつも出力が得られるとは限らない。 部分関数 このような関数を部分帰納的関数という。 常に出力が得られるときは、帰納的関数という。 チューリング機械が常に止まる場合。

決定性と非決定性 計算可能性に関して（言語の認識装置として）、 決定的なチューリング機械と 非決定的なチューリング機械に 能力の差はない。 非決定的なチューリング機械が入力文字列を 受理するとは、入力文字列をテープ上に書き込み、 非決定的な動作を適切に選べば、 （受理状態で）停止すること。 任意の非決定的なチューリング機械に対して、 同じ言語を受理する決定的なチューリング機械が 存在する。

非決定的な チューリング機械 M M M 分身を作ると 思えばよい。 分身の一つが 受理すればよい。 M M 0 1 1 0 1 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への入力 万能 チューリング 機械 M 受理or不受理（or非停止） 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年に提示した 七つのミレニアム問題の一つ （賞金１００万ドル）

ＮＰ完全 ＰとＮＰが等しいかどうかはわからないが、 ＰとＮＰが等しくないと仮定すると、 ＮＰ－Ｐに含まれることを示せる問題がある。 ＮＰのうちで最も難しい問題 ＮＰに属する任意の問題は、 多項式ステップでそのような問題に還元できる。 そのような問題をＮＰ完全という。 逆に、ＮＰ完全の問題がＰに属するならば、 ＮＰに属するすべての問題がＰに属する。

ＮＰ完全問題 ハミルトン経路問題 ブール式の充足可能性問題 グラフにハミルトン経路が存在するか。 ブール式は充足可能か。 指定された点から始まり指定された点に終わり、 すべての点をちょうど一回ずつ訪れる経路があるか。 グラフを適当なアルファベットの文字列として表現する。 ブール式の充足可能性問題 ブール式は充足可能か。 ブール変数の真偽を適当に定めると ブール式全体を真にできるか。 ブール式を適当なアルファベットの文字列として表現する。

関数の計算量 ハミルトン経路問題はＮＰ完全である。 では、与えられたグラフに対して ハミルトン経路を求める問題は どのくらい難しいか？ もし、ハミルトン経路が 決定的なチューリング機械により、 多項式時間で計算できるならば、 ハミルトン経路があるかどうかが 多項式時間で判定できてしまう。 従って、ハミルトン経路の計算も、 多項式ではできないはず。

ＰＳＰＡＣＥ：多項式空間 帰納的な言語を認識するチューリング機械が、 停止するまでに、入力文字列の長さの 多項式で抑えられる空間（テープの量）しか 消費しないとき、その言語をＰＳＰＡＣＥという。 決定的でも非決定的でも差はない。 ＮＰを含む。 （真に含むかどうかはわからない。） Ｐ⊆ＮＰ⊆ＰＳＰＡＣＥ