非決定性チューリングマシン
この定義には様々なバリエーションが存在する。初期状態が1つではなく集合となっている場合もある。なお、初期状態が複数存在するものは、1つの初期状態から非決定的に複数の状態に分岐すると考えることで元の定義と等価であることがわかる。
バリエーションには、不受理状態の集合を持つものもある。この場合、全経路が不受理状態に到達すると、NTM は入力を不受理とする。