非确定性图灵机

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

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

非确定性图灵机可以正式定义为 6 元组 (Q, X, Σ, δ, q 0 , B, F)，其中 -

  • Q是有限状态集

  • X是磁带字母表

  • Σ是输入字母表

  • δ是过渡函数；

    δ : Q × X → P(Q × X × {左移，右移})。

  • q 0是初始状态

  • B是空白符号

  • F是最终状态的集合