模型概率模型23 元胞自动机简介(一)

元胞自动机(CA)是一组排列在特定形状的网格中的细胞（也叫做元胞)，每个细胞的状态根据一组定义的规则(由相邻细胞的状态驱动)作为时间的函数变化。它被用于公钥密码学，以及在地理学、人类学、政治学、社会学和物理学等领域。

元胞自动机的特征¶

CA是特定形状网格上的彩色细胞或原子的集合。每个细胞都处于有限的状态之一。该计算模型既抽象又时空离散。

计算性是指该模型可以计算函数和解决算法问题。抽象指的是CA可以用纯数学术语来指定。CA在空间和时间上都是离散的，这意味着在每个时间单位中，构成CA的单元表示有限的状态集中的一个。此外，网格中的细胞通过考虑相邻细胞的状态，以离散时间步并行进化。

因此，CA通过几个离散时间步骤的演化是基于一组建立在相邻细胞状态上的规则。这些规则可以根据需要迭代应用任意多的时间步骤。

CA的典型特征如下:

细胞自动机有不同的形状和种类。最简单的CA是一维的，单元格位于一条直线上，每个单元格只能有两种可能的状态(例如高/低或黑/白)。然而，其他形状也是可能的。在二维空间中，常见的单元格形状是正方形、六边形和立方体。

理论上，CA可以有任意数量的维度，每个细胞可以有任意数量的可能状态。每个细胞的状态以离散的步骤以固定的时间间隔变化。在任何给定时间，这种状态取决于以下情况:

CA可以构造在任意维数的笛卡尔网格上。

CA有很多种类型，最简单的类型是二元的、最近邻的一维自动机，称为基本元胞自动机。这样的CA共有256个。另一种类型的CA是最近邻k色一维整体细胞自动机。在最简单的CA中，k = 3。

在二维中，最著名的两个CA如下:

H.康威的生命游戏，二元极权的CA
WireWorld ## 理解基本细胞自动机基本CA是CA中最简单的非平凡类。在这个CA中，单元格可以有两个可能的值，0或1。因此，这个CA可以用一个表来描述，这个表指定了一个cell在下一代中将拥有的状态，其值基于:
左边的细胞
细胞本身
右边的细胞

一个特定单元相邻的三个单元有八种可能的二进制状态，这意味着有28 = 256个基本CA，其中每个CA都可以用8位二进制数索引。

基本CA的主要特征如下:

它是一维的。
细胞状态只能有两个可能值中的一个:0或1。
网格上的任何细胞都依赖于单元格本身和两个相邻的邻居(左和右)。
细胞的状态会因代而异。一维CA的演化可以从第一行的初始状态(“零代”)开始，第二行的第一代，等等来说明。 ## 元胞自动机的分类细胞自动机早在20世纪50年代就被研究为生物系统的可能模型。然而，直到20世纪80年代，这一领域的研究才开始蓬勃发展，这要归功于英裔美国计算机科学家斯蒂芬·沃尔夫拉姆(Stephen Wolfram)。Wolfram在他的《一种新的科学》一书中根据CA的行为将其分为以下四类:
类1。几乎所有模式都演化为稳定的同质状态。
类2。几乎所有的初始模式都转变为稳定的或振荡的。
类3。所有的初始模式都以混沌或伪随机的方式变换。对初始模式的局部变化可能无限地扩散。
类4。所有初始模式都转换为以有趣的方式相互作用的复杂结构。

John Conway的Game of Life(也被简称为Life)是一个二维的、极权的CA，它比基本CA引入了更多的复杂性，因为网格中的每个细胞都有更大的邻域。它是一个“通用”(或计算通用)CA，因为它可以有效地模拟任何CA、图灵机或其他可以转换为已知通用系统的系统。

这个二维CA由细胞矩阵组成，而不是一维的细胞行。每一代都会根据周围细胞的状态来开启或关闭细胞。

在生命中，一个细胞周围有八个细胞。检查所有8个单元格，看它们是否处于开启状态。对单元格进行计数，该计数用于确定当前单元格将发生什么。根据计数，定义Life的规则如下:

下面是CA的一些最流行的应用。

参考资料