非決定性チューリングマシン

非決定性チューリング機械（ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。

概要

通常の（決定性）チューリング機械（DTM）の遷移機構は、現在状態とテープ上のヘッドの現在位置にある記号によって次の3つの動作をする。(1)テープに記号を書き込む。(2)右または左にヘッドを移動させる。(3)新たな状態をとる。例えば、テープ上に X があって状態番号 3 であった場合、DTM は Y をテープに書き込み、ヘッドを右に移動させ、状態番号 5 に遷移する、といった具合である。

NTM が異なるのは、状態とテープ上の記号によって、すべきことがユニークに指定されないという点である。同じ状態と記号の組合せであっても、様々な動作をする可能性がある。例えば、テープ上に X があって状態番号 3 であるとき、NTM は Y を書き込んで右に移動して状態番号 5 となるかもしれないし、X を書き込んで左に移動して状態番号 3 のままとなるかもしれない。

NTM はこのような動作のうちどれを実行すべきかをどうやって「知る」のだろうか? これには2つの考え方がある。第一に非決定性チューリング機械は「最も幸運な推測機; luckiest possible guesser」であるとする考え方である。NTM は受理状態に到達することがあるならその状態に最終的に到達するような状態を常に選択して遷移する。第二に非決定性チューリング機械は多数の複製に分岐し、それぞれがとりうる遷移のいずれかを実行するとする考え方である。DTM には計算経路が1つしかないが、NTM には一種の計算の木構造が存在する。その木構造の一つの枝で受理状態で停止したとき、NTM 全体が入力を受理したと言える。

定義

形式的には、非決定性チューリング機械は6タプル $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ で表され、以下のような意味を持つ。

$Q$ は状態群の有限な集合である。
$\Sigma$ は記号群（テープ上のアルファベット）の有限な集合である。
$\iota \in Q$ は初期状態である。
$\sqcup$ は空記号である ( $\sqcup \in \Sigma$ )。
$A\subseteq Q$ は受理状態の集合である。
$\delta :Q\backslash A\times \Sigma \rightarrow \left(Q\times \Sigma \times \{L,R\}\right)$ は遷移関数であり、状態と記号に関する多価関数である。ここで、L はテープヘッドの左シフト、R は右シフトを表す。普通のチューリング機械では遷移関数は多価ではない。

バリエーション

この定義には様々なバリエーションが存在する。初期状態が1つではなく集合となっている場合もある。なお、初期状態が複数存在するものは、1つの初期状態から非決定的に複数の状態に分岐すると考えることで元の定義と等価であることがわかる。

バリエーションには、不受理状態の集合を持つものもある。この場合、全経路が不受理状態に到達すると、NTM は入力を不受理とする。

決定性チューリング機械との等価性

直観的に NTM は、考えられる計算を同時並行的に行え、そのうち1つが成功すればよいのだから、DTM より強力であると思われるかもしれない。しかし、NTM が認識可能な言語は全て DTM でも認識可能である。DTM は NTM での遷移の分岐ごとに複製を作り、マルチタスクのような方法でそれらを並列にシミュレートできる。

このようなシミュレーションが NTM に比較して非常に時間がかかることは明らかである。一般にどれだけ長くかかるかは不明であり、これはP≠NP予想の問題と根本的には同じである。

制限された非決定性

NTM は制限された非決定性を持つ。すなわち NTM がある入力テープ T について必ず停止するとき、有限のステップ数の後に停止するのであり、考えられる構成の数は有限である。

量子コンピュータとの比較

量子コンピュータが NTM であるということをよく言われるが、これは間違っている。多項式時間の量子コンピュータの能力は多項式時間の NTM よりも低いと考えられている。つまり、これらのモデルについて、一方で解けるが、もう一方では解けないという問題が存在する。NTM で解けて量子コンピュータで解けないと予想される問題の例としてNP完全問題がある。

参考文献

Harry R. Lewis, Christos Papadimitriou (1981年). Elements of the Theory of Computation (1st edition ed.). Prentice-Hall. ISBN 0-13-273417-6 Section 4.6: Nondeterministic Turing machines, pp.204–211.
John C. Martin (1997年). Introduction to Languages and the Theory of Computation (2nd edition ed.). McGraw-Hill. ISBN 0-07-040845-9 Section 9.6: Nondeterministic Turing machines, pp.277–281.
Christos Papadimitriou (1993年). Computational Complexity (1st edition ed.). Addison-Wesley. ISBN 0-201-53082-1 Section 2.7: Nondeterministic machines, pp.45–50.

外部リンク

C++ Simulator of a Nondeterministic Multitape Turing Machine （フリーソフトウェア）

概要

定義