稳定的蜂窝自动化

Question

我在做细胞自动化模拟。规则如下：

• 每个单元与摩尔的邻里相互作用，以更新其价值。
• 细胞处于任何无限维网格中。
• 细胞可能有一个随机初始值。
• 规则是稳定的，经过一定的迭代，它们将收敛到一个统一的状态。

对于特定的编程语言来说，这是不必要的，因此在该算法中，我们只需要基本的数据类型，如bool、int、它们的n维数组等。

我有任何单元格的初始值，只要我想要，就可以加载到内存中。是否有任何算法来计算它的稳定值而不循环整个无限网格？

具体来说，我正在研究的是B 5678/S 45678二维生命型细胞自动化规则。

Answer 1

是否有任何算法计算特定单元格的稳定值而不循环整个无限网格？

对于这个特殊的CA规则，是的，有点。特别是，您可以通过只检查有限数量的周围单元来确定格上任何给定单元的最终稳定状态。但是，您可能需要检查的单元格数量可以任意大。

首先，请允许我注意，类生命元胞自动机规则代码“B 5678/S 45678”表示“多数票”规则，其中每个单元格在下一时间步骤中的状态是由其自身及其八个邻居组成的九个单元格中的当前多数状态。

此规则恰好满足单调性属性:将一个或多个单元格的初始状态从"off“翻转到"on”，不能导致任何单元格的未来状态从"on“切换到"off"，反之亦然。换句话说，格的未来状态是当前状态的单调增长函数。

这种单调性有一些重要的后果。特别是，它意味着，如果在" on“状态下，有一组单元格被处于"off”状态的单元格所包围(反之亦然)，并且如果该群集当前是稳定的(也就是说，应用CA更新规则一次不会导致任何单元格处于群集更改状态)，那么它实际上将永远稳定，不管在晶格上其他地方发生了什么。

这是因为其他地方的事件可能影响集群的唯一方法是改变它周围一个或多个单元的状态。由于周围的所有细胞都处于“关闭”状态，而集群中的细胞处于"on“状态，因此单调性确保了将周围任何细胞的状态更改为"on”不会导致集群中任何细胞的未来状态变为"off“。(当然，同样的论点也可以比照适用于由"on“细胞包围的”关闭“细胞群。)

(实际上，不需要"on“单元实际上被"off”单元包围，反之亦然-稳定所需的只是集群将是稳定的，即使其周围的所有单元处于相反的状态。)

因此，一般来说，要确定一个细胞的最终状态，它就足以模拟其周围细胞的时间演变，直到它成为这样一个稳定的集群的一部分。

在(几乎可以肯定的)有限时间内这样做的一种方法是将连续时间步骤中的2D格序列处理为形成一个由叠加的2D切片组成的三维晶格，并计算这个3D格的逐次“金字塔”段，由中央单元的状态到时间步骤n，其邻域一直到时间步骤n−1，它们的邻域一直到时间步骤n−2，等等。定期检查这个不断增长的金字塔的每一层，看看其中是否有一个稳定的集群(在上面描述的意义上)包含中央细胞。

假设中央细胞最终最终成为这样一个稳定的有限簇的一部分(几乎所有随机初始化格上的单元最终都是按照这个规则进行的；作为练习留下的证明！)，这个方法最终会找到这个簇。然而，取决于周围细胞的初始状态，这种稳定可能需要任意长的时间，而细胞的最终状态可能取决于其他细胞的状态。

例如，让我们假设我们感兴趣的单元恰好位于格子的一个区域，在这个区域，初始的细胞状态就像棋盘上的正方形:每个单元的四个正交邻居处于相反的状态，而四个对角线的邻居都处于与中心单元相同的状态。显然，这种棋盘布置是局部稳定的，因为每个单元都是(勉强！)在它的大多数邻居中，但是在棋盘边缘的任何一个方向偏离这种不稳定的平衡，都会作为连锁反应在整个棋盘上传播。因此，棋盘上任何特定单元的最终稳定状态将取决于棋盘区域周围的单元格的状态，这种状态可以任意地远离。