形式陈述

非确定性图灵机的转移是从当前配置到有限多个后继配置的关系。输入被接受，当且仅当计算树中存在一条有限分支到达接受状态；所有分支拒绝或无限运行则不构成接受。对语言可识别性和可判定性，NTM 与确定性 TM 等价：确定性机器可按广度优先交错模拟整棵有限分支计算树。复杂性中则以最短接受分支的步数定义 NTime，并产生 NP 等重要类别。

直觉

非确定性不是随机选择，也不是物理上免费并行；它是一种存在量词语义：“是否存在一串合法选择使验证成功”。确定性模拟必须系统搜索所有选择。

例子与边界

对 SAT，NTM 可猜一个赋值并在线性于公式大小的时间内验证。若只沿深度优先的一条分支模拟，可能陷入无限路径而错过另一条接受分支，因此可识别性等价证明使用分层交错。拒绝通常要求没有接受分支，而不是存在一条拒绝分支。NTM 不会扩展可计算函数的集合，但可能把已知确定性运行时间显著缩短。

推论与应用

NTM 为 NP、NPSPACE 和证书验证提供统一模型，也把组合搜索中的“猜测—验证”模式转化为精确复杂性定义。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1936，Full paper。