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

Question

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

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

Answer 1

如果我正确理解了您的问题，那么您说的是带有磁带的类图灵机，该磁带仅限于最终字母表的某些恒定长度（在您的问题 1000 中）元素。磁带的长度不取决于输入大小（线性有界自动机就是这种情况）。

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

• 另外，图灵机有一些内部状态（假设这些状态的数量是S）。在每一点机器都有一些内部状态和磁带的一些状态，因此我们可以使用普通的有限状态机来模拟具有恒定长度磁带的图灵机。

• 要构建有限状态机，您需要获取有限图灵机的所有可能状态。这是机器内部状态（其中有S）和磁带状态（其中有 A ^T）的组合，因此您最终会得到一个具有S*A ^T状态的有限状态机。这是相当多的，但理论上我们并不关心 - 它是一个常数。

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

Answer 2

我认为您所描述的更接近线性有界自动机而不是图灵机。LBA 可以识别上下文相关的语言。

Answer 3

直觉上，我认为您有限的机器可以识别图灵可识别语言的严格子集。为了证明这一点，您需要构建一种图灵可识别的语言，以便识别该语言的最有效图灵机需要在其磁带上超过 1000 个位置。

Answer 4

根据定义，具有非无限磁带（对于相当小的无限值）的“类图灵机”不是“图灵机”。

在实践中，这样一台有限的机器将很难计算任何感兴趣的函数。