我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:主页 > 杜林机图灵机 >

图灵机的变体

归档日期:06-28       文本归类:杜林机图灵机      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  图灵机有很多变种,但可以证明这些变种的计算能力都是等价的,即它们识别同样的语言类。证明两个计算模型 A 和 B 的计算能力等价的基本思想是:用 A 和 B 相互模拟, 若 A 可模拟 B 且 B 可模拟 A, 显然他们的计算能力等价。注意这里我们暂时不考虑计算的效率,只考虑计算的理论上“可行性”。

  首先我们可以发现,改变图灵机的带字母表并不会改变其计算能力。例如我们可以限制图灵机 的带字母表为 {0,1},这并不会改变图灵机的计算能力,因为我们显然可以用带字母表为 {0,1} 的图灵机模拟带字母表为任意有限集合 Γ 的图灵机。

  另一个要注意的是,如果我们允许图灵机的纸带两端都可以无限伸展,这并不能增加图灵机的计 算能力,因为我们显然可以用只有纸带一端能无限伸展的图灵机来模拟这种纸带两端都可以无限 伸展的图灵机。

  如果我们允许图灵机的读写头在某一步保持原地不动,那也不会增加其计算能力,因为我们可以用 向左移动一次再向右移动一次来代替在原地不动。

本文链接:http://auxloisirs.com/dulinjitulingji/451.html