自我复制的细胞自动机

弗雷特金栅极是最着名的，弗雷德金是最着名的，适用于褶皱门，这是一个通用的可逆电路。

我最近发现Fredkin是蜂窝自动机中的一个先驱之一。他的学生Edwin银行描述了Fredkin推出的蜂窝自动机[1]。

MIT的Edward Fredkin描述了以下有趣的蜂窝空间。如果状态为0和1，并且如果通过占用邻居的总和而获得结果状态，则每个初始配置将自身重现初始配置的副本。

换句话说，从位的无限棋盘中以某些位模式开始。然后，在每个步骤中，通过相邻位之和的奇偶校验替换每个比特。最终你会看到那个原始模式的副本。

关于“邻居”的意思有一些歧义。银行的论文认为，邻居是北，南，东方和西部的位，这意味着当他描述Fredkin的自动机时，银行有这些邻居。其他消息人士称，Fredkin也被认为是对角相邻的位，作为邻里的一部分，即西北，东北，西南和东南。

Terry Winograd（1970）概括了这一结果，表明任何邻居，不仅仅是四个最近的邻居，并且任何数量的维度仍然产生相同的结果。

我将其“四个最近的邻居”北，南，东部和西方的邻居。我不确定Winograd的定理中的“任何邻居”意味着什么;我想起必须有一些隐含的限制。

在任何情况下，我将通过示例来展示上面讨论的“邻居”的定义导致再现原始模式，尽管它们不会以相同的方式再现它。 我将在网格中间的“e”开始。 黑色方块表示0s，白色方块表示1s。 以下是使用“邻居”仅包括北，南，东部和西邻的规则来发展这种模式的前八个步骤。 如果我们认为每个点都有八个邻居，即我们包括对角线，这就是前八步的样子。 使用每个单元格，使用彩色而不是黑白单元格，请参阅下一篇文章以使用两个以上的状态。 如果颜色的数量是素数，并且您将相邻状态的总和为Mod P而不是Mod 2，您将获得类似的结果。 [1] edwin r.银行，信息处理和蜂窝自动机的传输。 麻省理工学院论文。 1971年1月。