非确定性 Turing 机 (NDTM，Aho 书 P364)
一台 k 带 DTM（确定性 Turing 机）根据其当前所在状态及
k 个读写头当前读到的字符唯一地确定下一步的三个动作：
1）改变 q 的状态（也可不改）；
2）改写当前指向各单元的字符（亦可不改）；
3）实现带头的移动（其中若干个甚至全部亦可以不动）；
但三者中至少有一个要发生变化，否则停机。
k 带 Turing 机是由其转移函数：QT
k
→Q(T{L,R,S})
k
而确定。
即（q
i
, a
1
, a
2
,…, a
k
）一旦给定，下一步的三个动作就唯一地确定了。
与 DTM 不同的是，NDTM 的每一步动作允许有若干个选择，
即对于给定的 QT
k
的一个元素（q
i
, a
1
, a
2
,…, a
k
），
它的转移函数值不是对应于一个 Q(T{L,R,S})
k
中的一个元素，
而是对应于 Q(T{L,R,S})
k
中的一个子集。
对于给定的一个输入串，类似于 DTM，NDTM 的格局也可用 ID 描述：
e.g. (
1l
q
i
1r
,
2l
q
i
2r
, ┅ ,
kl
q
i
kr
)
与 DTM 不同的是，DTM 的 ID 序列是线性的:
ID
0
├ ID
1
├ ID
2
├ ┅├ ID
m
，
而 NDTM 的 ID 序列通常是用树来描述的
