是否可以编写自解释FSM或下推自动机？

Question

我很抱歉这个新手问题,但我需要快速回答,告诉朋友是否可能.

Answer 1

哇.很多回答这个问题归结为决定这样的事情意味着什么.

快速回答是"不".

您可以解释用某种语言编写的程序.你无法"解释"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.

下推式自动机也是如此.超过一定大小的序列,它必须使用堆栈作为内存.问题是,只要它从堆栈中读回来,下推自动机的堆栈部分就会忘记那里有什么.同时,FSM部分只能存储有限大小的序列.

下推自动机和FSM无法解释简单的三种指令语言.如果固定的FSM或下推自动机能够以某种语言执行任意程序,那么该语言不仅必须不是图灵完整的,它必须比给定的更简单.这是如此限制,以至于说FSM和下推自动机不能自我解释是合理的.