【计算理论】图灵机 ( 非确定性图灵机 -＞ 确定性图灵机 | 模仿过程示例 | 算法的数学模型 )

文章目录

一、非确定性图灵机 -＞ 确定性图灵机

二、确定性图灵机 模仿 非确定性图灵机 过程

三、算法的数学模型

一、非确定性图灵机 -＞ 确定性图灵机

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

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

二、确定性图灵机 模仿 非确定性图灵机 过程

使用 确定性图灵机 描述上述 非确定性图灵机 ;

设计的 确定性图灵机 有 3 33 个带子 , 每个带子对应着 非确定性图灵机 计算树 的一个分支 ;

第 1 11 个带子 ( 输入字符串 ) 上是 图灵机的输入字符串 , 该带子上的内容永不改变 , 不能放其它内容 ;

第 2 22 个带子 ( 模仿带子 ) 上是 模仿的计算树的一个分支的内容 ;

第 3 33 个带子 ( 地址带子 ) 上是数字编码 , 该数字编码会不停的更新 , 该编码代表了计算树中计算分支的编码 ,

下图中 第 3 33 个带子的 123 1 2 3123 含义是 ,

在深度为 1 11 的分支中 , 选择第 1 11 个分支 ,

在深度为 2 22 的分支中 , 选择第 2 22 个分支 ,

在深度为 3 33 的分支中 , 选择第 3 33 个分支 , 如下图所示的分支

第 3 33 个带子是计算分支编码 , 真实的模仿计算分支计算过程在 第 2 22 个带子上完成 ,

带子的数据变化 :

① 第 1 11 个带子放输入字符串 , 永不改变 ;

② 第 2 22 个带子根据 第 3 33 个带子选择的计算分支加载不同的计算分支对应的字符串 ;

③ 第 3 33 个带子上的数字会按照字典序的顺序 , 不停的进行更新 , 更新的过程就是宽度有限搜索的顺序 ;

通过 3 33 个带子中的确定性图灵机 , 可以模仿非确定性图灵机的计算 , 本质是找到非确定图灵机中的接受状态对应的 计算分支 ;

三、算法的数学模型

为算法提供严格的数学模型 , 除了图灵机之外 , 还有其它的 3 33 种数学模型 :

① 可计算函数 ,数学方向 ;

② Lambda 演算 , 程序语言方向 ;

③ 登记计算机 ( Register Machine ) , 计算理论方向 ;