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

非決定性チューリングマシンは、現在の状態とテープから読み取った記号に対して、次に行うべき動作の候補が一つに限定されず、複数の遷移先を同時に、あるいは選択的に探索することを許容する仮想的な計算モデルのことです。

これは、計算理論の生みの親であるアラン・チューリングが提唱した決定性チューリングマシン（DTM）を拡張した概念であり、特定の入力に対して複数の計算経路を「並列的」にたどる能力を持つ、計算複雑性理論において極めて重要な役割を果たす理論上の機械です。

非決定性チューリングマシンの仕組みと決定性モデルとの違い

決定性チューリングマシン（DTM）が、一つの状態と一つの記号に対して次に取るべき行動が常に一意に決まる「一本道」の計算を行うのに対し、非決定性チューリングマシン（NTM）は、木構造のように分岐する「複数の道」を同時に探索するイメージで動作します。

1. 遷移関数の定義

数学的な観点では、決定性モデルと非決定性モデルの最大の違いは遷移関数にあります。NTMの遷移関数は、状態と記号の組み合わせに対して、可能性のある次の動作（新しい状態、書き込む記号、ヘッドの移動方向）の「集合」を返します。

遷移関数は以下のように表現されます。

ここで、Qは状態の集合、Γはテープ記号の集合、{L, R}はヘッドの移動方向、そして

はべき集合（すべての部分集合の集合）を指します。つまり、一つの入力に対して、複数の遷移先の選択肢が許されていることを意味します。

2. 受理の条件

NTMがある入力を受理（正解と判定）するための条件は、枝分かれした膨大な計算経路のうち、少なくとも一つの経路が「受理状態」に到達することです。他の無数の経路が拒絶状態に陥ったり、無限ループに陥ったりしても、一つでも成功する経路があれば、そのマシンはその入力を受理したとみなされます。

理論的な計算能力の等価性

非決定性チューリングマシンは、その「魔法のような並列性」から決定性モデルよりも強力であるように思われがちですが、計算可能性（解けるか解けないか）という観点では、決定性チューリングマシンと完全に等価です。

1. DTMによるシミュレーション

任意のNTMは、決定性チューリングマシン（DTM）によってシミュレーションすることが可能です。具体的には、NTMのすべての計算経路を幅優先探索などで一つずつ順番に調べていくことで、DTMでも同じ結果を得ることができます。

2. 効率性の違い

計算可能性は同じでも、計算にかかる「時間（ステップ数）」には大きな差が生じます。NTMで多項式時間で解ける問題であっても、それを決定性マシンでシミュレートしようとすると、経路の数が指数関数的に増加するため、膨大な時間を要することになります。

計算複雑性理論における重要性（P対NP問題）

非決定性チューリングマシンの概念は、現代の計算機科学における最大の未解決問題の一つである「P対NP問題」の定義そのものに関わっています。

1. クラスNPの定義

NP（Nondeterministic Polynomial time）とは、非決定性チューリングマシンを用いることで、入力の長さに対して多項式時間で解くことができる問題のクラスを指します。

2. 指数時間への挑戦

もし、NTMで多項式時間で解けるすべての問題が、決定性マシン（DTM）でも多項式時間で解ける（P = NP）と証明されれば、現在「解くのが難しい」とされている暗号技術などの前提が根底から覆ることになります。

非決定性チューリングマシンは、物理的な実機として構築することは困難ですが、人間の知性が「可能性を探索する」プロセスを数学的に厳密にモデル化したものであり、アルゴリズムの限界を知る上で欠かせない指標となっています。

関連用語

お問い合わせ

システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。