稳定元胞自动机
Stablized cellular automation
我正在研究细胞自动化模拟。
规则如下：
- 每个单元与其摩尔邻域相互作用以更新其值。
- 单元格位于任何无限维网格中。
- 单元格可能具有随机初始值。
- 规则是稳定的，经过一定的迭代后，会收敛到一个统一的状态。
对于某种编程语言来说不是必需的，所以我们在这个算法中只有基本数据类型，即bool，int，它们的n维数组等。
我有任何单元格的初始值，我可以随时将其加载到内存中。有没有什么算法可以在不循环整个无限网格的情况下计算出它的稳定值？
具体来说，我正在研究的是一个规则B5678/S45678二维类生命细胞自动化。
Is there any algorithm to calculate [a particular cell's] stabilized value without looping the whole infinite grid?
对于这个特定的 CA 规则，是的，有点。特别是，您可以 almost surely 通过仅检查有限数量的周围单元来确定晶格上任何给定单元的最终稳定状态。但是，您可能需要检查的单元格数量可以任意大。
首先，让我注意到life-like cellular automaton规则代码“B5678/S45678”表示“多数表决”规则，其中每个单元格在下一个时间步的状态是当前多数状态九个单元格由它自己和它的八个邻居组成。
这条规则恰好满足单调性属性：将一个或多个细胞的初始状态从“关闭”翻转到“打开”不会导致任何细胞的未来状态从“打开”翻转到“打开” “关闭”，反之亦然。也就是说，晶格的未来状态是当前状态的单调递增函数。
这种单调性有一些重要的后果。特别是，它意味着如果你有一个处于“开”状态的细胞群，周围都是处于“关”状态的细胞（反之亦然），并且如果这个细胞群目前是稳定的（在某种意义上应用 CA 更新规则一次不会导致集群中的任何单元改变状态），那么它实际上将永远稳定，无论晶格上其他地方发生什么。
这是因为其他地方的事件可能影响星团的唯一方式是改变它周围一个或多个细胞的状态。并且由于所有这些周围的细胞都处于“关闭”状态，而集群中的细胞处于“开启”状态，单调性确保将任何周围细胞的状态更改为“开启”不会导致任何细胞的未来状态群集更改为“关闭”。 （当然，同样的论点也适用于mutatis mutandis到被“on”细胞包围的“off”细胞簇。）
（事实上，您并不真的需要 实际上 被“关闭”单元包围的“打开”单元簇，反之亦然——所有这些都需要稳定性是集群会稳定，即使它周围的所有细胞都处于相反的状态。）
因此，一般来说，要确定一个细胞的最终状态，只需模拟其周围细胞的时间演化，直到它成为这样一个稳定的集群的一部分。
在（几乎肯定）有限时间内完成此操作的一种方法是将连续时间步长的 2D 格子序列视为形成堆叠 2D 切片的 3D 格子，并计算连续的“金字塔形”部分这个 3D 晶格由中心单元的状态组成，直到时间步长 n，它的邻居直到时间步长 n − 1，他们的邻居向上到时间步 n − 2，依此类推。定期检查这个不断增长的金字塔的每一层，看看它们中是否有任何一层包含一个包含中央单元的稳定簇（在上述意义上）。
假设中心单元实际上最终成为这样一个稳定的有限簇的一部分（随机初始化的格子上的几乎所有单元最终都遵循这个规则；证明留作练习！），这个方法最终会发现簇。然而，根据周围细胞的初始状态，这种稳定可能需要任意长的时间，而细胞的最终状态可能取决于任意远处的其他细胞的状态。
例如，假设我们感兴趣的单元恰好位于晶格的某个区域，其中初始单元状态偶然地排列成棋盘上的正方形：四个正交每个单元格的邻居都处于相反的状态，而四个对角线邻居都与中心单元格处于相同状态。显然，这样的棋盘排列在局部是稳定的，因为每个单元（几乎！）在其邻居中占多数，但任何方向偏离棋盘边缘这种不稳定平衡的任何方向都会作为连锁反应传播到整个棋盘。因此，棋盘上任何特定单元的最终稳定状态将取决于棋盘区域周围的单元状态，该区域可以任意远。
我正在研究细胞自动化模拟。 规则如下：
- 每个单元与其摩尔邻域相互作用以更新其值。
- 单元格位于任何无限维网格中。
- 单元格可能具有随机初始值。
- 规则是稳定的，经过一定的迭代后，会收敛到一个统一的状态。
对于某种编程语言来说不是必需的，所以我们在这个算法中只有基本数据类型，即bool，int，它们的n维数组等。
我有任何单元格的初始值，我可以随时将其加载到内存中。有没有什么算法可以在不循环整个无限网格的情况下计算出它的稳定值？
具体来说，我正在研究的是一个规则B5678/S45678二维类生命细胞自动化。
Is there any algorithm to calculate [a particular cell's] stabilized value without looping the whole infinite grid?
对于这个特定的 CA 规则，是的，有点。特别是，您可以 almost surely 通过仅检查有限数量的周围单元来确定晶格上任何给定单元的最终稳定状态。但是，您可能需要检查的单元格数量可以任意大。
首先，让我注意到life-like cellular automaton规则代码“B5678/S45678”表示“多数表决”规则，其中每个单元格在下一个时间步的状态是当前多数状态九个单元格由它自己和它的八个邻居组成。
这条规则恰好满足单调性属性：将一个或多个细胞的初始状态从“关闭”翻转到“打开”不会导致任何细胞的未来状态从“打开”翻转到“打开” “关闭”，反之亦然。也就是说，晶格的未来状态是当前状态的单调递增函数。
这种单调性有一些重要的后果。特别是，它意味着如果你有一个处于“开”状态的细胞群，周围都是处于“关”状态的细胞（反之亦然），并且如果这个细胞群目前是稳定的（在某种意义上应用 CA 更新规则一次不会导致集群中的任何单元改变状态），那么它实际上将永远稳定，无论晶格上其他地方发生什么。
这是因为其他地方的事件可能影响星团的唯一方式是改变它周围一个或多个细胞的状态。并且由于所有这些周围的细胞都处于“关闭”状态，而集群中的细胞处于“开启”状态，单调性确保将任何周围细胞的状态更改为“开启”不会导致任何细胞的未来状态群集更改为“关闭”。 （当然，同样的论点也适用于mutatis mutandis到被“on”细胞包围的“off”细胞簇。）
（事实上，您并不真的需要 实际上 被“关闭”单元包围的“打开”单元簇，反之亦然——所有这些都需要稳定性是集群会稳定，即使它周围的所有细胞都处于相反的状态。）
因此，一般来说，要确定一个细胞的最终状态，只需模拟其周围细胞的时间演化，直到它成为这样一个稳定的集群的一部分。
在（几乎肯定）有限时间内完成此操作的一种方法是将连续时间步长的 2D 格子序列视为形成堆叠 2D 切片的 3D 格子，并计算连续的“金字塔形”部分这个 3D 晶格由中心单元的状态组成，直到时间步长 n，它的邻居直到时间步长 n − 1，他们的邻居向上到时间步 n − 2，依此类推。定期检查这个不断增长的金字塔的每一层，看看它们中是否有任何一层包含一个包含中央单元的稳定簇（在上述意义上）。
假设中心单元实际上最终成为这样一个稳定的有限簇的一部分（随机初始化的格子上的几乎所有单元最终都遵循这个规则；证明留作练习！），这个方法最终会发现簇。然而，根据周围细胞的初始状态，这种稳定可能需要任意长的时间，而细胞的最终状态可能取决于任意远处的其他细胞的状态。
例如，假设我们感兴趣的单元恰好位于晶格的某个区域，其中初始单元状态偶然地排列成棋盘上的正方形：四个正交每个单元格的邻居都处于相反的状态，而四个对角线邻居都与中心单元格处于相同状态。显然，这样的棋盘排列在局部是稳定的，因为每个单元（几乎！）在其邻居中占多数，但任何方向偏离棋盘边缘这种不稳定平衡的任何方向都会作为连锁反应传播到整个棋盘。因此，棋盘上任何特定单元的最终稳定状态将取决于棋盘区域周围的单元状态，该区域可以任意远。