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

非決定性チューリング機械（ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。 == 概要 == 通常の（決定性）チューリング機械（DTM）の遷移機構は、現在状態とテープ上のヘッドの現在位置にある記号によって次の3つの動作をする。