wolfram-mathematica - 使用元胞自动机的 Brainfuck 解释器

Question

有没有人有一套用于脑残解释器的元胞自动机规则？我认为它类似于通用图灵机的实现。这些存在于 wolfram 网站上，但我不知道如何为 BF 系统调整它们。

Answer 1

元胞自动机是“就地”规则。一组规则不需要当前规则之前的状态来计算下一个规则。

然而，BF 不会“就地”计算：它有一个指针和一个堆栈，并且程序空间本身在计算时不能改变。由于指针变量和堆栈空间是全局状态，因此很难设计一组评估 BF 程序的元胞自动机规则。

BF 程序是一维的，所以在冯诺依曼的意义上，“细胞”自动机是荒谬的。

确实存在作为通用图灵机的元胞自动机，但这并不意味着（本身）所有通用图灵机都是元胞自动机。

Answer 2

规则 110是图灵完备的，并且能够进行通用计算。