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

非決定性チューリングマシンでは、すべての状態とシンボルに対して、TMが実行できるアクションのグループがあります。したがって、ここでは遷移は決定論的ではありません。非決定性チューリングマシンの計算は、開始構成から到達できる構成のツリーです。

受け入れ構成であるツリーのノードが少なくとも1つある場合、入力は受け入れられます。それ以外の場合、入力は受け入れられません。計算木のすべての分岐がすべての入力で停止する場合、非決定性チューリングマシンはDecider また、一部の入力について、すべてのブランチが拒否された場合、入力も拒否されます。

非決定性チューリングマシンは、正式には6タプル（Q、X、∑、δ、q ₀、B、F）として定義できます。