チューリング機械と計算可能性 言語の認識装置として • 入力アルファベット上の言語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年に提示した 七つのミレニアム問題の一つ （賞金１００万ドル） ＮＰ完全 • ＰとＮＰが等しいかどうかはわからないが、 ＰとＮＰが等しくないと仮定すると、 ＮＰ－Ｐに含まれることを示せる問題がある。 – ＮＰのうちで最も難しい問題 – ＮＰに属する任意の問題は、 多項式ステップでそのような問題に還元できる。 – そのような問題をＮＰ完全という。 – 逆に、ＮＰ完全の問題がＰに属するならば、 ＮＰに属するすべての問題がＰに属する。 ＮＰ完全問題 • ハミルトン経路問題 – グラフにハミルトン経路が存在するか。 • 指定された点から始まり指定された点に終わり、 すべての点をちょうど一回ずつ訪れる経路があるか。 • グラフを適当なアルファベットの文字列として表現する。 • ブール式の充足可能性問題 – ブール式は充足可能か。 • ブール変数の真偽を適当に定めると ブール式全体を真にできるか。 • ブール式を適当なアルファベットの文字列として表現する。 関数の計算量 • ハミルトン経路問題はＮＰ完全である。 • では、与えられたグラフに対して ハミルトン経路を求める問題は どのくらい難しいか？ – もし、ハミルトン経路が 決定的なチューリング機械により、 多項式時間で計算できるならば、 ハミルトン経路があるかどうかが 多項式時間で判定できてしまう。 – 従って、ハミルトン経路の計算も、 多項式ではできないはず。 ＰＳＰＡＣＥ：多項式空間 • 帰納的な言語を認識するチューリング機械が、 停止するまでに、入力文字列の長さの 多項式で抑えられる空間（テープの量）しか 消費しないとき、その言語をＰＳＰＡＣＥという。 • 決定的でも非決定的でも差はない。 • ＮＰを含む。 （真に含むかどうかはわからない。） Ｐ⊆ＮＰ⊆ＰＳＰＡＣＥ
© Copyright 2024 ExpyDoc
