非決定論的チューリングマシン

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

受け入れ構成であるツリーのノードが少なくとも1つある場合、入力は受け入れられます。それ以外の場合、入力は受け入れられません。計算ツリーのすべてのブランチがすべての入力で停止した場合、非決定的チューリングマシンは*デサイダー*と呼ばれ、一部の入力ですべてのブランチが拒否された場合、入力も拒否されます。

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