非确定型图灵机 (NTM) 的转移函数为 δ:Q×Γ→P(Q×Γ×{L,R}). 称 NTM M 接受 x, 若在 x 上运行 M 时有接受分支. 称 NTM 是判定的若对所有输入的所有分支都停机. 定理 每个 NTM 都有等价的确定 TM. 定理 每个判定 NTM 都有等价的判定 TM.