三、非确定性图灵机 与 确定性图灵机 相互模仿
非确定性图灵机 与 确定性图灵机 之间 , 可以进行 互相模仿 ;
非确定性图灵机 与 确定性图灵机 给我们的最初印象是 非确定性图灵机 计算能力要强于 确定性图灵机 ,
非确定性图灵机 的后续操作可以有多个 ,
确定性图灵机 的后续操作只有唯一的一个 ,
但实际上 非确定性图灵机 与 确定性图灵机 的计算能力是等价的 , 它们之间是可以 相互模仿 的 ;
给定一个 非确定性图灵机 , 可以找到一个 确定性图灵机 来模仿它 ,
给定一个 确定性图灵机 , 可以找到一个 非确定性图灵机 来模仿它 ;
四、非确定性图灵机 -> 确定性图灵机
确定性图灵机 可以看成是特殊的 非确定性图灵机 ;
给定一个 非确定性图灵机 , 设计一个 确定性图灵机 来模仿该 非确定性图灵机 ;
给定如下非确定性图灵机 , 设计 确定性图灵机 模仿下面的 非确定性图灵机 ;
确定性图灵机 模仿 非确定性图灵机 思路 :
给定一个 非确定性图灵机 , 给定一个输入字符串 , 在字符串上进行计算 , 得到的 格局 快照 , 形成一个 计算树 , 如下图示例 :
如果设计 确定性图灵机 模仿 非确定性图灵机 的计算过程 , 即计算树 ,
首先模仿 非确定性图灵机 在计算树中的 左侧 深度为 1 11 的计算 , 如下图的红色部分对应的计算过程 ;
然后模仿 非确定性图灵机 在计算树中的 右侧的 深度为 1 11 的计算 , 如下图的蓝色部分对应的计算过程 ;
如果上述两个计算都没有进入接受状态 , 那么继续模仿 深度为 2 22 的计算 , 如下图的红色部分对应的计算过程 ;
如果还没有进入接受状态 , 那么继续模仿另外的深度为 2 22 的计算 , 如下图紫色部分对应的计算 :
如果在所有的 深度为 2 22 的计算中 , 都没有进入接受状态 , 那么继续 模仿深度为 3 33 的计算过程 ;
以此类推 , 直到找到 非确定性图灵机的 接受状态为止 ;
如果中间 出现一次接受状态 , 就让搜索停止下来 , 如果没有就继续模仿 ;
上述的模仿过程是一个 深度优先搜索 过程 ;
非确定性图灵机 转为 确定性图灵机 的计算过程 在最坏的情况下是 深度优先搜索 ,
