2、元胞自动机(Cellular Automata，简称CA）

 

诞生：从游戏到科学
元胞自动机本来是现代计算机之父（冯·诺伊曼，Von Neumann)及其追随者提出的想法，但是Wolfram却将这种带有强烈的纯游戏色彩的原始想法从学术上加以分类整理，并使之最终上升到了科学方法论。元胞自动机的基础就在于“如果让计算机反复地计算极其简单的运算法则，那么就可以使之发展成为异常复杂的模型，并可以解释自然界中的所有现象”的观点。

受挫：主流眼中的异端
20世纪1980年代这一理论成了人们议论的话题，比如“雪花的结晶”、“海螺的图案”或者“基于相对论的扭曲时空”等自然界的各种各样的模型都确实可以由这种“反复计算”而生成，这一切不断地证明了Wolfram的观点。但是他的观点当时却被科学界中的主流斥为“异端”。

淡出：十年磨一剑
此后，Wolfram开发了名为Mathematica的、在工作站上使用的Calculus(以微积分为主的解析计算)工具，并在商业上获得了成功，由此也积累了相当的财富。他利用这笔财富成立了专用于科学计算的Mathematica软件开发公司，该公司进入正常发展轨道后，他实际上就已经脱离了经营领域。 进入1990年代后Wolfram完全沉默了。悠然自得的他把生活中的全部时间都用在了思考和计算上，专心致志地从事阐明宇宙原理的工作。Wolfram在2002年出了一本他写了十几年的科学巨著，象辞海那么厚，名字叫《A New Kind Of Science》。甚至有人传言就连Wolfram本人也自信地表示，这部著作是“与牛顿发现的万有引力基本原理相媲美的科学金字塔”。甚至有人说，如果一个理工科大学毕业生不知道Mathematica软件或者Stephen Wolfram这个人，那么他的学位应该算不合格的。Wolfram认为，传统的科学建立在数学基础上，新的科学建立在计算机程序上；数学只能表达相对简单的科学规律，不能描述复杂现象，比如生物世界、湍流、社会、思维、经济、股票等。他的新科学的要点在于，宇宙的一切规律都可以由简单的程序经过反复计算而得到。这可能揭示了前所未知的科学本质。

颠覆：学科分类
根据《一种新科学》中的观点，认为截止目前数千年来发展而成的全部科学从某种意义上讲，依赖的是一种完全无法预测的方法。从物理学、化学、生物学到心理学，甚至各种社会学等现有学术领域本来就不应该进行如此分类。 这些科学领域中各种各样的现象，说到底实际上都在受同一种运算法则的支配，利用各种方法对此反复计算就可以生成各种领域的复杂现象。Wolfram认为，“支持整个宇宙的原理无非就是区区几行程序代码”。 从“完全打破现有的学术体系，按照完全不同的原理来理解自然界”。

核心：计算机万能
也可以把Wolfram的观点称作是计算机万能理论。以物理学和数学为中心的传统科学是以方程式为基础而演绎推导出来的，但是在自动机方面，则是通过反复计算单纯的程序代码，也可以说是递归推导而出的。在牛顿生活的17世纪，由于还没有像现在一样的先进计算机，因此当时的科学家不得不依赖于演绎的方法(算式计算)。这一切也可以说是历史上的必然、科学上的偶然。Wolfram认为：真正意义上的正确的科学方法是利用像现有那样的计算机来进行的算法运算。

 

元胞自动机是一种时空离散的局部动力学模型，是复杂系统研究的一个典型方法，特别适合用于空间复杂系统的时空动态模拟研究。CA自产生以来，被广泛地应用到社会、经济、军事和科学研究的各个领域。应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、歹境、军事学等。

 

附注：Wolfram1959年出生于伦敦，父亲是相当成功的作家，母亲是牛津大学的哲学教授。他幼年聪慧，13岁入伊顿（Eton）公学，15岁发表首篇粒子物理方面的学术论文，到17岁，他的科学论文发到了《核物理》（Nuclear Physics）杂志上。在获得牛津大学奖学金并在牛津学习一年之后，即到美国阿贡国家实验室的理论高能物理小组工作。1978年，19岁的Wolfram受著名物理学家穆雷·盖尔曼（Murray Gell-Mann）之邀赴加州理工学院，从事基本粒子物理学方面的研究，一年内获得理论物理学博士学位。1981年他成为历史上最年轻的麦克阿瑟“天才”奖（MacArthur "Genius" Fellowship）获得者。他早年研究粒子物理，后来转搞元胞自动机，取得了一系列突出成绩，开创了复杂系统研究这一新领域。

 

 

CA是一时间和空间都离散的动力系统，是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。CA不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。

 

元胞自动机的构建没有固定的数学公式，构成方式繁杂，变种很多，行为复杂。故其分类难度也较大，自元胞自动机产生以来，对于元胞自动机分类的研究就是元胞自动机的一个重要的研究课题和核心理论，在基于不同的出发点，元胞自动机可有多种分类，其中，最具影响力的当属S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类，而基于维数的元胞自动机分类也是最简单和最常用的划分。除此之外，在1990年，Howard A.Gutowitz提出了基于元胞自动机行为的马尔科夫概率量测的层次化、参量化的分类体系(Gutowitz, H. A. ,1990)。下面就上述的前两种分类作进一步的介绍。同时就几种特殊类型的元胞自动机进行介绍和探讨S. Wolfrarm在详细分忻研究了一维元胞自动机的演化行为，并在大量的计算机实验的基础上，将所有元胞自动机的动力学行为归纳为四大类(Wolfram. S.，1986):

 

在一个有限的规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的相同的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。

元胞自动机最基本组成:元胞、状态、元胞空间、邻居、规则五部分。
元胞。元胞又可称为单元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。
状态。状态可以是{0,1}的二进制形式。或是{s0,s2,……si……sk}整数形式的离散集，严格意义上，元胞自动机的元胞只能有一个状态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。
元胞空间。元胞所分布在的空间网点集合就是这里的元胞空间。 目前研究多集中在一维和二维元胞自动机上。对于一维元抱自动机，元胞空间的划分只有一种。而高维的元胞自动机，元胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机，二维元胞空间通常可按三角、四万或六边形三种网格排列。

邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但最常用的规则四方网格划分，如冯-诺依曼(Von. Neumann)型（一个元胞的上、下、左、有相邻四个元胞为该元胞的邻居）、摩尔(Moore)型（一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该元胞的邻居）、扩展的摩尔(Moore)型（邻居半径扩展为2或者更大）、马哥勒斯 (Margolus)型等。

规则。决定一个元胞下一时刻的状态动力学函数，简单讲，就是一个状态转移函数。我们将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数。可以是定性的，也可以是定量的。

时间。元胞自动机是一个动力系统，它在时间维上的变化是离散的。在上述转换函数中，一个元胞在t+1的时刻只(直接)决定于t时刻的该元胞及其邻居元胞的状态，虽然，在t-1时刻的元胞及其邻居元胞的状态间接(时间上的滞后)影响了元胞在t+1的时刻的状态。

 

CA的程序很多，由于其变种很多，因此没有固定的软件。一下是一些连接可以借鉴：

萝卜驿站 http://luobo.ycool.com/archive.57000.html

（图片来自互联网）