非确定型图灵机

如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为

\delta :Q\times \Gamma \to 2^{Q\times \Gamma \times \{L,R\}}

其中 $Q$ 是状态集合， $\Gamma$ 是带字母表， $L,R$ 分别表示读写头向左和向右移动；符号 $2^{A}$ 表示集合 $A$ 的幂集，即

2^{A}=\{S~|~S\subseteq A\}

例如，设非确定型图灵机 $M$ 的当前状态为 $q$ ，当前读写头所读的符号为 $x$ ，若

\delta (q,x)=\{(q_{1},x_{1},d_{1}),(q_{2},x_{2},d_{2}),\ldots ,(q_{k},x_{k},d_{k})\}

则 $M$ 将任意地选择一个 $(q_{i},x_{i},d_{i})$ ，按其进行操作，然后进入下一步计算。

非确定型图灵机 $M$ 在输入串 $\omega$ 上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称 $M$ 接受 $\omega$ ；只要有任意一个分支进入拒绝状态，则称 $M$ 拒绝 $\omega$ ；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说 $M$ 在输入 $\omega$ 上可停机。注意，我们规定 $M$ 必须是无矛盾的，即它不能有某个分支接受 $\omega$ 而同时另一个分支拒绝 $\omega$ ，这样有矛盾的非确定型图灵机是不合法的。