【计算理论】图灵机 ( 非确定性图灵机 -＞ 确定性图灵机 | 模仿过程示例 | 算法的数学模型 )
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【计算理论】图灵机 ( 非确定性图灵机 -＞ 确定性图灵机 | 模仿过程示例 | 算法的数学模型 )，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1509字，纯文字阅读大概需要3分钟。
内容图文
文章目录
一、非确定性图灵机 -＞ 确定性图灵机
给定如下非确定性图灵机 , 设计 确定性图灵机 模仿下面的 非确定性图灵机 ;
上述非确定性图灵机 的计算过程是一个 计算树 ;
二、确定性图灵机 模仿 非确定性图灵机 过程
使用 确定性图灵机 描述上述 非确定性图灵机 ;
设计的 确定性图灵机 有 3 3 3 个带子 , 每个带子对应着 非确定性图灵机 计算树 的一个分支 ;
第 1 1 1 个带子 ( 输入字符串 ) 上是 图灵机的输入字符串 , 该带子上的内容永不改变 , 不能放其它内容 ;
第 2 2 2 个带子 ( 模仿带子 ) 上是 模仿的计算树的一个分支的内容 ;
第 3 3 3 个带子 ( 地址带子 ) 上是数字编码 , 该数字编码会不停的更新 , 该编码代表了计算树中计算分支的编码 ,
下图中 第
3
3
3 个带子的
123
1 2 3
123 含义是 ,
在深度为
1
1
1 的分支中 , 选择第
1
1
1 个分支 ,
在深度为
2
2
2 的分支中 , 选择第
2
2
2 个分支 ,
在深度为
3
3
3 的分支中 , 选择第
3
3
3 个分支 , 如下图所示的分支
第 3 3 3 个带子是计算分支编码 , 真实的模仿计算分支计算过程在 第 2 2 2 个带子上完成 ,
带子的数据变化 :
① 第 1 1 1 个带子放输入字符串 , 永不改变 ;
② 第 2 2 2 个带子根据 第 3 3 3 个带子选择的计算分支加载不同的计算分支对应的字符串 ;
③ 第 3 3 3 个带子上的数字会按照字典序的顺序 , 不停的进行更新 , 更新的过程就是宽度有限搜索的顺序 ;
通过 3 3 3 个带子中的确定性图灵机 , 可以模仿非确定性图灵机的计算 , 本质是找到非确定图灵机中的接受状态对应的 计算分支 ;
三、算法的数学模型
为算法提供严格的数学模型 , 除了图灵机之外 , 还有其它的 3 3 3 种数学模型 :
① 可计算函数 ,数学方向 ;
② Lambda 演算 , 程序语言方向 ;
③ 登记计算机 ( Register Machine ) , 计算理论方向 ;
内容总结
以上是互联网集市为您收集整理的【计算理论】图灵机 ( 非确定性图灵机 -＞ 确定性图灵机 | 模仿过程示例 | 算法的数学模型 )全部内容，希望文章能够帮你解决【计算理论】图灵机 ( 非确定性图灵机 -＞ 确定性图灵机 | 模仿过程示例 | 算法的数学模型 )所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。