非決定性チューリングマシン
直観的に NTM は、考えられる計算を同時並行的に行え、そのうち1つが成功すればよいのだから、DTM より強力であると思われるかもしれない。しかし、NTM が認識可能な言語は全て DTM でも認識可能である。DTM は NTM での遷移の分岐ごとに複製を作り、マルチタスクのような方法でそれらを並列にシミュレートできる。
このようなシミュレーションが NTM に比較して非常に時間がかかることは明らかである。一般にどれだけ長くかかるかは不明であり、これはP≠NP予想の問題と根本的には同じである。
非決定性チューリング機械(ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM)は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。