Automata Theory 简明教程

在非确定图灵机中，对于每个状态和符号，TM 有一组操作。因此，这里的转换不是确定的。非确定图灵机的计算是从开始配置可以到达的一系列配置树。

如果树至少有一个节点是接受配置，则接受输入，否则不接受。如果计算树的所有分支在所有输入上停止，则非确定图灵机被称为 Decider ，如果对于某个输入，所有分支都被拒绝，则输入也被拒绝。

一个非确定图灵机可以形式地定义为一个 6 元组 (Q, X, ∑, δ, q0, B, F)，其中 -