为什么有有限数量的图灵机？
为什么有有限数量的图灵机？
提问于 2013-04-09 22:48:16
在Michael对计算理论的介绍中，他说：
“有些语言是不可分辨的，甚至是图灵可识别的，原因是有无数种语言，但只有可数的图灵机。因为每台图灵机都能识别一种语言，而且比图灵机多语言，所以有些语言不能被图灵机识别”(178)。
图灵机不是一台可以模拟任何计算机算法的假想机器吗？理论上你不是可以想出无限多的算法吗？我很难理解这个概念。一个“解释就像我是5”的回答是非常感谢的，但当然，任何帮助总比没有好。
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-04-09 22:54:06
图灵机的数目是可数的。这并不意味着有一个有限的数字。图灵机的集合是可数无限的，这意味着图灵机可以用自然数来编号。也就是说，你可以在自然数和图灵机器之间创建一个1比1的映射。
Stack Overflow用户
发布于 2022-11-05 11:51:44
我想有无限数量的图灵机，即使是具有相同功能的机器。例如，图灵机M是乘法算法的一个实现，即给定两个整数，例如5和6，它输出乘积30。然后，只需在执行过程中添加无用的操作，就可以将M转换为另一个图灵机M‘。也可以在字母表中添加无用的状态、转换表项或符号。最后，您得到一个不同的图灵机M'，但它的功能与M重复这个过程相同，您可能会得到无限数量的图灵机。
提醒我们可以通过添加注释或无用的语句来使源代码有所不同。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15913898
复制相关文章
相似问题
腾讯云开发者
