wolfram-mathematica - セルオートマトンを使用したBrainfuckインタプリタ

Question

誰かがbrainfuckインタプリタのためのセルオートマトンルールのセットを持っていますか？万能チューリング機械の実装に似ていると思います。それらはwolframサイトに存在しますが、BFシステム用にそれらを微調整する方法がわかりません。

Answer 1

セルオートマトンは「インプレース」ルールです。一連のルールは、次のルールを計算するために、現在のステータスより前のステータスを必要としません。

ただし、BF は「インプレース」で計算しません。BF にはポインターとスタックがあり、評価中にプログラム空間自体を変更してはなりません。ポインター変数とスタック空間はグローバルな状態であるため、BF プログラムを評価する一連のセル オートマトン ルールを設計することは困難です。

BF プログラムは 1 次元であるため、フォン ノイマンの感覚では、「セルラー」オートマトンは無意味です。

ユニバーサル チューリング マシンであるセル オートマトンが存在することは事実ですが、それは (それ自体) すべてのユニバーサル チューリング マシンがセル オートマトンであることを意味しません。

Answer 2

ルール110はチューリング完全であり、ユニバーサル計算が可能です。