Question

在3.4 节中，我们看到非确定性没有让有限自动机有什么不同，而4.2.2 节表明一台非确定性的下推自动机比一台确定性的能多做一些事情，这留给我们一个明显的关于图灵机的问题：增加不确定性2会使一台图灵机更强大吗？

2对于一台图灵机，“不确定性”意味着每个状态和字符的组合会允许多于一个的规则，因此从一个起始配置开始会有多个可能的执行路径。

答案是不会：一台非确定型图灵机并不能比一台确定型图灵机多做任何事情。下推自动机一个状态能用来表示许多状态的组合，而图灵机的一条纸带能用来存储许多纸带的内容，但一个下推自动机的栈无法同时表示多个可能的栈。

因此，就像有限自动机一样，一台确定型图灵机可以模拟一台非确定型图灵机。使用纸带存储由图灵机配置适当编码后组成的一个队列，每一个配置都包含一个可能的当前状态和所模拟机器的纸带，模拟就靠它运行。模拟开始的时候，纸带上只存有一个配置，它表示所模拟机器的初始配置。模拟计算的每一步执行都是先读取队列前面的配置，找到能用的每一个规则，并使用这个规则生成新的配置，再把配置写回纸带放到队尾。一旦对每一个规则都这样做了，最前面的配置会被擦除，然后会再次对队列中的下一个配置进行处理。

这个机器模拟的步骤会一直重复，直到队列前面的配置表示机器已经到达接受状态为止。这个技术允许确定型图灵机按照广度优先的顺序探索被模拟机器的所有可能配置。如果对于非确定型图灵机来说存在一条执行路径到达一个接受状态，模拟就会找到它，就算其他路径会导致无限循环也没有关系。实际上把这个模拟实现为一个规则手册要求大量的细节，因此我们不会在这里进行尝试，但能够用确定型图灵机模拟就意味着我们不能仅仅通过增加非确定性就让一台图灵机更强大。