对于这个新手问题，我很抱歉，但如果可能的话，我需要一个快速的答案来告诉朋友。
问问题
713 次
3 回答
6
哇。很多回答这个问题归结为决定这样的事情意味着什么。
快速回答是“不”。
您可以解释用某种语言编写的程序。你不能“解释”一个 FSM。您可以做的是让一个 FSM 模仿另一个。FSM 可以以一种微不足道且无趣的方式模仿自己。也可以设置一个 FSM 来模拟另一个比它小的 FSM。一般来说，它不能模拟比它更大的 FSM。它的状态总数太少，无法代表较大 FSM 的状态。
是否可以认为 FSM 以非平凡的方式模拟自身取决于语义。考虑一个生成序列 1,1,1,1 的 FSM。现在看看每秒的输出。这是完全相同的顺序。FSM 重复生成五步序列 1,0,1,1,1 也是如此。解释自己的解释器的有趣行为——你只在不同的尺度上看到完全相同的输出——是存在的。那么这是否使答案“是”？
可以说，这种“分形”属性本身就足以让这样的 FSM 被称为自我模拟器——但不是自我解释器。一个自我解释者，至少对于任何明智的定义来说，必须有更多的魅力。
- 解释语言“HALT”的空解释器不应算作自解释器。语言必须有更多的复杂性。在上面的例子中，我们并没有要求 FSM 做足够的事情。它忽略了它的输入。
- 一个可以解释自己的解释器之所以有趣，是因为它还可以解释用相同语言编写的其他程序，而且改动很小（粗略地说，最小改动意味着只改变一个指向不同程序的指针）。
所以现在的问题。FSM，同样是下推自动机，不能在其输入磁带中后退。如果我们将磁带上的输入符号视为计算机语言中的程序，那么 FSM 和下推自动机都不能成为传统意义上的解释器。
好吧，我们已经知道我们无法使用 FSM 或下推自动机解释图灵完备的语言。比如说，一些更严格的语言可以生成任意长度的重复二进制模式呢？
我们允许三个指令，
- OUT0 - 输出 0
- OUT1 - 输出 1
- RESTART - 回到开头。
我们可以用这种语言为任何程序编写 FSM。这真的很容易。我们不能编写一个 FSM 来解释这种语言的任何程序。
The same is true for a pushdown automaton. Beyond a certain size of sequence it has to use the stack for memory. The problem is that as soon as it reads back from the stack the stack part of the pushdown automaton has forgotten what was there. Meanwhile the FSM part can only store a sequence of limited size.
A push down automaton and an FSM cannot interpret the simple three instruction language. If a fixed FSM or a pushdown automaton is able to execute arbitrary programs in some language, that language must be not only not Turing complete, it has to be simpler than the one given. That's so restrictive that it's legitimate to say that FSMs and pushdown automata cannot be self-interpreting.
于 2011-03-13T14:15:35.307 回答
2
FSM = 会飞的意大利面怪物？
您可以编写一个自我解释的图灵机，但 FSM 不是图灵完整的（据我所知），因此我认为答案是否定的，您不能。
于 2011-03-05T17:30:17.680 回答
0
于 2011-03-05T17:32:09.180 回答