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

文章目录

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

二、非确定性

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

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

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

非确定性图灵机体现在多个方面 , 如果在下图的 q 1 \rm q_1q

1

 状态时 , 读写头指向 0 00 时 , 有 两个操作 ;

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

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

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

二、非确定性

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

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