Brainfuck解釋器使用元胞自動機

Question

有沒有人有腦袋解釋器的細胞自動機規則集？我認爲它與通用圖靈機的實現類似。那些存在於wolfram網站，但我不知道如何調整他們的BF系統。

Answer 1

元胞自動機是「就地」規則。一組規則不需要當前狀態之前的狀態來計算下一個狀態。然而，BF不計算「in-place」：它有一個指針和一個堆棧，程序空間本身在評估時不能改變。由於指針變量和堆棧空間是全局狀態，因此很難設計一組評估BF程序的元胞自動機規則。

BF程序是一維的，所以在Von Neumann意義上說「細胞」自動機將是荒謬的。

的確存在細胞自動機是通用圖靈機，但並不意味着（本身）所有通用圖靈機都是細胞自動機。

Answer 2

Rule 110是圖靈完整的，並能夠通用計算。