简明介绍：http://mmdays.com/2007/07/12/game_of_life/ 简单模拟：http://www.bitstorm.org/gameoflife/ 更多例子： 网址：http://www.atlas-zone.com/complex/alife/ca/index.html 细胞自动机　Cellular Automata 2002, 1, 10　吴文成 　　细胞自动机（Cellular Automata）最初由数学家 Stanislaw M. Ulam（1909-1984） 与 John von Neumann（1903-1957）於 1950 年代所提出 ，在型态表现上，细胞自动机 是一个离散型的动力系统（ Discrete Dynamical Systems）。在 1940 年代 ，von Neumann 与共事的科学家们合作设计了可储存程式的数位电脑之後，他就对自我复制发生 兴趣：能储存程式的机器能不能自我复制 ？ von Neumann 认为，至少在原则上与形式上是可行的，於是他开始作这方面的理论研 究，过程中他提出了「细胞自动机」的概念， 这个实际构想是由罗沙拉摩斯的数学家 Ulam 所建议的 。当细胞自动机在电脑上模拟的时候，几乎可以复制出类似於自然界当中实际发生的动力 系统运作，这使得细胞自动机成为了研究复杂系统行为的最初理论框架，罗沙拉摩斯的博 士後研究员 Christopher Langton 因而提出了「人工生命」（ Artificial Life ）这个 名词 ， 细胞自动机便是人工生命的第一个雏形，并且变成复杂性科学，或者说是复杂适 应性系统的其中一支。 　　细胞自动机是由一些特定规则的格子所组成，每个格子看做是一个细胞；每一个细胞 可以具有一些状态，但是在某一时刻只能处一种状态之中。随着时间的变化（我们称作「 叠代」过程），格子上的每一个细胞根据周围细胞的情形，按照相同的法则而改变状态， 换句话说，一个细胞的状态是由上一个时刻所围绕的细胞的状态所决定。以人工生命的角 度来看，细胞自动机可以视为一个让许多单细胞生物生活的世界，在我们设定好这个世界 的初始状态之後，它们便按照同一个规则做演化。 　　设计一个细胞自动机需要包含几个部份： 　　◆ 决定细胞活动空间的维度 　　◆ 定义细胞可能具有的状态 　　◆ 定义细胞改变状态的规则 　　◆ 设定细胞自动机中各个细胞的初始状态 　　细胞自动机，在细胞活动的空间上，可以是一维的，二维的，三维的，或更高维度， 在这个网页，笔者要分别介绍二维的细胞自动机（也称作「生命游戏」），与一维的细胞 自动机。透过不同的设计，细胞自动机可以展现无限的多样性，其中最让人惊异的是有些 细胞自动机可以产生存在於大自然的景象，例如贝壳上的图案、雪花的结构、蜿蜒的河流 等等，另外，我们也可以发现，这些小方格的变化似乎展现了许多真实生命的特质，例如 ，细胞自动机中的细胞们会像有机生物一般，有移动、成长、灭亡与自我复制等类似的行 为。 　　就形式而言，细胞自动机有三个特徵： 　　◆ 平行计算（parallel computation）：每一个细胞个体都同时同步的改变 　　◆ 局部的（local）：细胞的状态变化只受周遭细胞的影响。 　　◆ 一致性的（homogeneous）：所有细胞均受同样的规则所支配 　　事实上，有些研究学者更进一步猜测，我们存在的这个宇宙是否就是一种极其复杂的 细胞自动机，我们的宇宙的确与理论上的细胞自动机有很多相似的地方，像是上述的细胞 自动机之三个特徵，宇宙也都符合：宇宙是平行处理的，宇宙中的每一点受邻近状态的影 响最大，宇宙各处遵循着同样的自然律。虽然与整个宇宙相比，细胞自动机的规则是过於 简单，但是它里面所蕴含的道理可能与宇宙的机制是相通的。 理论物理学家 Stephen Wolfram（1959-）就指出 ，细胞自动机的数学架构，与一些造成真实世界的复杂物理系 统之数学架构是完全一样的，也许这正是掌管遗传重任的 DNA 所赖以工作的原理 。当你 看到自然界那些贝壳或指纹曲折的图案时，不免要问 ：「这麽复杂的图案要如何编码到 DNA 里头呢？」Wolfram 说 ：「如果我猜的不错，那些图形是由类似於细胞自动机的简 单法则所产生的，而这样的编码显然是易如反掌。」 　　细胞自动机以简单的规则，却能够产生复杂的动态交互现象，显然我们不该只是以一 个数学游戏，来看待它。这些年来，细胞自动机已经被运用於不同领域的研究，包括通讯 、计算、建设、生长、再生、竞争及演化。细胞自动机已为物理中平常的微分方程式提供 极为简单的模型，例如热和波的波动方程，同时也为湍流、混沌、碎形等提供了离散型的 模型，最後，利用细胞自动机所做的生物模型也被提出。接下来，笔者将尽可能地介绍细 胞自动机的规则、范例与相关资讯，以下的介绍分为两种不同类型的细胞自动机： 　　｜ 　　├─ 二维的细胞自动机： 　　｜　　　｜ 　　｜　　　├─ 生命游戏，与其规则 　　｜　　　├─ 生命游戏的有趣范例 　　｜　　　├─ 生命游戏的规则变化（一） 　　｜　　　├─ 生命游戏的规则变化（二） 　　｜　　　├─ 生命游戏的规则变化（三） 　　｜　　　└─ 生命起源於混沌的边缘 　　｜ 　　├─ 一维的细胞自动机： 　　｜　　　｜ 　　｜　　　├─ 一维细胞自动机，与其规则（一） 　　｜　　　├─ 一维细胞自动机，与其规则（二） 　　｜　　　├─ 一维细胞自动机，与其规则（三） 　　｜　　　├─ 一维细胞自动机的有趣范例 　　｜　　　└─ 四个普遍性等级的再探讨 　　｜ 　　└─ 相关连结与资源 　　了解了细胞自动机的叠代过程之後，你会发现：细胞自动机在某一叠代的细胞形态只 会产生「唯一」形态的下一代，而我们却无法从新一代的形态而回溯得知上一代确定的细 胞形态，因为这样的「回溯」有太多种可能性，而且可能性的数量会随着一次接着一次的 「回溯」而以指数比例地增加，这使得我们即使看见某一叠代中有趣的细胞演化，却无法 准确地推回出它的初始状态 。这种性质，我们称呼为「Forward-Deterministic」，意思 是，细胞自动机的叠代演化是往前决定的，它有许多个可能的过去，但是它的未来发展只 有一个，而这个唯一的未来发展所产生的复杂度，却常常在人们的预期与想像之外。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.229.124.159