有限图灵机中自然和可识别语言的映射

Question

我一直在努力寻找这个理论问题的答案，即使它不是直接的编程问题，我相信它确实是相关的。

假设一种图灵机不能超过 1000 个方格。这种类型的可识别语言的集合与正常可识别语言的集合之间是什么关系。

Answer 1

如果我正确理解了您的问题，那么您在谈论的是图灵式机器，其带子被限制为最后一个字母的一定的恒定长度(在您的问题1000中)。磁带的长度不取决于输入的大小(线性有边界的自动装箱就是这种情况)。

在这种情况下，您可以由磁带表示的状态数是恒定的。更具体地说，如果磁带的长度是 T 并且字母表的大小是 A，那么磁带只能编码 AT 状态。

另外，图灵机有一些内部状态(假设这些状态的数量是 S)。在每个点，机器都有一些内部状态和磁带的一些状态，因此我们可以使用普通的有限状态机模拟带有等长磁带的图灵机。

要构造有限状态机，您需要获取有限的图灵机的所有可能状态。这是机器内部状态(它们中有S)和磁带状态(它们中的AT)的组合，因此最终得到的是具有S * AT状态的有限状态机。这是相当多的，但我们在理论上并不关心它——它是一个常数。

所以，我的回答是，您有限的恒定磁带图灵机可以识别与有限状态机相同的语言。