什么是非确定性图灵机？

就像在 PDA（部分 NFA）中一样，非确定性对于一个输入配置可能有多个可能的输出。

非确定性图灵机类似于图灵机，但具有有限数量的移动选择；对于相同的输入“当前状态和当前符号”，可能有多个移动。

如果至少存在一个计算对于输入 w 正常停止，则非确定性图灵机接受输入 w。

对于下推自动机，非确定性比确定性更强大。但对于有限自动机，它没有区别。

令人惊讶的是，确定性和非确定性图灵机的功能相同。

注意

如果一个非确定性图灵机接受语言 L，则存在一个确定性图灵机也接受 L。

还有许多其他类似的机器，它们可能看起来功能更强大或更弱，但可以认为它们的功能与简单的图灵机相同（识别由无限制语法生成的相同的递归可枚举语言）——添加更多磁带、更多控制单元等。

等价性是通过描述如何使用简单的单磁带图灵机来模拟它们，反之亦然来证明的。

更新于： 2021年6月16日

2K+ 阅读量

启动你的 职业生涯

通过完成课程获得认证

开始学习
广告