非确定性图灵机
在非确定性图灵机中，对于每个状态和符号，TM 可以执行一组操作。因此，这里的转换不是确定性的。非确定性图灵机的计算是可以从起始配置到达的配置树。
如果树中至少有一个节点是接受配置，则输入被接受，否则不被接受。如果计算树的所有分支在所有输入上都停止，则非确定性图灵机称为判定器，如果对于某些输入，所有分支都被拒绝，则该输入也会被拒绝。
非确定性图灵机可以正式定义为 6 元组 (Q、X、∑、δ、q0、B、F)，其中 −
Q 是一组有限的状态
X 是磁带字母表
∑ 是输入字母表
δ 是转换函数；
δ : Q × X → P(Q × X × {Left_shift, Right_shift})。
q0 为初始状态
B 为空白符号
F 为最终状态集
