是否可以編寫自解釋的FSM或下推自動機？

6

哇。很多回答這個問題歸結爲決定這樣的事情意味着什麼。

快速回答是「否」。

可以解釋程序寫在語言。你不能'解釋'FSM。你可以做的是讓一個FSM模擬另一個。以一種微不足道的，無趣的方式，FSM可以模擬自己。還可以設置FSM來模擬另一個比它小的FSM。一般來說，它不能模擬比它大的FSM。它的狀態總數太少，不足以代表更大的密克羅尼西亞聯邦的狀態。

是否FSM可以考慮模仿本身在不平凡的方式下降到語義。考慮產生序列1,1,1,1的FSM。現在看看每個第二個輸出。這是完全一樣的順序。 FSM同樣可以重複產生1,0,1,1,1五個步驟序列。解釋自己的解釋器的有趣行爲 - 即你看到的只是不同規模的完全相同的輸出 - 是存在的。那麼這樣做的答案是「是」？

「分形」屬性本身就足以證明這樣的FSM被稱爲自我模擬器 - 但不是自我解釋器。一個自我解釋者，至少對於任何明智的定義，都必須有更多的榮譽。

空解釋器解釋語言「停止」應該不算作爲自我解釋。語言必須具有更多的複雜性。在上面的例子中，我們並沒有要求FSM做足夠的事情。它忽略了它的輸入。
一個可以解釋自己的解釋器只是一個有趣的東西，因爲它也可以解釋其他程序以相同的語言寫成，並且變化很小（粗略地說，最小改變意味着只改變一個指向不同程序的指針）。

所以，現在的問題。一個FSM，同樣也是一個下推式自動機，不能在其輸入磁帶中倒退。如果我們將磁帶上的輸入符號當作計算機語言中的程序來考慮，那麼無論是FSM還是下推自動機都不能作爲傳統意義上的解釋器。嗯，我們已經知道我們不能使用FSM或下推自動機來解釋圖靈完成的語言。那麼一些更具限制性的語言會怎樣產生一個任意長度的重複二進制模式呢？

我們允許三個指令，

OUT0 - 輸出0
OUT1 - 輸出1個
RESTART - 又回到了起點。

我們可以爲此語言的任何程序編寫一個FSM。這真的很容易。我們不能編寫一個可以用這種語言解釋任何程序的FSM。

下推自動機也是如此。除了一定大小的序列之外，它必須使用堆棧來存儲內存。問題是，只要它從堆棧中讀回，下推自動機的堆棧部分就忘記了那裏的東西。同時FSM部分只能存儲一個有限大小的序列。

下推自動機和FSM不能解釋簡單的三種指令語言。如果固定的FSM或下推自動機能夠執行一些語言中的任意程序，那麼該語言不僅必須不是圖靈完整的，而且必須比給定的更簡單。這是非常嚴格的，所以說FSM和下推自動機不能自我解釋是合理的。

來源

2011-03-13 14:15:35

2

FSM = Flying Spaguetti Monster？你可以寫一個自我解釋的圖靈機，但是一個FSM不是圖靈完整的（據我所知），所以我認爲答案是否定的，你不能。

來源

2011-03-05 17:30:17 Luixv

+2

但是...一個自我解釋器可能不如圖靈機器強大。你的回答需要編輯來覆蓋這種可能性。 – 2011-03-14 17:00:00

0

是（自口譯有限狀態機）

這裏有一個很短的一紙...

http://arxiv.org/abs/cs/0311032

，但我不知道這是否是免費提供任何地方。

這裏是brainfuck自我解釋 -

http://www.iwriteiam.nl/Ha_bf_inter.html

來源

2011-03-05 17:32:09 Orbit

+0

對不起，但它說，解釋器是基於「簡單的圖靈完全語言」。我的目標是瞭解更強大的語言。 Thx :) – Bubba88 2011-03-05 17:35:45

+0

哦，道歉誤會。 – Orbit 2011-03-05 17:36:50

+0

但如果該版本的Brainf ** k不是圖靈完成的，那麼你確實幫了我。 – Bubba88 2011-03-05 17:38:06

是否可以編寫自解釋的FSM或下推自動機？

回答

相關問題