子图灵完备类计算模型
子图灵完备类计算模型
提问于 2017-05-30 15:32:17
许多编程语言和系统都是图灵完整的，它们可以模拟任何图灵机，因此也可以模拟任何有限状态机。
考虑以下非正式模式：
语言A定义了一组有限的NAND门，它们之间的连接，以及哪些门接收输入，哪些门被输出。
在该模型中，可以建立任何有限状态机。NAND可以形成锁存器、寄存器、总线和控制结构，并最终形成任何有限状态机，包括完整的计算机和其他系统。
然而，该模型无法模拟无限大的磁带，只有有限大小的磁带。它不能模拟任何图灵机，因为它可能没有内存。
语言A和所有其他可以模拟任何有限状态机的系统都被认为是完全的吗？他们是否有一个单独的类，或者有机会定义这样的类？
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-05-30 18:44:26
正如您已经意识到的，有一个层次--具有无限多个级别--的语言类，包括规则语言(由有限自动机识别)和可判定的语言(被图灵机接受)。
所有真正的计算机--包括可以用来构造它们的理论模型，比如你的NAND门--都不是图灵等价的，因为理论上它们不能访问无限大的磁带。在实践中，时间、空间和物质在物理现实中不足以允许真正的图灵-等效计算。所有的物理计算都可以通过有限自动机进行。在实践中，有一些常规语言过于复杂，无法通过构造真正的有限状态机或通用计算机来接受。
建模语言作为一种比常规语言更高的类型是为了方便--它是一个谎言，就像建模是连续的一样(例如，当计算转动惯量时)是一个谎言。物质实际上是由离散的分子组成的，而这些分子又是由较小的离散粒子组成的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44266371
复制相关文章
相似问题
腾讯云开发者
