细胞自动机

细胞自动机（英语：Cellular automaton），又称格状自动机、元胞自动机，是一种离散模型，在可计算性理论、数学及理论生物学都有相关研究。它是由无限个有规律、坚硬的方格组成，每格均处于一种有限状态。整个格网可以是任何有限维的。同时也是离散的。每格于t时的态由t-1时的一集有限格（这集叫那格的邻域）的态决定。每一格的“邻居”都是已被固定的。（一格可以是自己的邻居。）每次演进时，每格均遵从同一规矩一齐演进。

就形式而言，细胞自动机有三个特征：

• 平行计算（parallel computation）：每一个细胞个体都同时同步的改变

• 局部的（local）：细胞的状态变化只受周遭细胞的影响。

• 一致性的（homogeneous）：所有细胞均受同样的规则所支配

“像生命游戏这样规则简单的东西能够创造出高度复杂的特征，智慧甚至可能从中诞生。这个游戏需要数百万的格子，但是这并没什么奇怪的，我们的脑中就有数千亿的细胞。”

————————纪录片《史蒂芬·霍金之大设计》

生命游戏

**生命游戏便是“涌现复杂性”（emergent complexity）或者说“自组织系统”（self-organizing system）的最简单版本。通过生命游戏，人们可以理解复杂的模式和行为是如何从几条简单的规则中“涌现”出来的。**比如，它可以解释，玫瑰的花瓣或者斑马身上的条纹是如何从一些生长在一起的活细胞中演变出来的。**它甚至能够帮助我们理解生命复杂性的来源。**认知科学家、哲学家丹尼尔·丹尼特（Daniel C. Dennett）甚至提出，康威生命游戏说明，复杂的哲学建构，比如意识和自由意志可能就是由一些简单的物理定律触发的，而这一切本质上是决定论的。

生命游戏中，对于任意细胞，规则如下：每个细胞有两种状态-存活或死亡，每个细胞与以自身为中心的周围八格细胞产生互动。（如图，黑色为存活，白色为死亡）当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时， 该细胞变成死亡状态。（模拟生命数量稀少）当前细胞为存活状态时，当周围有2个或3个存活细胞时， 该细胞保持原样。当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。 （模拟繁殖）可以把最初的细胞结构定义为种子，当所有在种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始。

在这个游戏中，还可以设定一些更加复杂的规则，例如当前方格的状况不仅由父一代决定，而且还考虑祖父一代的情况。玩家还可以作为这个世界的“上帝”，随意设定某个方格细胞的死活，以观察对世界的影响。在游戏的进行中，杂乱无序的细胞会逐渐演化出各种精致、有形的结构；这些结构往往有很好的对称性，而且每一代都在变化形状。一些形状已经锁定，不会逐代变化。有时，一些已经成形的结构会因为一些无序细胞的“入侵”而被破坏。但是形状和秩序经常能从杂乱中产生出来。

游戏试玩：

[该类型的内容暂不支持下载]

请根据初始的图进行游玩观察变化，以下是几个比较著名的模型：

康威的最大发现是**“滑翔机”**（glider，康威认为滑翔机属于轻量级的“太空船”spaceship，太空船是会不断移动位置，但会周期性回到原来样子的图案）。在2轮后，它会移动位置并且沿着对角线翻转。几何学家把这种反转叫做“滑移反射”（glide reflection），这就是为什么它被叫做滑翔机的原因。再过2轮，滑翔机又会翻回来，并沿着对角线向下移动1格。

下面三幅图被称为**“振荡器”（oscillator），因为它会在几个图案间不停轮换。康威把最简单的振荡器叫做“闪光灯”（blinker，下图左）。除了闪光灯，常见振荡器还有“信号灯”（traffic light，下图中，也是常见图案）和“脉冲星”**（pulser，下图右）等。

闪光灯、信号灯、脉冲星

有一种5个细胞组成的图案叫做“R pentomino”。康威在试验了460轮后它依然没有灭绝，而且还从第69轮吐出一些“滑翔机”。

康威说：“它会留下许多奇奇怪怪的垃圾，它们四处游荡。不过它只有很少一部分活跃的区域，所以并不清楚它会不会一直如此无穷地持续下去。”实际上，后来人们发现 R pentomino 在第1103轮会最终稳定下来，此时它是由116个细胞组成的，它们组成了8个方块、6个滑翔机、4个蜂巢、4个闪光灯、1个小船、1个面包和1个大船（ship）。

