【计算理论】图灵机 ( 非确定性图灵机 与 计算树 | 非确定性 | 非确定性图灵机 与 确定性图灵机 相互模仿 | 非确定性图灵机 -＞ 确定性图灵机 )

文章目录

• 一、非确定性图灵机 与 计算树
• 二、非确定性
• 三、非确定性图灵机 与 确定性图灵机 相互模仿
• 四、非确定性图灵机 -> 确定性图灵机

一、非确定性图灵机 与 计算树

非确定性图灵机体现在多个方面 , 如果在下图的

状态时 , 读写头指向

时 , 有 两个操作 ;

确定性图灵机中 , 单个状态下 , 读取确定的字符时 , 只允许有一条对应的指令 , 不能出现多个后继状态 ;

非确定性图灵机 的计算过程是一个 计算树 ;

计算树 在计算机科学中 , 是一个很重要的数据结构 , 算法的计算复杂度主要是根据计算树进行分析的 ;

二、非确定性

非确定性图灵机的优势是 , 给图灵机设计带来了很多方便 , 给定一个计算问题 , 如果可以找到一个图灵机来认识该计算问题 , 如果要 设计一个非确定性图灵机很容易 , 设计确定性图灵机 , 难度很大 ;

非确定性 在 计算理论中 , 是 搜索 和 猜测 的代名词 ;

三、非确定性图灵机 与 确定性图灵机 相互模仿

非确定性图灵机 与 确定性图灵机 之间 , 可以进行 互相模仿 ;

非确定性图灵机 与 确定性图灵机 给我们的最初印象是 非确定性图灵机 计算能力要强于 确定性图灵机 ,

非确定性图灵机 的后续操作可以有多个 ,

确定性图灵机 的后续操作只有唯一的一个 ,

但实际上 非确定性图灵机 与 确定性图灵机 的计算能力是等价的 , 它们之间是可以 相互模仿 的 ;

给定一个 非确定性图灵机 , 可以找到一个 确定性图灵机 来模仿它 ,

给定一个 确定性图灵机 , 可以找到一个 非确定性图灵机 来模仿它 ;

四、非确定性图灵机 -> 确定性图灵机

确定性图灵机 可以看成是特殊的 非确定性图灵机 ;

给定一个 非确定性图灵机 , 设计一个 确定性图灵机 来模仿该 非确定性图灵机 ;

给定如下非确定性图灵机 , 设计 确定性图灵机 模仿下面的 非确定性图灵机 ;

确定性图灵机 模仿 非确定性图灵机 思路 :

给定一个 非确定性图灵机 , 给定一个输入字符串 , 在字符串上进行计算 , 得到的 格局 快照 , 形成一个 计算树 , 如下图示例 :

如果设计 确定性图灵机 模仿 非确定性图灵机 的计算过程 , 即计算树 ,

首先模仿 非确定性图灵机 在计算树中的 左侧 深度为

的计算 , 如下图的红色部分对应的计算过程 ;

然后模仿 非确定性图灵机 在计算树中的 右侧的 深度为

的计算 , 如下图的蓝色部分对应的计算过程 ;

如果上述两个计算都没有进入接受状态 , 那么继续模仿 深度为

的计算 , 如下图的红色部分对应的计算过程 ;

如果还没有进入接受状态 , 那么继续模仿另外的深度为

的计算 , 如下图紫色部分对应的计算 :

如果在所有的 深度为

的计算中 , 都没有进入接受状态 , 那么继续 模仿深度为

的计算过程 ;

以此类推 , 直到找到 非确定性图灵机的 接受状态为止 ;

如果中间 出现一次接受状态 , 就让搜索停止下来 , 如果没有就继续模仿 ;

上述的模仿过程是一个 深度优先搜索 过程 ;

非确定性图灵机 转为 确定性图灵机 的计算过程 在最坏的情况下是 深度优先搜索 ,