元胞自动机

元胞自动机是在指定形状的网格上“着色”单元的集合，它根据一组基于相邻单元状态的规则，通过若干离散时间步长演化。然后，将这些规则迭代地应用于所需的多个时间步长。冯·诺伊曼是最早考虑这种模型的人之一，并将元胞模型纳入了他的“通用构造器”中。在 1950 年代初期，人们研究了元胞自动机，作为生物系统的可能模型（Wolfram 2002，第 48 页）。S. Wolfram 从 1980 年代开始对元胞自动机进行了全面的研究，Wolfram 在该领域的基础研究最终促成了他的著作A New Kind of Science（Wolfram 2002）的出版，Wolfram 在书中展示了关于自动机的巨量研究成果，其中包括许多开创性的新发现。

电视剧犯罪剧集数字追凶第二季剧集“Bettor or Worse”（2006 年）提到了 一维元胞自动机。

元胞自动机有多种形状和类型。元胞自动机最基本的属性之一是计算它的网格类型。最简单的这种“网格”是一维线。在二维中，可以考虑正方形、三角形和六边形网格。元胞自动机也可以在任意维数的笛卡尔网格上构建，其中维整数格是最常见的选择。在维整数格上的元胞自动机在 Wolfram 语言中实现为CellularAutomaton[规则, 初始状态, 步数]。

还必须指定元胞自动机可能假设的颜色（或不同状态）的数量。这个数字通常是整数，其中（二进制）是最简单的选择。对于二进制自动机，颜色 0 通常称为“白色”，颜色 1 通常称为“黑色”。但是，也可以考虑具有连续值范围的元胞自动机。

除了元胞自动机所处的网格及其单元可能假设的颜色之外，还必须指定单元相互影响的邻域。最简单的选择是“最近邻域”，其中在每个时间步长只影响直接相邻于给定单元的单元。在正方形网格上的二维元胞自动机的情况下，两个常见的邻域是所谓的摩尔邻域（正方形邻域）和冯·诺伊曼邻域（菱形邻域）。

最简单的元胞自动机类型是二进制、最近邻、一维自动机。S. Wolfram 将这种自动机称为“基本元胞自动机”，他广泛研究了它们惊人的特性（Wolfram 1983；2002，第 57 页）。共有 256 个这样的自动机，每个自动机都可以通过唯一的二进制数进行索引，该二进制数的十进制表示形式称为特定自动机的“规则”。上面显示了规则 30 的图示，以及从单个黑色单元开始 15 步后产生的演化。

稍微复杂一点的元胞自动机类别是最近邻、色、一维全域元胞自动机。在这种自动机中，决定演化的是相邻单元的平均值，最简单的非平凡示例具有种颜色。对于这些自动机，描述行为的规则集可以编码为位进制数，称为“代码”。上面说明了三元（）代码 912 自动机的规则和 300 步。

在二维中，最著名的元胞自动机是康威的生命游戏，由 J. H. Conway 于 1970 年发现，并在 Martin Gardner 的科学美国人专栏中普及。生命游戏是二进制（）全域元胞自动机，具有范围为的摩尔邻域。尽管连续生命游戏世代的计算最初是手工完成的，但计算机革命很快到来，使得可以研究和传播更广泛的模式。上面说明了被称为充气火车（puffer train）的生命游戏构造的动画。

线世界是另一种常见的二维元胞自动机。

元胞自动机的理论非常丰富，简单的规则和结构能够产生各种意想不到的行为。例如，存在通用元胞自动机，它能够模拟任何其他元胞自动机或图灵机的行为。Gacs (2001) 甚至证明，存在容错通用元胞自动机，只要扰动足够稀疏，它们的模拟其他元胞自动机的能力就不会受到随机扰动的阻碍。