初始状态和1103轮后的 R pentomino（不包括6个飞走的滑翔机）。图片来源：conwaylife.com

康威曾推测，没有任何图案能够无止境地生长。他曾拿出50美金作为奖品，奖励第一个能够在那年证明这个命题或者将其证伪的人。

这个奖在同年11月就被麻省理工学院的 Bill Gosper 摘取。Gosper 发现了**“Gosper glider gun”**，它在15轮产生第一个滑翔机，再过15轮又产生第二个滑翔机。这一模型是目前为止最小的 glider gun。

Gosper glider gun

实际上，“枪”（gun，能够不断产生移动图案的初始图案），或者**“喷气火车”**（puffer train，会移动的图案，在身后会留下一缕“烟”）也是能无限生长的初始图案。

后来，更多的枪、喷气火车和耙子（rake，能够移动并产生太空船）被发现。Gosper 还建造了第一个具有渐近最优二次增长速率的初始图案——“繁殖者”（breeder，也称“龙虾” lobster），它在行进的过程中会在身后留下一串“枪”。最后一种叫做**“填充者”** （Spacefiller），它会不断生长填充空间，这种图案是在1993年借助计算机发现的。

繁殖者

填充者

2010年，加拿大多伦多的程序员创造出了生命游戏中首个能够实现自我复制的图案——双生子（gemini）。（其实类似的能够自我复制的元胞自动机早已存在。比如，有一个著名的一维元胞自动机叫做“rule 90”，它可以在一定轮数后开始复制。）

“双生子”自我复制的方式。图片来源：NewScientist

康威提出，图案移动到空白空间的速度是有限的。在方格世界中，速度的定义指的是，一个图案复制一次所移动的格子数除以轮数得出的值。

康威把1轮1格（可直角，可斜角移动；也就是国际象棋中王的移动速度）的速度叫做**“光速”**。康威把这个速度叫做“光速”的原因是，在方格世界中任何图案都无法超过这个速度。比如，滑翔机每4轮就复制一次并沿着对角移动1格，因此它的速度就是1/4光速。

康威证明，沿着对角线移动的最快速度是“光速”的四分之一，而太空船的最高速度是1/2光速，因为无法建造一个每一轮都能移动的太空船。不过在生命游戏中，可以通过介质获得光速，比如物体在穿越由蜂巢构成的特殊轨道时就能够以光速行进。有时候，物体看起来的移动速度超过了光速，不过这些都是视错觉。

“星际之门”（star gate）中的太空船在6轮中似乎“飞跃”了11格。

简单版本

每个细胞都有两种可能的状态：生存或死亡。在大多数情况下，死亡的细胞被标记为白色，而存活的细胞被标记为黑色。整个系统的演化规则是简单而优雅的，它根据每个细胞周围存活细胞的数量来确定该细胞在下一个迭代阶段的状态。

规则一：死

有两种情况这个细胞会死亡：1）周围存活的邻居少于2个，孤独而死；2）存活邻居多于3个，资源枯竭而死；

规则二：生

有2~4细胞相邻，将活到下一轮；

规则三：转生

最后，复活规则，如果一个死亡的细胞周围有恰好三个存活的邻居，那么在下一步迭代中，这个细胞将由死转生。

可以把最初的细胞结构定义为种子，当所有在种子中的细胞同时被以上规则处理后，可以得到第一代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始。这个基于简单规则的系统可以产生出意想不到的复杂性，正是这种复杂性使得《生命游戏》和其他细胞自动机如此引人入胜。

在复杂系统中，最有趣的行为不是在系统的个体组成部分这个规模级别上产生的，而是在许多个体部分所组成的群体这个规模级别上产生的。比如说鸟群，整个鸟群仿佛是一个整体，每个个体都遵循如下规则：想群体中心不为移动；配合相邻个体的方向和速度；避免个体和相邻个体过于接近。这样整群鸟都会遵循一个明确的形状、方向和目标。

其他资料

[该类型的内容暂不支持下载]

其他版本的自动机，康伟生命游戏知识其中最具代表性的之一；