初等细胞自动机

书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第7章目录

7.2　初等细胞自动机

  本章将从Wolfram理论的模拟开始，为了理解Wolfram提出的初等CA模型，我们要先问自己几个问题：“你能想象到的最简单的细胞自动机是什么？”
  问这个问题的意义在于：即使在最简单的CA模型中，我们也能看到复杂系统的特性。
  下面我们要从头开始构建Wolfram的初等CA模型。在实现之前，我们要先学习其中的概念。
1、CA三大要素

• 1.网格
  最简单的网格是一维的，即一行细胞。
  
  
  
• 2.状态集
  最简单的状态集（多于一种状态）是0或1。
  
  
  
• 3.邻居
  在最简单的情况下，某个细胞在一维空间中的邻居就是它自身和相邻的两个细胞，即左边和右边的细胞。
  
  
  

2、模型

• 因此我们的模型从一行细胞开始，每个细胞都有一个初始状态（假设它不是随机的），还有两个相邻的细胞。除此之外，我们还要约定边缘细胞的处理方式（因为它们只有一个相邻的细胞），
  
• 细胞自动机最重要的工作细节——时间，
  它不是现实世界的时间，而是CA的运行所需的时间段，也可以称为代（generation），在本例中，时间就是动画的帧数。
  上面的几幅图展示了CA在第0代的状态。对此，我们需要问自己几个问题：如何计算细胞在第1代的状态，如何计算第2代以及后面几代的状态？
  
  
  
• 假设在CA中有个细胞，我们称之为CELL。CELL在第t代的状态计算公式如下：
  CELL在第t代的状态 = f(CELL的邻居在第t-1代的状态)
  这意味着：细胞的新状态是一个函数，函数的参数是邻居在上一代的状态。我们可以根据邻居先前的状态计算出该细胞的新状态。
  
  
  
• 在细胞自动机世界里，细胞状态有多种计算方式。图像模糊处理算法和CA规则类似：某个像素的新状态（也就是它的颜色）等于所有邻居像素颜色的平均值。我们也可以让细胞的新状态等于邻居状态的加和。在Wolfram的初等CA模型中，我们就用这种简化方式计算细胞状态：枚举邻居细胞的所有状态组合，对每种可能的情况建立结果映射。
  

3、谢尔宾斯基三角形

• 假设有3个细胞，每个细胞的状态都是0或1。这3个状态相互组合能出现多少种情况？
  根据二进制运算的知识，这3个细胞代表3个比特位，它们能形成8种组合：
  
  
  
• 标准的Wolfram模型从第0代开始，最中间细胞的初始状态是1，而其他细胞的初始状态是0。
  根据上面的规则，推算一个给定的细胞（我们选择最中间的细胞）在第1代会发生怎样的状态变化。
  我们把同样的逻辑作用在所有细胞上，然后填补空白的细胞状态。
  
• 得到新一代细胞的状态后，我们可以为它们着色，用白色方块表示0，用黑色方块表示1；然后把每代细胞堆叠在一起，让新一代细胞显示在旧一代的下面。
  
  
  
• 这个低分辨率图案称为“谢尔宾斯基三角形”，以波兰数学家瓦茨瓦夫·谢尔宾斯基的名字命名，这是一种分形图案。
  我们将在下一章学习分形。我们可以从上图看出：一个由0和1组成的简单系统，只要根据3个邻居细胞的状态，就可以生成复杂的谢尔宾斯基三角形。
  
• Wolfram初等CA也有256种可能的规则。而上图所示的规则通常称为“规则90”，因为二进制序列01011010转化为十进制后就等于90。