图灵机的表示有多随意？
图灵机的表示有多随意？
提问于 2010-10-28 03:41:14
我正在处理一个相关的可判断性/可识别性问题，为了解决它，我需要澄清图灵机的编码/表示。
我知道图灵机被正式定义为7元组。如果我有一个图灵机U和另一个图灵机M，设计U来识别M的某些部分(例如M的字母表、输入符号、接受状态集等)是不是很简单？
我的一部分认为，因为这些是有限的集合，所以计算它们是微不足道的，但我也想知道，你是否可以只列举M定义的某一部分，而不是无限循环的可能性。
回答 1
Stack Overflow用户
发布于 2010-10-28 03:48:51
是的，U代表万能图灵机。在http://en.wikipedia.org/wiki/Turing_machine#Universal_Turing_machines上阅读有关它的信息。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4037034
复制相关文章
相似问题
腾讯云开发者
