非決定性チューリングマシン
通常の(決定性)チューリング機械(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 全体が入力を受理したと言える。