有限图灵机中自然语言和可识别语言的映射
我一直在努力寻找这个理论问题的答案，即使它不是直接的编程问题，但我相信它确实相关。
假设一种图灵机不能超过 1000 个方格。此类可识别语言的集合与普通可识别语言的集合之间的关系是什么？
I have been struggling to find an answer to this theoretical question, even tho it is not directly a programming question, I believe it is really related.
Assume a type of Turing machine which cannot have more than 1000 squares. What would be the relationship between the set of such type of recognizable languages and set of normal recognizable languages.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果我正确理解你的问题，你正在谈论类似图灵机的磁带，该磁带仅限于最终字母表的某些恒定长度（在你的问题中为 1000 个）元素。胶带的长度不取决于输入大小（线性有界自动机就是这种情况）。
在这种情况下，磁带可以表示的状态数是恒定的。更具体地说，如果磁带的长度为 T 并且字母表的大小为 A，则磁带只能编码 AT 状态。
此外，图灵机还有一些内部状态（假设这些状态的数量为S）。在每个点，机器都有一些内部状态和磁带的一些状态，因此我们可以使用普通的有限状态机来模拟具有恒定长度磁带的图灵机。
要构造有限状态机，您需要获取有限图灵机的所有可能状态。这是机器内部状态（其中 S）和磁带状态（其中AT）的组合，因此最终得到一个具有 S*AT 状态的有限状态机。这是相当多的，但我们在理论上并不关心它 - 它是一个常数。
所以，我的答案是，有限的恒定磁带图灵机可以识别与有限状态机相同的语言。
If I understand your question correctly, you're talking about Turing-like machine with a tape that is limited to some constant legnth (in your question 1000) elements of a final alphabet. The length of the tape doesn't depend on the input size (which would be the case for Linear Bounded Automoton).
In this scenario, the number of states that you can represent by the tape is constant. More specifically, if the length of the tape is T and the size of the alphabet is A then the tape can encode only AT states.
Additionaly, the Turing machine has some internal states (let's say that the number of these states is S). At each point the machine has some internal state and some state of the tape, so we can simulate the Turing machine with constant-length tape using an ordinary finite state machine.
To construct the finite state machine, you'll need to take all possible states of your limited Turing-machine. This is a combination of internal states of the machine (there is S of them) and the states of the tape (AT of them), so you end up with a finite state machine with S*AT states. That's quite a lot, but we don't care about that in theory - it is a constant.
So, my answer is that your limited constant-tape Turing machine can recognize the same languages as a finitie-state machine.
我认为你所描述的更接近线性有界自动机而不是图灵机。 LBA 可以识别上下文相关语言。
I think that what you are describing is more close to a Linear Bounded Automoton than to a Turing Machine. An LBA can recognize context-sensitive languages.
直觉上，我认为有限的机器可以识别图灵可识别语言的严格子集。为了证明这一点，您需要构建一种图灵可识别的语言，以便识别该语言的最高效图灵机需要其磁带上有 1000 多个位置。
Intuitively, I would think that your limited machines could recognize a strict subset of turing-recognizable languages. To prove that, you'd need to construct a turing-recognizable language such that the most efficient turing machine that recognizes the language requires more than 1000 positions on its tape.
根据定义，具有非无限磁带（对于相当小的无穷大值）的“类图灵机”不是“图灵机”。
在实践中，这种有限的机器将很难计算任何感兴趣的函数。
By definition, a "turing-like machine" with a non-infinite tape (for reasonably small values of infinity) isn't a "turing machine".
In practice, such a limited machine would be hard pressed to compute functions of any interest.