非決定性チューリングマシンとは、ある状態と読み取った文字から次の状態が一意に決まらず、複数の可能性を同時に分岐して探索できる仮想的な計算モデルです。計算複雑性理論において、P問題とNP問題の定義や比較を行う際の根幹となる重要な概念です。
非決定性チューリングマシンとは
一言でいうと、非決定性チューリングマシンとは「複数の選択肢を同時にすべて試すことができる、理想化された仮想的な計算機モデル」です。
詳しく解説
通常の決定性チューリングマシンは、1つの状態と入力に対して次の動作が1通りに決まります。しかし、非決定性チューリングマシンは、ある状況で複数の有効な次の手が存在する場合、それらのすべての分岐を同時に並行して実行（または正解の道筋を常に選び取る）できると仮定します。現実の物理的なコンピュータとしては実装不可能ですが、計算複雑性理論において「効率的に検証可能な問題」のクラスであるNPを定義するための強力な理論的ツールとして使われています。
具体例・使われ方
例えば、迷路の最短経路やパジャルの正解を見つける場合、通常のコンピュータは考えうるすべてのルートを1つずつ順番に試す必要があります。これに対し、非決定性チューリングマシンはすべてのルートを同時に分岐させて探索するため、実質的に一瞬で正解の経路にたどり着くことができるというイメージです。
似た用語との違い
決定性チューリングマシンとの最大の違いは、状態遷移の決定性です。決定性モデルが1ステップごとに1つの道しか進めないのに対し、非決定性モデルは常に正しい選択肢を直感的に選ぶかのように複数の道を同時に進めます。これにより、計算の複雑さを分類する基準となります。
注意点
非決定性チューリングマシンはあくまで理論上の概念であり、未来を予知したり無制限の並列処理を行ったりする現実のハードウェアが存在するわけではありません。そのため、「非決定性」を「乱数を用いた確率的アルゴリズム」や「量子コンピュータの重ね合わせ」と混同しないよう注意が必要です。