文章目录

• 一、非确定性图灵机 -＞ 确定性图灵机
• 二、确定性图灵机 模仿 非确定性图灵机 过程
• 三、算法的数学模型

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

---

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

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

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

---

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

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

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

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

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

下图中 第 $3$ 个带子的 $123$ 含义是 ,
在深度为 $1$ 的分支中 , 选择第 $1$ 个分支 ,
在深度为 $2$ 的分支中 , 选择第 $2$ 个分支 ,
在深度为 $3$ 的分支中 , 选择第 $3$ 个分支 , 如下图所示的分支

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

带子的数据变化 :

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

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

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

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

三、算法的数学模型

---

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

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

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

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

总结

以上是生活随笔为你收集整理的【计算理论】图灵机 ( 非确定性图灵机 -＞ 确定性图灵机 | 模仿过程示例 | 算法的数学模型 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。