元胞自动机与现代科学中的计算主义
摘要: 元胞自动机理论的研究领域是滋生计算主义思潮的温床，元胞自动机理论的发展强有力的支持了计算主义的观点。因此，元胞自动机也是理解计算主义观点的一个枢纽。论文试图通过详细介绍元胞自动机理论来解释和剖析计算主义的观点。同时出于需要，论文还简要介绍了与讨论相关的计算理论和生命科学、人工智能、人工生命等领域的一些发现及观点。
元胞自动机与现代科学中的计算主义
引言 1
第一章 计算理论简介 2
第二章 计算主义观点简介 4
2．1 宇宙的本原是计算的观点 4
2．2 生命的本质是计算的观点 5
2．3 计算主义及其观点综述 7
第三章 认识元胞自动机 7
3．1 元胞自动机概念的提出 7
3．2 从不同视角理解元胞自动机 8
3．3 元胞自动机的基本元素 10
3．4 元胞自动机的特征 14
第四章 元胞自动机理论的发展轨迹 14
4．1 康卫与生命游戏 14
4．2 沃尔夫拉姆对元胞自动机的分类 17
4．3 朗顿的工作与“混沌边缘” 32
4．4 人工生命科学的诞生与发展 39
4．5 元胞自动机理论的继续发展 40
4．6 弗雷德金猜想 41
4．7 《一种新科学》的诞生 42
第五章 元胞自动机理论的思想意义 45
第六章 元胞自动机与计算主义 47
6．1 元胞自动机理论对计算主义的支持 47
6．2 评价 48
6．3 小结 50
致谢 51
参考文献 52
引言
一 种“把一切归结为计算，归结为方程式，归结为数学，归结为逻辑，追求对世界解释的完美性”的思想倾向一直在科学界蔓延。在物理学界，他们曾经认为世界已经 被牛顿力学方程完美的描述，我们剩下所能做的便是提高我们的计算能力。在经济学界和社会学界，他们把一切数字化和量化，并试图将一切现象之间的联系用数量 关系来解释。在生命科学领域，他们坚信人工智能是可能的，生命可以在实验室创造。哲学界，他们认为人是机器。他们把一切科学归结为数学，而在数学界，他们 又试图构造完美无暇、无矛盾而又具有完备性的数学体系。他们这种“还原论”“决定论”“盲目量化”“一切都是数学”的观点，遭到了不同的领域的学者理性的 非难和强烈的抨击，随着科学的发展，在新的科学发现事实面前，逐步缩小它的领地。而它的反面，即“重视实验”、“尊重定性分析”、“重视模拟”、“承认不 确定性”、“承认不完备性”的观点，却在各个领域不断发扬光大。
但 是，近年来，一种新的类似于上述观点但与其有很多不同―我们不妨称之为“计算主义”―的观点，即“生命的本质是一种计算”，“自然界这本大书是用算法语言 写的”，“宇宙是一个巨大的计算系统”等等观点又在科学界时髦起来，在计算理论、现代生命科学、人工生命、人工智能等几个不同领域的学科出现的新进展都不 约而同的显示了“计算”的重要性，从而为计算主义观点的诞生提供了肥沃的土壤。它认为人类应该从一个全新的视角，即计算的视角来理解我们的世界。
元 胞自动机理论的研究领域是滋生计算主义思潮的温床，元胞自动机理论的发展强有力的支持了计算主义的观点。因此，元胞自动机也是理解计算主义观点的一个枢 纽。论文试图通过详细介绍元胞自动机理论来解释和剖析计算主义的观点。同时出于需要，论文还简要介绍了与讨论相关的计算理论和生命科学、人工智能、人工生 命等领域的一些发现及观点。
第一章 计算理论简介
为了使读者能更好的理解后面有关元胞自动机的理论，特在此对计算理论的几个概念作一个简要的通俗介绍，作为知识预备。
概念一：计算。
“计算”是一个无人不知无人不晓的数学概念。然而，正如爱因斯坦（Albert Einstein）所说，“一个概念愈是普遍，愈是频繁地进入人们的视野，我们要想理解它的意义也愈困难”。因此，虽然人类很早就学会了加、减、乘、除等的运算，但直到20世纪30年代以前，还没有什么人能真正说清楚计算的本质。从20世纪30年代开始，由于哥德尔(Gödel)、邱奇(Church)和图灵(Alan Turing)等人的工作，人们终于对计算的本质有了清楚的理解，由此形成了“计算理论”这一专门的数学分支，并因此导致计算机科学的诞生。
简单地说，计算就是输入到输出的一种变换。如果我们把一切看作信息，那么计算就是对信息的变换。具体说，从一个已知的输入i开始，按照一定的规则，经过有限步骤，最后得到一个输出o，这种变换过程就是计算。比如，从字符串“1+1”变换成“2”就是一个加法计算，从“1＋1＝2”变换为“true”是一个逻辑计算，语言的翻译也都是计算，由x经过函数变化为F(x)也是计算，把一个小球扔到地上从地上弹起来，也是一个计算，因为我们可以把大地当成一个系统，扔下去的小球是一个输入，弹回来的小球便是一个输出。
这样理解，你就会发现世界到处都是计算了。目前的科学界，DNA计算机、生物计算机、量子计算机等概念频频出现，无非是把DNA的化学反应、量子世界的波函数都看作计算了。
概念二：算法。
与计算紧密联系的一个概念是“算法”。算法是求解某类问题的通用法则或方法，即从输入变换到输出的规则。人们常常把算法看成是用某种精确的语言写成的程序。程序的执行和操作就是计算。从算法的角度讲，一个问题是不是可计算的，与该问题是不是具有相应的算法是完全一致的。
概念三：图灵机。
上世纪30年代，图灵提出了“图灵机”（Turning Machine）模型。它是一个典型的计算模型，即它能够由一定输入得到一定输出。
图灵机的模型如下图所示：
在 图中，下面是一条无限长的纸带，分为很多格子，每个格子有自己的状态。上面是一个有限状态控制器，有其内部状态。控制器上有个读写头，能够读取纸带上的每 一个格子的状态。控制器由一个程序来控制，它根据程序的命令、读取到的纸带上的状态以及自身的状态来进行纸带的读写，或者在纸带上前后移动一格。
图灵机有个“停机状态”，遇到该状态，就会自动停机。
纸带上的格子的信息便是输入，最后图灵机停机之后得到的纸带便是其输出。
图灵机能够停机，便完成了一个正常的计算过程。如果不能停机，说明图灵机进入了死循环，那么证明图灵机无法完成相应的计算过程。
人 们发现，只要设置好合适的输出输入的格式、内部状态以及控制程序，几乎现实中的所有计算，都能用图灵机来计算，包括加减乘除四则运算、微分、积分、平方开 方等，甚至判别一个数是否是质数、判断一个程序中是否有错误、判断一个方程是否有解等等。于是，人们定义图灵机具有最高的计算能力，而把图灵机不能计算的 问题，也就是图灵机不能停机的问题叫做不可计算的。不可计算的问题具有不可计算性，或者不可判定性。著名的“波斯特问题”，“希尔伯特第十问题”，“图灵 停机问题”等都是不可计算的问题。图灵机能够计算的问题则在习惯上称为“丘奇命题”。
概念四：计算等价性。
计算等价性是指两种计算模型具有相同的计算能力。即所有相同的输入，一定会在二者间得到相同的输出。
图灵机只是一种计算模型，后来，人们发现了各种各样的计算模型。有些计算模型计算能力不强，即图灵机能够计算的问题，它却不能计算。有些计算模型计算能力能够与图灵机等价，例如递归函数、λ演算，动态网络模型，受限生成系统1等。没有一种计算模型的计算能力能超过图灵机。任一计算模型都以取得跟图灵机等价来表明其具有最高的计算能力。
现在，我们日常生活中所见到的计算机大都采用冯·诺伊曼(J. von Neumann)结构，其计算模型也是计算等价于图灵机的。
概念五：通用图灵机。
如果一台图灵机能够模拟任何一台特殊图灵机，那么就称其为“通用图灵机”（Universal Turning Machine）。如果把信息X输入到图灵机M中，得到结果O，那么如果把X和M的信息都输入给通用图灵机N，那么该通用图灵机也能输入O。已经证明了，通用图灵机是存在的。
概念六：计算的不可化归性。
我们发现，有些算法是易于观测的，不用看着它一直运行下去就能推断出输出结果。但是有些算法却不是这样，消耗时间最少的预测方式就是看着它运行下去，这就是计算的不可化归性（computational irreducibility）。
图灵在上世纪30年代证明了所谓的“不可判定定理”，其内容是说：无论你认为自己有多么聪明，总有算法超出你的事先预测能力。
第二章 计算主义观点简介
2．1 宇宙的本原是计算的观点
泰勒斯说“万物的本原是水”；毕达哥拉斯说“万物的本原是数”；德谟克利特说“万物的本原是原子”；到了如今这个计算机时代，计算机科学家们站出来说“万物的本原是计算”。
控制论的创始人维纳（Norbert Weiner）在1948年的《控制论》（Cybernetics）中提出宇宙的基本构件是信息的传递，而不是能量。麻省理工学院的计算机科学家弗雷德金（Edward Fredkin）将这一思想发扬光大，在20世纪80年 代早期提出了他的“新物理学理论”，认为宇宙由最基本的计算软件构成。终极的实在不是粒子或力，而是根据计算规则变化的数据比特。世界是由一份一份的信息 构成，宇宙是离散的而不是连续的。弗雷德金热情地宣称：“在这世界中，没有什么是像比特这样具体的构件，它比光子或电子更具体，它不是实在的模仿，它不是 假扮实在的东西，它就是实在。宇宙是一部巨型的计算装置，任何自然事件都是在自然规律作用下的计算过程。现实世界的多样性不过是算法的复杂程度不同的外部 表现。从虚无到存在，从非生命到生命，从感觉到思维，整个世界的演化，实际上都是一个计算复杂性不断增加的过程。”诺贝尔物理奖获得者费曼（Richard Feynman）在1981的一篇论文里也表达过类似的观点。
同时供职于密歇根大学和圣塔菲研究所(Santa Fe Institute)的学者约翰·霍兰德（John Holland）在其1998年的著作《涌现》中，提出“受限生成过程”模型。他认为，世界上的很多现象本质上都是“复杂适应系统”，而具有可变结构的受限生成过程再加遗传算法可能就是这类系统的一般性解释。很显然，霍兰德是试图用一种通用的算法来解释世界。在他的眼里，世界也是一个计算过程。
2．2 生命的本质是计算的观点
宇宙的万事万物都是计算，那其中最具特色的生命也是计算吗？
生命的最大的特征是能够思维。尽管人们对于人脑的结构还远不清楚，但人类却很早就从计算的视角审视人的思维本质了。最早涉足的是哲学家。拉美利特曾简单的认 为，人是机器，人脑是机器的一个部件；洛克曾把思维的本质看作是计算；莱布尼兹也认为，一切思维都可以看作是符号的形式操作的过程。真正把思维理解为计算 并付诸实施的是计算机领域的科学家。1950年图灵在《心》（Mind） 杂志上发表了一篇题为“计算机器与智能”的文章，开篇就写道：“我准备考虑这样一个问题：机器能思维吗？”在这篇文章中，他提出了著名的“图灵检验”的思 想，以说明机器能够像人一样具有智能。图灵认为，人的大脑应当被看作是一台离散态机器。尽管大脑是由粘糊糊的“凉粥”一样的物质组成，电子计算机是由生硬 的金属物质组成，但它们的本质则是相同的。离散态机器的行为原则上能够被写在一张行为表上，因此与思想有关的大脑的每个特征也可以被写在一张行为表上，因 而能被一台计算机所仿效。在该论文中，图灵详细论证了思维的计算本质，并批驳了反对机器能够思维的多种可能的意见。他坚信人脑不会超越图灵机模型。
的确，图灵机可以极其巧妙的模仿人脑。人有记忆，图灵机有内部状态，就是其记忆。人有情绪和喜怒哀乐，这只不过对应于图灵机不同的规则而已。人能学习，图灵 机虽然在运行中是不能改变其程序的，但是却很有可能激活了它的某个内部状态，导致其行为发生了本质变化，这样给它相同的输入，它给出了完全不同的输出，这 就是学习。
在图灵的影响下，麦卡锡(J. McCarthy)、明斯基(M. L. Minsky)、西蒙(H. A. Simon)和纽厄尔(A. Newell)等 人开创了人工智能这样一门新的学科。人工智能是认知科学与计算机相互交叉的学科。此后经过多年的努力，物理符号系统假说、心灵的表征计算理论等也相继提 出。这些学说的共同特点都是把思维的本质看作是计算，把思维看作是一种信息加工过程。尽管符号学派后来受到联结主义和基于行为的人工智能学派的挑战，但思维的本质是计算这一基本的人工智能假说并没有被抛弃。
目前我们用计算机进行的辅助设计、翻译、检索、绘图、写作、下棋、机械作业等方面的发展，已经向计算机的智能化迈进了一步。世界头号国际象棋大师卡斯帕罗夫在1997年向IBM公司的超级计算机“深蓝”的俯首称臣，让人脑第一次尝到了在电脑面前失败的滋味。但是，冯·诺 伊曼型计算机在认字、识图、听话及形象思维方面的功能特别差，跟人脑无法比拟，这又促使生命科学家对人脑进行进一步的研究，而计算机科学家们则对其研究成 果进行借鉴。近年来，各国学者开展人工神经网络的研究，向计算机的智能化迈出了重要的一步。有学者猜测，智能计算机的构成，可能就是作为主机的冯·诺依曼机与作为智能外围的人工神经网络的结合。同时，目前至少有三种技术有可能引发全新的革命，它们是光子计算机、生物计算机和量子计算机。人们普遍认为智能计算机将像穆尔定律2的应验那样必然出现。提出这一定律的Intel公司名誉董事长戈登·穆尔本人也同意这一看法，他认为“硅智能将发展到很难将计算机和人区分开来的程度。”但是计算机智能不会到此为止。许多科学家断言，机器的智慧会迅速超过爱因斯坦和霍金（Stephen Hawking）3的智慧之和。霍金预言：“就像人类可以凭借其高超的捣弄数字的能力来设计计算机一样，智能机器将创造出性能更好的计算机。最迟到21世纪中叶（而且很可能还要快得多），计算机的智能也许就会超出人类的理解能力。”
生命的第二个特征是能够生长、发育、遗传和自我繁殖。在计算理论的影响下，一些生物学家也开始从计算的视角来思考生命的遗传问题。1994年11月，美国科学家阿德勒曼（L. M. Adleman）在《科学》（Science）杂志上发表的关于DNA计算机理论，从另一个方面说明了生命的计算本质。通过把图灵机与生物细胞内DNA自我复制过程的比较，阿德勒曼得出结论：细胞就是计算机，DNA聚合酶合成互补DNA链事实上就是一种计算过程。他还说明了如何通过对DNA编程来改变其结构，使之进行各种计算。这个事实给了人类某种启发，或许，生命系统事实上就是一台以分子算法为组织法则的多层次的计算网络。
目前，生命科学进入到以破译基因信息为主要内容的后基因组时代。在这一时代，计算将成为生命科学的一个重要内容。基因组是生命的信息库和程序库。生命的生 长、发育、分化、免疫反应等特征本质上是包含在基因组中的生命信息和程序的表达和执行的表现。所有的生命信息和程序都以不同的形式记载在A、G、T、C四种碱基书写的一维DNA序列中。生命的奥妙就藏在这本四字天书里面。人类基因组序列的巨大数据，必须借助计算机技术来存储和分析。生物信息学、基因组语言学和计算生物学就是在这样的背景下产生的新兴学科。它们利用计算机和新的数学分析方法，分析生物基因组的序列数据，寻找生物生长和发育规律。
另一方面，计算机科学者在计算机上面开展了对自我复制的研究。元胞自动机正是冯·诺伊曼在这一研究过程中提出的概念。后来，在元胞自动机理论的进一步发展的基础上，朗顿（Langton）开创了人工生命这一新兴学科，从生命的“生长，繁衍，自我复制”等角度揭示了生命的计算本质。
在世纪之交的2000年， 科学界的两大成就引起世人的广泛关注，这就是人类基因组序列的测定和可进行自我设计与进化的进化机器人的出现。人类基因组序列的测定产生了广泛的社会反 响，进化机器人的出现也引起不小的震动，尽管由于对前者的过分关注影响了一些人对后者的关注。人类基因组研究的是一般生物学的内容，而进化机器人的出现则 是人工生命领域的突破。这两个研究领域虽然形式完全不同，而且前者是着重从生命的生长繁衍的特征入手，后者从生命能思维的特征入手，但它们的目标都是试图 理解生命的本质，手段都是采用计算的方法。两个领域的研究和突破说明，信息、算法和计算等概念已经成为理解生命本质的重要概念。
2．3 计算主义及其观点综述
前 面介绍的包括计算理论、人工智能、生命科学、人工生命等各个领域的一些观点内容与形式都不尽一样，有的甚至相互迥异并各执一词，持这些观点的学者们也没有 自发的形成一个团体，更没有给自己的理论贴上“计算主义”的标签，但是他们的观点却表达了一种共同的倾向，那就是“计算”或者“算法”在理解世界和生命的 时候非常重要。
基 于计算或算法的观念在当今已经渗透到宇宙学、物理学、生物学乃至经济学和社会科学等诸多领域并取得丰硕成果的事实，出现了一批学者，强烈的鼓吹计算或者算 法的作用。他们认为：计算不仅应该成为人们认识自然、生命、思维和社会的一种普适的观念和方法，而且应该成为一种新的世界观。整个世界都是由算法控制，并 按算法所规定的规则演化的。宇宙是一部巨型的计算装置，任何自然事件都是在自然规律作用下的计算过程。现实世界事物的多样性只不过是算法的复杂程度的不同 的外部表现。整个世界的演化：从虚无到存在，从非生命到生命，从感觉到思维，实际上都是一个计算复杂性不断增加的过程。
我们为行文方便，不妨称呼他们的观点为“计算主义”4（Computationism）或者“算法主义”（Algorithmism）。而同时，将一大批持有此类观点的学者称之为“计算主义者”。
计算主义的核心观点概括起来就是：
1．世界的本质就是计算，宇宙就是一台计算机，世界上所有现象表现为一种算法过程。
2．生命的本质是计算，生命的思维本质是计算，生命的生长、发育、遗传、自我繁衍等特征都是计算。
第三章 认识元胞自动机
3．1 元胞自动机概念的提出
上世纪50 年代，在图灵提出人的大脑是一台离散态的计算机的思想几乎同一时期，计算机科学的另一个开创者冯·诺伊曼即开始从计算的视角思考生命的本质问题，他认为自我复制乃是有生命的物体的独一无二的特征，也是被称之为生命的必要条件。为了构造一个能够自我复制的机器，冯·诺伊曼提出了元胞自动机的概念。在提出这个概念的过程中，他在洛斯阿拉莫斯（Los Alamos）的同事数学家乌拉姆（Stanislaw M. Ulam）曾给予他一定启发。
冯·诺依曼在逝世前证明了起码有一种确实能够自我繁衍的元胞自动机模型的存在。这个模型极其复杂，要求大量的细胞格，而且每一个细胞有二十九种不同的状态，这是任何现有计算机的模仿功能都无法胜任的。但这种模型确实存在的事实回答了根本的原则问题。
从此，由元胞自动机来构造具有生命特征的机器成为科学界的一个新的方向，而对元胞自动机理论本身的研究开始逐步展开。
3．2 从不同视角理解元胞自动机
元胞自动机，英文名Cellular Automata，简称CA，有的文献中译为细胞自动机、分子自动机、点格自动机或单元自动机等等。冯·诺 依曼和乌拉姆只是给出了一个初步的基本的概念。此后，经过物理学家、数学家、计算机科学家、生物学家以及其它学科的学者们共同工作，元胞自动机成为一个地 地道道的“混血儿”。因此，对元胞自动机的含义也存在不同的解释。而且，元胞自动机构成方式繁杂，在各个领域变种很多，行为复杂，而且有着较为宽松、甚至 近乎模糊的构成条件。这里，仅选取几个易于理解的角度来对其进行描述。5
视角一：物理学视角。
元胞自动机由一些被称为“元胞”的基本部件组成，每个元胞可以具有一些状态，例如或“生”或“死”，或者是7种 颜色中的一种，等等。这些状态应该是离散的，而且元胞在某一时刻只能处于一种状态之中，例如要么就“生”，要么就是“死”。这些元胞规则地排列在被称为 “元胞空间”的空间网格上。元胞空间可以是一维、二维或多维的欧几里德空间。网格是离散的，且每个网格只能容纳一个元胞。元胞的状态会随着时间变化，而且 时间步也是离散的。每个元胞的状态变化是依据某个确定的规则。规则一般定义为：一个元胞在下一时刻的状态由此时刻所围绕着它的那些元胞的状态以及它自身的 状态所共同决定。
元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化。
概括起来说，元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上进行演化的动力学系统。
视角二：生物学视角。
以生物学或者人工生命的角度来看，元胞自动机可以视为一个让许多单细胞生物生活的世界，在我们设定好这个世界的初始状态和进化规则之后，这些单细胞生物便依据规则在离散的时间步上进行演化。
视角三：数学视角。
对以上描述，我们可以将其用数学符号来表示。标准的元胞自动机是一个四元组 :
A=(Ld,S,N,f)
这里A代表一个元胞自动机系统；L表示元胞空间，d是一正整数，表示元胞空间的维数；S是元胞的有限的、离散的状态集合；N表示一个邻域内所有元胞的组合，即包含n个不同元胞状态的一个空间矢量，记为:N=(s1,s2,...,sn)，其中si∈S，i∈{1，...,n}；f表示将Sn映射到S上的一个局部转换函数。所有的元胞位于d维空间上，其位置可用一个d元的整数矩阵Zd来确定。
视角四：计算视角。
按照计算理论，凡是信息的变换都是计算。显然，元胞自动机每一个元胞的状态变化都是一种计算。我们可以把每一个元胞都看作一台计算机，这样元胞自动机就是一种计算模型。
我们看到，元胞自动机每个元胞的变化是同步进行的，也就是对信息的处理是同步进行的，特别适合于并行计算。元胞自动机可能是下一代并行计算机的雏形。
元胞计算是目前的研究热点。其特点是大量和并行，跟传统的冯·诺伊曼计算机结构不同。
视角五：动力学视角。
元胞自动机可以视为离散动力系统中的一种自动器网络模型。
离 散动态系统中自动器网络模型的基本结构可用图论中的图来表示，它由若干结点及连接这些结点的边而构成，但在自动器组成的复杂网络模型中，我们还可引入不同 层次的动力学，即每个结点表示一个子系统，它们有各自的动态行为，结点之间的连接强度也可能发生变化，由此反映元素间作用关系的变化。每个结点（或元素） 都可以看作是一个自动器，这些连接起来的自动器组成了自动器网络。若干自动器（automation）叫作自动机（automata）。
自动器的经典定义可以简单地表示为三种集合与两个映射是离散映射的特殊形式。如图：
输入符号集,状态变量集
,输出变量集
,其中
均为矢量。
映射,即
为状态变化函数，它将系统在
时刻的的输入和状态映射为系统在
时刻的状态。
映射，即
为输出函数，它将系统在
时刻的输入和状态映射为系统在
时刻的输出。
如果一个自动器网络具有规则的晶格结构，每个元素是完全一样的有限自动器（相同的局部连接即输入集和输出函数相同），且元素间的联接强度为常数，这样的自动器网络称为“元胞自动机”。
若自动器网络的元素是一布尔自动器（状态为0和1）且状态函数为布尔开关函数，元素间联接强度不变，则我们得到“布尔网络”。
当元素间联接强度可随时间变化时，网络的行为就变得更复杂，这将是“神经网络”要讨论的问题。
复杂系统理论中研究的这些自动器网络模型的共同特点在于：
(1) 涉及的元素数量较大（从几个到成千上万）；
(2) 元素间局部联接；
(3) 系统总体体现了鲜明的涌现性。
元胞自动机、神经网络、布尔网络、L系统等相互联系，关系密切。例如目前，一种被称为元胞神经网络(Cellular Neural Network，简称CNN)的模型就是元胞自动机与神经网络结合的产物。
3．3 元胞自动机的基本元素
1.元胞
元胞又可称为单元、基元或细胞，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的网格上。
2.元胞状态
在实际应用中，元胞状态一般是{s0,s1,……si……sn}整数形式的离散集。对于其它类型的取值，比如“红”“白”等颜色取值，可以映射到整数集上。
严格意义上，元胞只能有一个状态变量，但在实际应用中，可以将其进行扩展，使得每个元胞拥有多个状态变量。
3.元胞空间
元胞所分布在的空间网格集合就是元胞空间。对于元胞空间，有几个特征需要注意。
(l)几何划分
理论上，元胞空间可以是任意维数的欧几里德空间，但目前研究多集中在一维和二维元胞自动机上。
对一维元胞自动机的系统研究最早，相对来讲，其状态、规则等较为简单，往往其所有可能的规则可以一一列出，易于处理，研究也最为深入。目前，对于元胞自动机的理论研究多集中在一维元胞自动机上。美国学者沃尔夫拉姆（Stephen Wolfram）对元胞自动机的动力学分类也是基于对一维初等元胞自动机 (Elementary Cellular Automata，简称ECA)6的分析研究得出的。它的最大的一个特征在于容易实现元胞自动机动态演化的可视化：在二维显示中，一维显示其空间构型，即空间维；另外一维显示其发展演化过程，即时间维。
二维元胞自动机是指元胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以英国学者康卫（John Horton Conway）的“生命游戏”（Game of Life）7为代表，应用最为广泛。由于世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法转换到二维空间上。所以，二维元胞自动机的应用最为广泛。
对于最为常见的二维元胞自动机，二维元胞空间通常可按三角、四万或六边形三种网格排列，如下图：
这三种规则的元胞空间划分在构建模型时各有优缺点。
三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有用；其缺点是在计算机的表达与显示不方便，需要转换为四方网格。
四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表达与显示;其缺点是不能较好地模拟各向同性的现象。显然，如果考查某个方格的和它的八个邻居的关系，“东”、“南”、“西”、“北”正方向和“东南”、“西北”、“东北”、“西南”等方向是不一样的。
六边形网格的优点是能较好地模拟各向同性的现象，因为针对某个方格来说，它的六个邻居的地位是一样的。因此，模型能更加自然而真实;其缺点同三角网格一样，在表达显示上较为困难、复杂。
对于三维元胞自动机， 某些学者在这方面做了若干试验性工作，例如在三维空间上实现了“生命游戏”，延续和扩展了一维和二维元胞自动机的理论。至于更高维元胞自动机，只是在理论上进行少量的探讨，实际的系统模型较少。
(2)边界类型
在理论上，元胞空间通常是在各维度上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要定义元胞空间的边界。例如，可以定义如下几种边界:周期型、反射型、定值型、随机型。
周期型边界(Periodic Boundary)是指相对的边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的“圈”。对于二维空间，上下相接、左右相连而形成一个拓扑圆环面 (Torus)，形似车胎或甜点圈。周期型空间与无限空间最为接近，因而在理论探讨时，常用此类边界来设计模型。
反射型边界(Reflective Boundary)指在边界外邻居的元胞状态是以边界为轴的镜面反射。例如在一维空间中，当r=1时的边界情形:
定值型边界 (Constant Boundary)指所有边界外元胞均取某一固定常量，如0、1等。
有时，在应用中，为更加客观、自然地模拟实际现象，还有可能采用随机型边界(Random Boundary)，即在边界实时产生随机值。
需要指出的是，这几种边界类型在实际应用中，尤其是二维或更高维数的建模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型。
(3)构型(Configuration)
在这个元胞、状态、元胞空间的概念基础上，我们引入另外一个非常重要的概念“构型”。构型是指在某个时刻，在元胞空间上所有元胞状态的空间分布组合。通常，在数学上，它可以表示为一个多维的整数矩阵。构型也被称为全局状态（global state）。
4.邻居
以上的元胞及元胞空间只表示了系统的静态成分，为将动态引入系统，必须加入演化规则。在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须明确哪些元胞是该元胞的邻居。
在一维元胞自动机中，通常以半径来确定邻居，与一个元胞相距在一个半径的距离之内的所有元胞均被认为是该元胞的邻居。
二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式，我们以最常用的规则四方网格划分为例。见下图，黑色元胞为中心元胞，灰色元胞为其邻居，它们的状态一起来计算中心元胞在下一时刻的状态。
l)冯·诺依曼(Von Neumann)型
一个元胞的上、下、左、右相邻四个元胞为该元胞的邻居。这里，邻居半径r为1。
2)摩尔(Moore)型
一个元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞为该元胞的邻居。
3)扩展的摩尔(Moore)型
将以上的邻居半径r扩展为2或者更大，即得到所谓扩展的摩尔型邻居。
4)马哥勒斯 (Margolus)型
这是一种同以上邻居类型迥然不同的形式，它是每次将一个2x2的元胞块做统一处理，而上述前三种邻居模型中，每个元胞是分别处理的。这种邻居类型因为格子气自动机8而得到关注。
有了邻居的定义，我们可以得到引入邻域的概念。邻域就是一个元胞及其所有邻居的集合。
有必要说明的是，邻居并不一定要去“最邻近”的，但是这些“最邻近”的邻居较为符合现实，而且已经足可以代表了所有的元胞自动机。
5.规则
根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数就是规则。
这里我们遇到一个典型的组合爆炸问题。假设元胞自动机中每个元胞存在种状态，其邻域拥有的元胞个数是n，那么邻域存在
种状态。元胞的规则，或称元胞自动机的转换函数，要将
种状态映射为
种状态的一种，则共有
种转换函数存在。假设一个元胞自动机中，每个元胞存在10种状态(
=10)，而且采取冯诺依曼邻居模式连接(
=5)，则共有
种转换函数。这是一个天文数字。
有时候，为了处理问题的方便，或者为了更加接近现实，我们可以定义另外的规则，让规则数量有所减少。比如下面两种：
可逆规则。比如， 可以定义邻域00011和11000是一样的。也就是对于中间的元胞0来说，不管它的“左边是00，右边是11”还是“左边是11，右边是00”，它的下一步状态都是一样的。这很符合现实中某些具有各向同性的物质。按这样的方式进行映射，可以使得规则减少一半。
总和规则。它规定每个元胞的状态，只与其邻域状态之和有关。那样，邻域11010和10011是一样的，因为对于中间的元胞0来说，它的邻域内各元胞的状态总和都为3。这样很符合现实中某些事物的特征，比如“生命游戏”采用的便是总和规则。按这种方式进行映射，可以使规则数量由指数级减少为多项式级。
非常重要的一点就是，沃尔夫拉姆（Wolfram）证明了，总和规则描述的元胞自动机可以展现所有元胞自动机可能表现的动态行为。
除此之外，还有可加规则，压迫规则等等。9
6.时间
元胞自动机是一个动态系统，它在时间维上的变化是离散的，即时间t是一个整数值，而且连续等间距。假设时间间距dt=1，若t=i为某一时刻，那么，t=i+1为其下一时刻。
3．4 元胞自动机的特征
从元胞自动机的构成及其规则上分析，标准的元胞自动机应具有以下几个特征：
同质性：在元胞空间内的每个元胞的变化都服从相同的规律，所有元胞均受同样的规则所支配。
齐性：元胞的分布方式相同，大小、形状相同，地位平等，空间分布规则整齐。
空间离散:元胞分布在按照一定规则划分的离散的元胞空间上。
时间离散:系统的演化是按照等间隔时间分步进行的，时间变量t只能取等步长的时刻点。
状态离散且有限：元胞自动器的状态只能取有限个离散值，在实际应用中，往往需要将有些连续变量进行离散化，如分类、分级，以便于建立元胞自动机模型。
并行性：各个元胞的在每个时刻的状态变化是独立的行为，相互没有任何影响。
时空局部性:每一个元胞的下一时刻的状态，取决于其邻域中所有元胞的状态，而不是全体元胞。从信息传输的角度来看，元胞自动机中信息的传递速度是有限的。
维数高:在 动力系统中一般将变量的个数成为维数。例如，将区间映射生成的动力系统称为一维动力系统；将平面映射生成的动力系统称为二维动力系统；对于偏微分方程描述 的动力系统则称为无穷维动力系统。从这个角度来看，由于任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集，每个元胞的状态便是这个动 力学系统的变量。因此，元胞自动机是一类无穷维动力系统。在具体应用中或计算机模拟时当然不可能处理无限个变量，但一般也总是处理数量很大的元胞组成的系 统。因此可以说维数高是元胞自动机研究中的一个特点。
在实际应用过程中，许多元胞自动机模型已经对其中的某些特征进行了扩展，例如圣托斯兰州立大学(San Tose State University)研究的所谓连续型的元胞自动机，其状态就是连续的。但正如我们在元胞自动机的概念分析中指出的，在上述特征中，同质性、并行性、局部性是元胞自动机的核心特征，任何对元胞自动机的扩展应当尽量保持这些核心特征，尤其是局部性特征。
第四章 元胞自动机理论的发展轨迹
元胞自动机理论产生以来，得到了长足的发展。下面进行一个简单的回顾。
4．1 康卫与生命游戏
生命游戏是由剑桥大学的数学家康卫于 1970 年 发表于《科学美国人》上的论文所提出的。理论上，它是一个二维元胞自动机。在这个元胞自动机中，元胞空间是一个分割成很多四方格子（类似棋盘）的平面，初 始状态时，某些方格上存活着单个元胞。播种可以是随机的，也可以指定确定的模式，以便考察一些特殊的行为。每一个元胞有八个邻居，即采用摩尔邻居形式。这 些元胞有两种状态：“生”或“死”，存活的元胞我们在方格内涂上特定单一的颜色，而死亡的元胞我们则不涂色。一个元胞的生死由其在该时刻本身的生死状态和 周围八个邻居的状态决定，更确切的讲是周围八个邻居的状态的和决定。其规则叙述如下：
◆ 对于存活的元胞（涂色的方格）：当八个邻近元胞中只有零个或一个是活元胞时，则该元胞会因孤独而死亡；当八个邻近元胞中，恰有二或三个是活元胞时，则该元胞继续存活；当八个邻近元胞中，有四个或超过四个是活元胞时，则该元胞会因拥挤而死亡
◆ 对于死亡的元胞（未涂色的空方格）：当八个邻近元胞中，恰有三个是活元胞时，则该处诞生一个活元胞
生命游戏的演化规则近似地描述了生物群体的生存繁殖规律：在生命密度过小(相邻元胞数<2)时，由于孤单、缺乏配种繁殖机会、缺乏互助也会出现生命危机，元胞状态值由“生”变为“死”;在生命密度过大 (相邻元胞数>3)时，由于环境恶化、资源短缺以及相互竞争而出现生存危机，元胞状态值由“生”变为“死”;只有处于个体适中(相邻元胞数为2或3)位置的生物才能生存(保持元胞的状态值为“生”)和繁衍后代(元胞状态值由“死”变为“生”)。正由于它能够模拟生命活动中的生存、灭绝、竞争等等复杂现象，因而得名“生命游戏”。
尽管生命游戏的规则看上去很简单，但是它具有产生动态图案和动态结构的能力。它能产生丰富的、有趣的图案。笔者用java编了一个Applet程序用以研究，图例如下：
运行这个程序的时候，我们发现，透过不同的设计，生命游戏可以展现无限的多样性。其演化结果与初始元胞状态值的分布有关，给定某个的初始状态分布，即随意的 设置一些活着的元胞，经过若干步的运算，有时候它们会全部死亡，即变成全黑的图案，有时候则生成固定不动的图案，有时候生成翻滚不已的图案，有时候则得到 周而复始重复的几个图案，更多的时候，是得到沸腾着的各种结构，有的图案蜿蜒而行，有的则保持图案定向移动，形似阅兵阵……，其中最为著名的是“滑翔机”(Glider)的图案，即一小簇以常速滑过屏幕的活元胞，在四个世代的一个循环中，它沿着对角线的方向在方格上爬行，转换自己的位置，一个正方形向右，一个正方形向下，直到与其它结构相撞，产生出新的结构。
康卫为了证明生命游戏就是一台通用计算机，他悬赏50美元找人反驳他的一个假设：生命游戏的有限初始构型不可能产生无限的结构。
麻省理工学院人工智能小组的高斯普尔（R. William Gosper）很快在生命游戏中发现了稳定的发射出新的“滑翔机”的“滑翔机枪”，吞噬“滑翔机”或者使其反转回去的其它结构10，以及在向前运动过程中不断在后面留下烟雾的“喷气火车”结构。其中，“滑翔机枪”结构每30步发射出一个新的“滑翔机”，如果整个网格空间足够大，时间也足够长的话，这种结构就能在网格空间上发展为无限多。这也说明了每重复运行一次，出现在屏幕上的图案都可能有所不同，从而无法穷其可能性。这个发现成功的驳倒了康卫的假设。
由 于这个突破，康卫利用“滑翔机枪”和许多其它单元作为基础，成功了构造了与、或、非等逻辑门，然后更进一步证明了生命游戏足以支持通用的计算，即这个元胞 自动机具有通用图灵机的计算能力，与图灵机计算等价。也就是说给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。
目前随着人们对生命游戏研究的深入，产生了许多变种和扩展。在上个世纪80年代末，A·K·Dewdney 和C·Bays 将Conway的生命游戏扩展到了三维空间上，构建了三维生命游戏，并对其规则作了具有普遍性的扩展。C·Bays的学生Lee Meeker在此基础上进一步构建了四维的生命游戏。另外，Gardner等人也曾在这方面作了很多迸一步的研究工作。
4．2 沃尔夫拉姆对元胞自动机的分类
沃尔夫拉姆在1984年对最简单的元胞自动机―初等元胞自动机进行了深入探讨，并在此基础上发现了元胞自动机的动力学分类规律。11
初等元胞自动机是元胞状态集S只有两个元素{s1，s2}（即状态个数k=2），邻居半径r=l的一维元胞自动机。它是最简单的元胞自动机模型。
在S中元素的含义并不重要，它可取 {0，1}，{-l，1}，{静止，运动}，{黑，白}，{生，死}等等，重要的是S所含的符号个数，通常我们将其记为 {0，1}。此时，邻域集所含的元胞个数为3，局部映射f：S×S×S→S可记为:
自变量的值域是S×S×S，其中变量有三个，每个变量取两个状态值，那么就有2×2×2=8种组合，只要给出在这8个自变量组合上的映射值，f就完全确定了。例如下面的映射表便是其中的一个规则:
t | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
t+1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
这个规则也可表示为以下图形方式 (黑色方块代表l，白色方块代表0):
这样，对于任何一个一维的0，1序列，应用以上规则，可以产生下一时刻的相应的序列。下面的序列就是应用该规则产生的：（注意，因为该例子中还没有定义边界类型，所以边界上的元胞没有映射值）
t: 010111110101011100010
t+1:1010001010101010001
因为规则长度是8，而且以上8种组合分别对应0或1，因而这样的组合共有28=256种，即初等元胞自动机只可能有256种不同规则。
由上述8个自变量产生的8个结果组成一个二进制（注意高低位顺序），如上面的映射表为01001100，计算它的十进制值R，得到R＝76。
沃尔夫拉姆定义R为初等元胞自动机的标号，则上面的元胞自动机模型就是76号初等元胞自动机。显然，初等元胞自动机的规则的编码方案有256种，即R在[0，255]内。
沃尔夫拉姆详细探讨了这256种初等元胞自动机的演化行为，并将其按生成图案的外观分为四类。
为了再现沃尔夫拉姆对于这256种初等元胞自动机的研究以及详细的说明这个分类，笔者编了一个较为通用的程序，它能考察所有的一维元胞自动机的运行行为，而不仅仅局限于初等元胞自动机。首先对状态数目进行扩展，即允许状态集合超过2个。然后，让半径可以大于1。最后再考虑规则的编码方式。显然，当状态数增多且半径增大的时候，前面的编码方式就不实用了，因为规则数量成几何级数增长。我们可以按前面提到过的总和规则编码，即考虑类似于下面这样的规则：
如果输入的三个方格中黑色方格只有1个，那么下一时刻当前方格就是黑色；如果有两个黑色方格，则下时刻是白色，如果有三个方格，则下时刻是黑色，如果有4个方格，那么下一时刻是白色。
这种情况下，输入就仅仅有4种情况，因此可以得到下面的表：
输入 | 0 | 1 | 2 | 3 |
输出 | 0 | 1 | 0 | 1 |
同样的道理，我们可以对它进行编码为：0101，表示为十进制就是5。显然，这种编码方式导致规则长度只有4，编码值共16种。如果邻居扩大到2，则规则长度为6，编码值共64种。
我们拟用一个动画区域来演示元胞自动机的演化。假设元胞空间是一条线段，并且线段的长度为我们动画区域的宽度，比如说是400，也就是说有400个网格在这条线段上。每个网格上分布着一个元胞，元胞的状态为0、1、2等等整数值。我们根据元胞的状态用某一种颜色来涂满其所在的网格，例如如果元胞状态为0时涂白色，为1时 涂黑色。那么一条断续的横线就是当前所有元胞状态的一种分布，也就是一个构型。构型随着时间变化，就形成了不同的横线。我们把这些随着时间变化的线纵向拼 在一起形成了一个二维网格区域。这样，纵轴表示时间的流逝（往下为正），横轴为元胞自动机在对应时刻的构型，这样就能得到一幅图像，通过这副图像我们可以 清晰的观测到元胞自动机的每一步的演化规律。
笔者用java语言编制了一个Applet示例程序来对此进行演示。12在该程序中，用户可以通过设置不同的半径，不同的状态数，不同的编码规则类型，不同的编码值来观察形形色色的元胞自动机的动态行为。每一次运行，初始构型都是随机生成的。
对初等元胞自动机（状态数是2，半径是1且编码规则是普通规则）的运行结果进行观测，发现它们可以分成4类。
观察224号元胞自动机，设置好初始参数后，点击“启动”按钮，程序随机生成一个初始构型，然后一步步往下面演化。从上而下出现了一些黑色区域，然后就逐渐变成了全白色。也就是说经过几个时间步的运行后，元胞全部变为了固定状态0（也就是白色的方格），并再也不变化了。如下图：
如果我们重新启动一次，也就是让初始构型再随机生成一遍，跟前一次变得不同，我们看到演化的结果如下：
显然，演化出来的图案不一样了。但是我们发现，其特征一样，也就是经过几步演化之后，元胞状态全变成0，屏幕全变成白色。
实际上，不管我们重复多少次，在初始构型随机生成的情况下，只要编码值等于224，演化得到的结果都是屏幕最终全变白色。
再看254号的运行情况，如下：
发现其运行几步之后就全部变成了黑色。同样，不管我们重复多少次，在初始构型随机生成的情况下，只要编码值等于254，演化得到的结果都是屏幕最终全变黑色。
沃尔夫拉姆把这种具有“很快忘记掉初始状态而被吸引到一个固定状态”特征的元胞自动机归为第1类，它是元胞自动机的第一个演化等级。从外观上看，它是最简单的一类。
再看132号和203号元胞自动机的运行情况，都是变成了几个竖线。因为每一行就是某一时刻元胞自动机的一个构型，因此在竖向上能够形成一条竖线就说明这些元胞的状态在时间轴上没有变化。
再看208号元胞自动机，它是若干条斜的线。由于我们的边界是循环的，因此可以预言，经过若干个时间周期的运行以后，元胞自动机又回复到了原来的状态，因而这样的元胞自动机是循环的。两个相同状态之间经历的时间步长为这种元胞自动机的周期。
仔细观察这两类图案的特征，前者具有固定轨道，后者具有周期性轨道，从某个初始状态出发后它们很快的汇聚到这些轨道上。它们具有一定的结构，如“白色条状”和“黑色条状”，但是这些结构局限在局部。
沃尔夫拉姆把这种具有“虽然存在很多不同的最终状态，但是它们都组成一些特定的简单结构，这些结构要么永远不变，要么周期性重复”特征的元胞自动机归为第2类，它是元胞自动机的第二个演化等级。从外观上看，它比第1类更为复杂。
再看150号元胞自动机，如下：
它显然是处于一种混乱的、无序的状态，从很多角度看都是随机的，虽然三角形和其它小规模的结构一直会在某个标准上出现。我们称这种状态为混沌状态。
另外，与之类似的还有规则18，其运行情况如下：
沃尔夫拉姆将这种具有“表现在外观上的随机”特征的元胞自动机归为第3类，它是元胞自动机演化的第三个等级。它的复杂性显然高于前两类。
再看110号元胞自动机，如下：
我 们看到，它既不等同于完全的随机，又没有固定的循环的迹象。某些局部结构保持了固定不变，但是某些局部结构在屏幕上线性移动。这些结构之间以复杂的方式进 行交互。这种复杂结构既没有被吸引到固定的点或周期状态而变得死板，又没有因为随机而过于活跃。它既保证了一定的流动活性，同时又能产生具有“记忆性”的 结构。
沃尔夫拉姆将这一类型归为第4类。就外观上看来，它比前三类都复杂。但是，从“活跃度”上说，该类型介于类型2和类型3之间。我们知道，第1类和第2类系统会很快的停留在某个状态，它们不在有更多的活力。第3类系统每一步都在变化，它们永远保持了一个很高水平的活跃度。第4类系统则处于二者之间：它所显示的活力既不完全死掉，也不保持在很高的水平。沃尔夫拉姆指出，第4类元胞自动机的显著特征是：有一些特定的结构会永远得到保持，同时肯定会有一些移动的结构。
通过反复的运行初等元胞自动机的程序我们不难发现，所有的这256种元胞自动机都能被归为这四类。
如果我们做更深一步的思考，这所谓的混沌型和复杂型，虽然表面上看起来没有周期。但是，何以料定经过成千上万个时间步之后，不会变得有周期呢？其实，有这样一个事实：如果元胞空间是有限的，元胞状态数为2，那么元胞自动机演化必然呈现周期型变化。证明如下：
我们假设初始行的元胞的数量是有限的，比如说5个。那么这个行能演化达到的状态数最多只有2的5次方也就是32个。即使它的前32步演化得到的32个构型各不相同，但是它在演化的第33步，必然回到了一个在前32步里以前曾经到达过的状态，比如说第6步。一旦回到这个状态，那么它的下一步演化的结果必然也和第7步一样。以此类推，它就变成周期型了。因此得出结论，任何一个元胞空间有限的元胞自动机都会穷尽其所有可能而回到循环状态。实际上，这个结论也适用于任何有限的离散动力系统。
但是，我们在程序中进行模拟，画布的宽度不可能取无限大，也就是元胞空间总是有限的，所以我们可以说实际上，在模拟结果中，不存在真正的混沌型和复杂型。
然而为什么又要把混沌型和复杂型单独归纳出来呢？因为在实际中，有限元胞自动机的可能性空间随着元胞空间的扩大呈指数增长。比如100个网格的元胞自动机要穷尽一遍可能性需要2^100步骤，大概是1后面跟30个0，对于这种大数目的可能状态，虽然它肯定是有限的，然而我们已经可以认为穷尽可能性不可能了。在用程序进行模拟的时候，只要初始个数达到一定大小，我们就认为已经足够模拟真实世界了。从而我们说，混沌型和复杂型，是相对于那种少量几步就开始循环的周期型来说的。
还有一点要说明的是，我们的程序设置了初始构型是随机生成的。在某些特殊的初始构型下，有可能110号规则也得不到第4类的行为。沃尔夫拉姆用实验验证了这一点。13总之，初始构型也对元胞自动机的行为有一定影响。实际上，对于第4类元胞自动机来说，通过适当的构造初始构型，它可以模仿其它几类行为。14
上面是我们在初等元胞自动机上发现的元胞自动机的四种运行级别，那么其它的元胞自动机是什么情形呢？让我们把探索的邻域扩大到稍微复杂一点的情况。我们考虑状态数为2，邻居半径为2（也就是说每个细胞都有4个邻居，左右两边各两个），仍然是一维的情况。在这样的元胞自动机我们同样发现了原来存在的四种级别。比如20号（按照总和规则）和52号（按照总和规则）的情况15：
这两个元胞自动机的动态运行图竟然如此怪异，就好像一棵倒挂的葡萄藤。图中，某些结构得以一直保持，某些结构在线性移动，在可以预见的将来，它们将会发生碰撞，这种碰撞将导致系统的复杂行为。它们显然都是属于第4级别的。
进一步，状态数为3，半径为1，按照总和规则，编码值为1086和1038的元胞自动机的运行情况如下16：
综合上面的讨论，沃尔夫拉姆把一维元胞自动机归为四种类别。而进一步的研究表明，二维元胞自动机也无非就是这四种情况之一。前面介绍过的 “生命游戏”即属于第四种。后来经过更进一步的研究表明，其它形形色色的元胞自动机都可划分为此四种基本类型。
2001年， 沃尔夫拉姆在其新著《一种新科学》中进一步说明，十几年前他完全是以运行时的外观图案为基础进行的分类，当他进一步研究这些分属各个类别的元胞自动机的其 它属性时，他发现这些属性都与其分类密切相关。只要知道其所属类别，就可以预知其很多属性。沃尔夫拉姆作了一个类比，他说：“从某种意义上，对元胞自动机 进行分类，类似于把物质分为固体、液体和气体，把生物分为动物和植物。最初，分类仅仅建立在表面，但是后来，当更多的属性被发现后，这些属性被发现与分类 密切相关。”因此，沃尔夫拉姆认为，可以用这些细节性的属性去重新对原有的分类定义进行精确化。
例如，沃尔夫拉姆专门探讨了这四类元胞自动机对初始状态的敏感性。即在初始构型中改变一个元胞，看其运行结果跟前一次有何不同。他得到如下结论：
第1类：改变很快就消失了。实际上，不管初始状态怎么样，都会达到一个相同的最终状态。
第2类：改变会持续，但是它保留在局部区域。
第3类：任何改变都会以恒定的速率传播开来，最终影响到系统的每一个部分。
第4类：改变也传播，但是，仅仅是不定期发生。即，改变初始构型中某个元胞时可能传播，但是改变另一个有可能不传播。
沃尔夫拉姆指出，某种意义上说，它们揭示了四类系统在处理信息的方式上的不同。
第1类：初始状态的信息很快的被遗忘。不管初始状态如何，系统很快的演化为一个单一的最终状态，这个状态没有任何痕迹。
第2类：初始状态的一些信息保留到最终构型中，但是这些信息完全保持在局部，决不会从系统的一个部分传递到另一部分。
第3类：它支持“长范围通信”（long-range communication）―任何地方的任何改变都会最终传递到系统的即使最远的地方。
第4类：是2和3的某种调和。长范围通信在原则上上是可能的，但并不是一直发生――因为任何特殊的改变，仅仅只有当它影响到一个在系统中移动的局部结构的时候才被传递给系统的其它部分。
沃尔夫拉姆指出，虽然在这四类元胞自动机之间有很多特性不同，但是，它们处理信息方式的不同却显得尤其基本。实际上，理解自然界系统的很多特性都是从它们处理信息的角度去看，而这与元胞自动机的四个类别具有很大类似性。
此外，沃尔夫拉姆还指出，正如在其它领域中运用所有的分类方法都不可避免的存在一些边界情况，对元胞自动机的分类也同样如此。存在着某些元胞自动机，即可以划为某一类，也可以划为另一类，但是其数量极为稀少。17
我们知道，元胞自动机可视为离散动力系统，如果与连续动力系统的进行类比，我们可以说：第1类元胞自动机具有点态吸引子，第2类元胞自动机具有周期吸引子，第3类元胞自动机具有混沌吸引子，而第4类元胞自动机在连续动力系统中没有相对应的模式，它是元胞自动机的一种独特的行为表现。
4．3 朗顿的工作与“混沌边缘”
沃尔夫拉姆虽然在1986年发现了元胞自动机行为的动力学分类，但在当时他不知道这四个运行等级之间是怎样相互关联的，是什么决定了某个特定规则属于某个类别。在他看来，发现一个特定的规则属于哪个等级的唯一办法就是对其进行测试，看看它会产生什么行为。这促使很多学者开始试图回答这一问题。
在 许多真正的非线性系统中，运动的方程式中包含了许多参数，这些参数起着调节钮的作用，决定这个系统的混沌究竟达到何种程度。比如，如果这个系统是个滴水的 龙头，其参数就是水流的流速。或者，如果这个系统是兔群，其参数就会是兔子的出生率和因繁殖过多而造成的死亡率之间的比值。一般来说，小参数值通常导致稳 定的行为：均速水滴、不变的兔群规模，等等。这与沃尔夫拉姆的第一和第二等级的停滞行为非常相似。但当参数越变越大时，这个系统的行为就会变得越来越复杂 ——不同大小的水滴、波动的兔群规模，等等——一直到最后变得完全混乱。到这个时候，这个系统的行为就是沃尔夫拉姆的第三等级。这些非线性连续系统中却没 有第四等级。尽管如此，这些非线性系统与沃尔夫拉姆的等级之间的却如此类似，这就促使很多学者开始沿着这一思路，试图寻找到这一参数。最终，当时还在密歇 根大学攻读博士学位的美国学者朗顿（Christopher Langton）如愿以偿，并以此成果作为其博士论文。
对于一维元胞自动机，他找到的参数如下:
现假设每个元胞具有k种状态(状态集为Σ)，每个元胞的邻域集合的元素个数为n，则共存在kn种邻域状态。选择k种状态中任意一种s∈Σ并称之为静态sq。假设对转换函数而言，共有nq种变换将邻域映射为该静态，剩下的kn-nq种状态被随机地、均匀地映射为Σ-{sq} 中的每一个状态，则可定义:
这样，对任意一个转换函数，定义了一个对应的参数值λ。随着参数λ由0到1地变化，元胞自动机的行为可从点吸引子变化到周期吸引子，并通过第4类复杂模式达到混沌吸引子。
为理解λ的含义，举个例子。假如我们选用4个状态{0,1,2,3}，邻居半径为2（一共4个邻居）的一维元胞自动机来讨论， 我们知道，在给定了状态集和邻居的情况下，元胞自动机的规则集决定了它们的不同。每一个元胞自动机的规则集都可以看成是一张大的转换表，形如：
输入 | 01203 | 03120 | 12231 | …… |
输出 | 0 | 1 | 2 | …… |
其中每个输入的5位数字串中，中间的一个表示当前细胞的t时刻的状态，两边的数字都是它的邻居状态，而输出则对应当前细胞在t+1时刻的状态。表中一共有45=1024项，这其中有些输出项为0状态，有些不为0，我们把所有输出项为0的个数记为nq。那么我们可以定义参数：
λ=(45-nq)/ 45
这个参数反映了一组规则中转换成非0状态的比例。显然，根据给定的λ，我们可以得到很多的规则表，因此我们可以随机的在这些规则表中选择一个。比如令λ=0.5，那么我们可以随机的生成一个规则组转换表，表的输出部分0状态占据了一半的比例，其他的位置由1,2,3这几个数随机的填充。
笔者用Java语言编写了一个Applet程序，用以验证这个结论。程序演示如下面三个图，分别对应的λ为0.148,0.296,0.441,0.709的时候，它们分别属于第1，2，3，3类行为。
朗顿和他的同事诺曼·帕卡德（Norman Packard）给运行于第四级别的系统状态取了个名字：“混沌边缘” (the Edge of Chaos)，并立即开始考虑将其与所谓的“二级相变”18现象相类比。
他把参数λ想成是温度，起初，他认为第一和第二等级规则λ的低值就像是冰一样的固体，其水分子牢牢地固化成了晶体格。λ值稍高一些的第三等级规则就相应是水蒸气一样的气体，其水分子四处挥发，相互碰撞，完全处于混沌状态。而在这之间的第四等级规则则是液体。
刚 开始他发现，液态分子通常会相互翻滚成一团，每一秒钟都要几十亿次地相互结合、聚集、然后再次打散，与“生命游戏”非常相似。但当他对此做进一步思考时， 他开始意识到这不十分正确。第四等级规则通常能够产生“延长瞬变值”，比如“生命游戏”中的滑翔机，一种能够在任意长的时间里存活和繁衍的结构。在通常情 况下，液体不会表现出这种分子层次上的行为现象。众所周知，液体能够像气体一样，完全处于混乱状态。而且，将温度和气压增大到一定的程度，水蒸气可以不需 要经过相变直接变成水。总的来说，气体和液体只不过是单个物质流动状态的两种表现，都是处于混沌状态，二者的区别并不是根本性的。液体与“生命游戏”的相 似性仅仅是表面现象。
朗 顿进一步发现，固体和液态转换的过程中，在达到转变温度之上时，大多数水分子相互翻滚，处于完全混乱的状态：流体阶段。然而，在相互翻滚的水分子中有成千 上万极其微小的、有秩序的的岛屿，其水分子经常在边缘线上解体和重新结晶。这些岛屿即使就其分子规模而言，也是既不非常大，也不非常持久的。所以这个系统 仍然接近混沌。但随着温度下降，最大的岛屿开始变得非常之大，存在的时间也相对延长。混沌和秩序之间的平衡开始起变化。当然，如果温度一下子上升到超过转 变点，其作用就会被扭转：物体的状态就会从布满岛屿的流体之海变为布满流体之湖的固体大陆。但如果温度恰好处在转变点上，其平衡就会尽善尽美：有秩序的结 构之量与混沌的流体之量正好相等，秩序和混沌相互交织，呈现出复杂而永恒变化的状态。最大的秩序结构会在空间上传播任意长的距离，并且持续任意长的时间。 没有任何东西能够真正安顿下来。能够繁衍的、滑翔机式的“延长的瞬变值”、永不静止的动力、能够生长、分裂和重组的结构之舞呈现出来的令人永恒惊奇的复 杂。这与沃尔夫拉姆的第四等级正好相似。
朗顿通过λ参数来预测相变的一些特征数据，发现与前人对于二级相变的所有统计数据完全吻合。
朗 顿又进一步发现相变与计算机之间、计算机和生命本身之间，有着非常深刻的联系。朗顿认为，如果用第一等级和第二等级规则控制的分子自动机来建造一台这样的 通用计算机，因为它们产生的结构过于呆滞，我们可以将数据储存其中，但却不能在其中繁衍信息。同样，我们也无法建造一台第三等级的计算机。因为在这之上信 号会很快丢失，所储存的结构也会很快变成碎片。能够使我们能建造一台通用计算机的唯一规则存在于像“生命游戏”这样的第四等级之中。这些是唯一既能够提供 足够的稳定性来储存信息，又能够有足够的流动性可以在任意的距离之间传送信号的规则，这些结构之间的相互作用可以改变存储的传递信息，以支持总体的计算过 程。比如我们可以用这些结构的组合传递和存储信息，用它们的组合构造计算机所必须的与、或、非门等等。
朗顿将元胞拟人化理解，并发现了“临界变慢”的规律。一般说来，元胞们每一步都将“计算”其下一步应该所处的状态，计算所需时间依赖于它们的初始状态。当λ从0逐步增加到临界值λc时候，计算的算法复杂度是多项式级的。而当λ接近λc的时候，算法复杂度越来越呈指数级增长，因此“计算”时间会很长。而当λ从λc逐步增加到1的时候，计算的算法复杂度又逐步变成多项式级。因此，在接近临界值λc的时候，瞬时值（也叫瞬态模式）滞留的时间会很长，整体行为具有最大的初始敏感性，而在两个极端0和1的时候，瞬态模式滞留时间会很短，整体行为具有最小的初始敏感性。故而在λ<<λc或λ>>λc时，不需要多长时间我们就可以确定该元胞自动机的最终动力学结果，但对λ约等于λc的时候，它们的最终结果时不可判定的。
我们在前面介绍沃尔夫拉姆对元胞自动机的动力学分类的时候，也提到了出于第四等级的元胞自动机，其演化行为与初始构型密切相关，而且给定不同的初始构型，它可以模拟其它三类行为。这与“临界变慢”规律是相吻合的。
如 果以此来考虑停机问题，第一和第二等级的计算机，会在有限的步骤内很快停机。第三等级的计算机，会陷入死循环而永不停机。第四等级的计算机，则具有初始敏 感性，也就具有不可判定的特性，即：它会在某个输入的条件下很快停机，也会在某个输入的条件下永不停机。我们无法对其行为作出预测。更重要的是，它具有 “可以任意编程”的特性，我们可以通过控制其初始构型，在不改变其自身规则的情况下，实现任何计算功能。这也正是通用图灵机的特性。
朗 顿进一步认为，在混沌边缘，很可能碰到生命本身。因为他无法抗拒这样的现象：具有生命特征的“信息动态过程”可以自发的在接近临界相变的物理过程中涌现出 来。生命确实是永远力图在混沌边缘保持平衡，一方面始终处于陷入过分的秩序的危险之中，另一方面又始终被过分的混乱所威胁。他推测，生命可能起源于水分子 的“信息动态过程”，然后扩展到漂浮于海洋内的生命分子中。进化只不过是生命越来越善于控制自己的参数，以使自己越来越能够在边缘上保持平衡的过程。也许 生命起源于四十亿年前的某种相变，如果有一天我们能写出相变的一般性物理规律，我们就可以揭开生命起源的奥秘。
朗 顿指出，生命细胞中由很多证据支持相变和生命之间的密切联系。生命细胞中发现的许多过程和结构就是在相变附近维持的。例如，细胞质膜就是被保持在溶胶和凝 胶转变的附近，细胞骨架的微管的末端保持在生长和融解之间。在智能的情况中，朗顿认为也有质的证据支持大脑动态过程的这种相变观点。
我们将朗顿的上述类别列表如下：
元胞自动机 | 第一、二等级→第四等级→第三等级 |
动力系统 | 秩序→“复杂”→混沌 |
物质形态 | 固体→“相变”→流体 |
计算机 | 停机→不可判定→永不停机 |
宇宙状态 | 过于稳定→“生命／智能”出现→过于喧闹 |
综 合上述，我们发现很多系统都存在一个“混沌边缘”的状态，当处于该状态时，系统会表现出复杂现象：在这个层次的行为中，该系统的元素从未完全锁定在一处， 但也从未解体到骚乱的地步。这样的系统既稳定到足以储存信息，又能快速传递信息。这样的系统是具有自发性和适应性的有生命的系统，它能够组织复杂的计算， 从而对世界做出反应。
“混沌边缘”已经成为当前复杂性科学研究的一个重要成果和标志性口号，它也是圣塔菲学派的旗帜。
当然，严格地说，朗顿的某些观点只是一种类比和推测。但另一方面，种种迹象表明，朗顿的发现具有普遍性的意义。比如事后人们发现，在关联论的模型中，有半数会出现类似相变的行为。在比如上世纪60年代，考夫曼（Kauffman）在他的基因网络中最先发现的事情之一就是相变。
对 于“混沌边缘”的概念是否也适用于共同进化系统，人们的认识更为模糊。在生态或社会经济系统中，我们对如何准确定义诸如秩序、混沌和复杂这些概念很不清 楚，就更别提要定义它们之间的相变了。但尽管如此，“混沌边缘”这个法则也总让人感到具有某种真意。举前苏联为例，很明显，用中央集权的办法来控制社会不 会有好效果。因为斯大林建立的社会体制过于僵硬呆滞、对社会的控制过于严密了，所以无法维持下去。也可以举上世纪70年 代底特律的三大汽车公司为例，这几家汽车公司发展规模过大、过于刻板地锁定在某种特定的运行方式中了，所以很难认识到来自日本的挑战在不断增强，要对这一 挑战做出回应就更是力不能胜了。而另一方面，无政府主义也不是行之有效的社会机制，放任自流的社会体制是行不通的。前苏联的某些地区在苏联瓦解之后的状 况、狄更斯恐怖小说中英国的工业革命，或更现代的美国储贷的崩溃，都说明了这一点。最近的政治经验给我们启示：一切健康的经济和健康的社会都必须保持秩序 与混乱之间的平衡，而不是保持某种软弱无力的、平庸的、中间道路似的平衡。“混沌边缘”上的复杂动力，是社会进化行为的理想解释。
4．4 人工生命科学的诞生与发展
前面提到，朗顿发现了处于“混沌边缘”的元胞自动机不仅可以完成复杂的计算，而且可以支持生命和智能。正是在这样的思想的指导下，朗顿提出了他的“人工生命”（Artificial Life）理念。1987年9月在圣塔菲研究所的支持下，朗顿主持召开了第一届国际人工生命研讨会，这次会议宣布了一门新的计算机与生物学交叉的前沿学科的诞生。自1987年至今，包括数字生命在内的人工生命研究得到了越来越多的计算机专家和生物学家关注，出现了“生物形态”19 、Tierra世界、“Avida”、“阿米巴世界”等数字生命模型，其中一些模型曾是著名科学杂志《自然》和《科学》报道的热点。人工生命已经成为是复杂性科学研究的支柱学科之一。
“人 工生命”的学者们认为，生命的本质不在具体的物质，而在物质的组织形式。生命并不像物质、能量、时间和空间那样，是宇宙的基本范畴，而只是物质以特定的形 式组织起来派生的范畴。这种组织原则完全可以用算法或程序的形式表达出来。所以，只要能将物质按着正确的形式构筑起来，那么这个新的系统就可以表现出生 命，而这种所谓的“正确的形式”就是生命的算法或程序。所以，算法和程序是把非生命和生命连接起来的桥梁，是生命的灵魂。
人 工生命就是人造的生命，而不是由碳水化合物有机形成的自然生命。人工生命虽然没有考虑现实的以碳为基础的生命的运作问题，但它一开时就从计算的视角来思考 生命的本质问题。人工生命把生命的本质看作是一种形式，这种形式可以通过程序或算法表现出来。所以，在人工生命看来，生命的本质实际上就是一种算法，这种 算法的运行就表现出生命。人工生命的很多研究就是通过计算机编程的方法揭示生命的本质。
人工生命研究能够展示自然生命特征或行为的人工系统，试图在计算机、机器人等人工媒体上仿真、合成和生物有机体相关联的一些基本现象，如自我复制、遗传、寄生、竞争、进化、协作等，试图用非生物媒介创造新的生命形式，并研究和观察“可能的生命现象”(Life-as-it-could-be)，从而使人们能够加深理解“已知的生命现象”(Life-as-we-know-it)。它采用的是一种合成的方法而不是还原的方法。
当 前，人工生命的含义有所扩大，构建人工生命的途径也有所增加。第一类是通过软件的形式，即用编程的方法建造人工生命，也就是原始的狭义的人工生命。由于这 类人工生命主要在计算机内活动，其行为主要通过计算机屏幕表现出来，所以它们被称为虚拟人工生命或数字人工生命。大家熟悉的计算机病毒就是一种较为低等的 数字人工生命。但美国生物学家托马斯·雷1990年编写的“Tierra”（西 班牙语，意为地球）模型所创造的生命更具典型性。第二类是通过硬件的形式，即通过电线、硅片、金属板、塑料等各种硬件的方法在现实环境中建造类似动物或人 类的人工生命。它们被称为“现实的人工生命”或“机器人版本的人工生命”。第三类是通过“湿件”的方式，即在试管中通过生物化学或遗传工程的方法合成或创 造人工的生命。不过这种方法在目前并不能从头开始，即完全从无生命物质开始合成生命，而只能对现有的生命进行改造创造人工生命，比如克隆羊就是如此。
总之，元胞自动机理论的发展催生了人工生命理念的诞生，而人工生命的发展则有力的支持了“生命的本质是计算”这一计算主义观点。
4．5 元胞自动机理论的继续发展
元胞自动机理论自从提出之后，在应用领域得到了长足的发展，其范围涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、环境、军事学等。
在社会学中，元胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。
在生态学中，元胞自动机用于兔子－草，鲨鱼－小鱼等生态动态变化过程的模拟，展示出令人满意的动态效果。元胞自动机还成功地应用于蚂蚁、大雁、鱼类等动物的群体行为的模拟。另外，基于元胞自动机模型的生物群落的扩散模拟也是当前的一个应用热点。
在信息学中，元胞自动机用于研究信息的保存、传递、扩散的过程。另外，Deutsch、Sternberg和Rosenfeld等人还将二维元胞自动机应用到图像处理和模式识别中。
在计算机科学中，元胞自动机可以被看作是并行计算机而用于并行计算的研究。另外，元胞自动机还应用于计算机图形学的研究中。目前，元胞自动机也成为量子计算机研究的一个热点。
在数学中，元胞自动机可用来研究数论问题。例如费歇尔（Fischer）设计的素数过滤器(Prime Number Sieves)。
在物理学中，除了格子气元胞自动机在流体力学上的成功应用外，元胞自动机还应用于磁场、电场等场的模拟，以及热扩散、热传导和机械波的模拟。20
在化学中，元胞自动机可用来通过模拟原子、分子等各种微观粒子在化学反应中的相互作用，而研究化学反应的过程。例如国内的中山大学副教授李才伟等在1997年应用元胞自动机模型成功模拟了由耗散结构创始人普里高津（Prgogine）所领导的布鲁塞尔（Brussel）学派提出的自催化模型－Brusselator模型，又称为三分子模型。21Y·BarYam等人利用元胞自动机模型构造了高分子的聚合过程模拟模型。
在地理信息系统中，元胞自动机也得到了深入的应用。22
在环境科学上，有人应用元胞自动机来模拟海上石油泄露后的油污扩散、工厂周围废水、废气的扩散等过程的模拟。
在军事科学中，国内的谭跃进教授指出，元胞自动机模型可用来进行战场的军事作战模拟。
因为元胞自动机的设计思想本身就来源于生物学自我繁殖的思想，因而它在生物学上的应用更为自然而广泛。例如元胞自动机用于肿瘤元胞的增长机理和过程模拟、人类大脑的机理探索、HIV的感染过程、自组织、自繁殖等生命现象的研究以及最新流行的克隆技术的研究等。
元胞自动机在复杂性科学的研究中更是显示出其特有的优势。赫尔曼（G. T. Herman）及其合作者在1973年提出了一个用来模拟贝壳图案的元胞自动机。斯威夫特（Jack Swift）和卡达诺夫（Leo P. Kadanoff）发表在1968年《物理评论》（Phys. Rev. 165－310）和弗里希（Frisch）等人发表在1986年《物理评论通信》（Phys. Rev. Lett. 56－1595）上的论文都不约而同介绍了一种模拟水流的元胞自动机。
曾因写作《自私的基因》（The Selfish Gene）而名扬天下的牛津大学的进化论学者道金斯（Richard Dawkins），主张用元胞自动机模仿生物的进化。他构造出模仿昆虫进化的元胞自动机，在电脑屏幕上观察昆虫的变异、繁殖和互相吞噬，居然在计算机上描绘出与真实生物界惊人相似的生命演化和灭绝的过程。他的程序名叫“生物形态”（Biomorphs）。 生物形态从一个默认的简单线条画开始，随后产生若干变异了的线条。程序使这些变异出现在计算机屏幕上。观测者也可以扮演大自然的角色：根据自己的喜好，在 屏幕上选择最喜欢的图画。程序接着复制这种图画，并使它发生新的变异。观测者接着选择最喜欢的图画使它发生新的复制和变异。多次重复上述突变和选择过程， 道金斯最后得到了许多个不相同的生物形态图案，这些生物形态与自然界的许多生物形态有着惊人的相似性。
当时，已经在圣塔菲研究所工作的朗顿利用更简单的二维元胞自动机模型发现的一个能自我复制的“圈”，或称“能自我复制的元胞自动机”，该工作建立在冯·诺依曼和泰德·考德（Ted Codd）工作的基础上。23
4．6 弗雷德金猜想
弗雷德金在他的“新物理学理论”里面提到过，宇宙的本质是计算。上世纪70年代末，他又进一步猜测，或许我们存在的这个宇宙就是一种巨大的极其复杂的元胞自动机，所有物理量（physical quantities）即能量和物质都可以看作存在于该元胞自动机中的信息包。在弗雷德金的模型中，时间和空间都不是连续的，而是颗粒状的，空间是由极其微小的、离散的一个个单元构成的，这些单元的状态按极小的、离散的时间间隔变化，这种过程就像计算机上的元胞自动机产生出复杂样式。
我 们的宇宙的确与理论上的元胞自动机有很多相似的地方，像元胞自动机的三个特征－并行性、局部性、同质性，宇宙也都符合。元胞自动机元胞的演化是并行的，宇 宙也是并行处理的；元胞自动机的元胞演化受邻居元胞的影响，宇宙中的每一点受邻近状态的影响最大；元胞自动机的所有元胞遵守统一的演化规则，宇宙各处遵循 着同样的自然律。虽然与整个宇宙相比，元胞自动机的规则是过于简单，但是它里面所蕴含的道理可能与宇宙的机制是相通的。
1990年，弗雷德金在一篇文章里面提出，有可能发现一种单一的元胞自动机规则，在这种规则的作用下，这种元胞自动机不仅能够模拟所有微观的物理现象，而且能够精确地模拟它们。他把这种系统称为“数字力学”（Digital Mechanics）。如果真的能找到这样的规则，那么我们建立宇宙的统一理论也就不远了。
认识到宇宙是一台元胞自动机对我们人类自身有什么意义吗？它有助于我们回答一些最基本的问题吗？譬如弗雷德金曾经思考过的三个哲学问题：生命是什么？意识、思想和记忆是什么？宇宙怎么运转？
弗 雷德金对他的三个问题深思熟虑之后，竟得出这样的猜想：有一个更高级的智慧生物在观察我们人类的进化、繁殖、相互残杀，人类只是存在于高级生命设定的一种 元胞自动机中，人类所相信的实在只是宇宙幻觉，只是高级生命的电脑实验。我们人类的存在或许是被高级生命用于解决某个难题的。对弗雷德金的这种近乎科幻的 思想，有人开玩笑说，“好消息是我们的生命有了目的了；坏消息是这个目的是为了帮助某个遥远的黑客来算π值小数点后第亿万万万位是个什么数。” 电影《楚门事件》（Truman Show）和《十三度凶间》(The Thirteenth Floor)里的主角们最后都觉醒了，弗雷德金难道是我们人类当中最早觉醒的？
4．7 《一种新科学》的诞生
沃尔夫拉姆“闭关”15年后，将他潜心研究的成果于2001年自费出版成书《一种新科学》（A New Kind of Science）， 在科学界丢下了一枚重磅炸弹。因为作者声称他发现了一种新科学，他所做的一切不亚于牛顿的贡献。早在该书面世以前，沃尔夫拉姆在接受《福布斯》杂志记者采 访时就夸耀了他将在书中给出的几个主要发现，譬如，向自然选择学说作出挑战；时间为什么单向流逝；怎样制造人造生物；解释股市涨落；诸如从雷电到星系的复 杂系统如何蕴藏着智能；树叶、树木、贝壳、雪花和几乎所有其他东西的形状为什么是那个样子的，等等等等。而这些属于绝然不同的研究领域、看起来似乎风马牛 不相及的问题，如何在沃尔夫拉姆所谓的“新科学”下得到统一的解释呢？ 其实，这个新科学的基础理论就是元胞自动机。
《一 种新科学》以如下惊人之言开始它的鸿篇巨制：“三个世纪以前，人们发现建立在数学方程基础上的规律能够用于对自然界的描述，伴随着这种新观念，科学发生了 转变。在此书中我的目的是将要用简单的电脑程序来表达更为一般类型的规律，并在此种规律基础上建立一种新的科学，从而启动另一场科学变革。”
作 者沃尔夫拉姆在这里所指的三个世纪前那场发生在科学上的转变就是我们常说的“科学革命”，那场革命以哥白尼发表《天体运行论》为开端，经过伽利略和开普勒 等人的推进，到牛顿出版《自然哲学的数学原理》达到高潮。沃尔夫拉姆认为“传统科学”未能建立起解释宇宙复杂性的理论，靠数学方程做不到这一点。所以他要 发动一场新的“科学革命”，革命的内容就是要用简单的电脑程序―元胞自动机―取代数学方程。
全书共分12章，各章的内容大体如下：
第一章：The Need for a New Kind of Science。
这一章讲述作者写作这本书的动机，以及作者发现自己的新科学的简单历史。作者在12岁 的时候看到了一本物理书上的随机分子碰撞的图形就想到了要用计算机模拟这一切，于是开始了他的科学生涯。在之后的日子里，作者不断的产生新想法，又不断自 己试图找到了答案，于是写成了这本书。这一章还介绍了与该书内容相关的很多领域，包括复杂系统、人工智能、人工生命、系统科学等等。
第二章：The Crucial Experiment。
大致介绍书中的研究方法，即用元胞自动机做实验，然后找到该自动机的涌现规律。其中很多内容是关于一维元胞自动机的基本知识，包括如何对规则编码等等细节。本论文前面已经有所介绍。
第三章：The World of Simple Programs。
这章开始介绍各种各样的计算模型，不仅仅是元胞自动机，还有移动自动机、图灵机、L系统、tag系统、寄存器计算机、符号系统等等模型。也许计算的类型多种多样，但是所有的计算系统的行为都可以大致分为类似于元胞自动机的四个运行类别。这些模型提醒我们，虽然自然界的现象千奇百怪，但我们可能仅仅用一些简单模型就可以模拟。
第四章：Systems Based on Numbers。
这章用丰富的图形展示给大家元胞自动机是怎样模拟数字运算系统，包括加法、减法、乘法、除法运算，求平方根、求π值，判断一个数是否是素数、甚至还能计算微积分、求解微分方程等等。本章传达了这样一个信息：凡是基本数学能做的事情，简单的元胞自动机也都能做。
第五章：Two Dimensions and Beyond。
主要介绍二维的计算系统的行为以及更多的计算模型，包括动态网络和受限生成系统。其中网络模型则可以直接应用于后面的物理系统，它有望最终解释究竟什么是时空。受限生成系统则直接跟复杂适应系统有关，作者认为复杂系统的适应性行为直接源于简单计算的满足受限行为。
第六章：Starting from Randomness。
详细的讨论了元胞自动机四个运行级别的行为，也就是本论文已经介绍过的四个类别。其中作者对后两种类型进行了比较详细的介绍。本章的之所以选用这个标题是因为作者在研究元胞自动机四类行为的时候，初始构型是随机生成的。
第七章：Mechanisms in Programs and Nature。
介 绍了什么是通用计算的概念，并讨论了随机性和复杂性。作者把随机性归为了三类，也就是全是由外部操作生成的随机、初始化微小扰动造成的随机和系统内生的随 机。对最后一种也就是说初始状态可能完全确定，最后行为也可能是随机的。本章还讨论了离散与连续、混沌与秩序、简单行为与复杂行为等问题。
第八章：Implications for Everyday Systems。
在 本章中进一步把元胞自动机与周围的真实世界联系起来，弹子球、纸牌游戏、布朗运动、三体问题等等问题中的随机性都可以用元胞自动机来解释；流体的湍流、晶 体生长的规律、华尔街股票的涨落也都可用元胞自动机来模拟；还有自然界中的树叶、贝壳、生物色素沉着、多彩多样的花纹等，元胞自动机能生成与它们一模一样 的图案和形态。
例 如，对生物学，作者说“生物系统常被当成自然界中复杂系统的极好例证，人们设想它们的复杂性必定从根本上要比其他系统的要高，这是毫不稀奇的……而我相 信，生物系统中许多最为明显的复杂性例子事实上与适应环境或自然选择几乎没有关系。相反，它们主要只是我所发现的基本现象的一个结果。”他以某些软体动物 的壳为例，指出这些壳上的图案与一些元胞自动机生成的图案非常类似。而这种类似绝非巧合：壳的图案由一层层的色素分泌细胞（生物细胞）沉淀而成，这些色素 分泌细胞与相邻的细胞交换化学信号，其行为与元胞自动机非常相似。这种类似性虽然不是由他首次提出来，但是他进一步指出了某种元胞自动机规则类型中所有可 能的规则都可以在不同的软体动物的壳上找到。
沃尔弗拉姆说，这种方法之所以成功不是因为它有多高明，而是世界本身就是如此。他不用达尔文进化学说解释生物的复杂性，而认为基于简单规则的极少计算过程就可以导致这种结果。
第九章：Fundamental Physics。
作者很聪明地构建了一种可逆（Reversible）的元胞自动机，这种元胞自动机产生的无序性是可逆的。这种元胞自动机与热力学第二定律发生冲突，却与物理定律的可逆性相吻合。这是作者在物理学领域吹响的最嘹亮的“革命”号角。
作 者还探讨了空间网络、因果网络等模型。究竟宇宙是不是一台计算机，我们实际上不能证伪，但是如果从程序的角度出发，却发现我们可以从一个完全不同的角度得 到很多疑难问题的解答。作者进一步认为宇宙就是一台元胞自动机，在因果网络模型下，空间、时间、引力、相对论和量子力学等等都是系统涌现出来的一种结果， 是这台宇宙元胞自动机所呈现出来的各种表象。如果这一切正确的话，我们自然能得到一个统一量子论和相对论的工具。他还深信，宇宙元胞自动机的初始规则，用 他的“数学”软件来表达，也许只有几行命令。
对于空间，沃尔弗拉姆认为它也许不是某种连续体，而是某种由相互关联的碎片组成的网络。
本章提出来的时空观是非常关键的，即因果网络是最本质的东西，时间和空间甚至都是涌现出来的现象。
第十章：Processes of Perception and Analysis。
讲述把元胞自动机应用到计算机科学、人工智能、信息处理等领域的具体方法，视觉感知、加密解密、思维过程等等都有涉猎。
第十一章：The Notion of Computation。
通 过作者特别的证明（运用图形和说明，而不是数学推导），我们看到一类特制的元胞自动机可以模拟任何一台其他的元胞自动机，而且还能模拟图灵机以及其他的计 算系统。反过来，图灵机和其他计算模型也都能模拟元胞自动机。实际上能够执行通用计算的机器仅仅需要简单的规则，也就是110号元胞自动机。
本论文前面已经详细介绍了110号元胞自动机的一些特征。作者认为110号元胞自动机非常重要，因为它规则简单，而且能够模拟任意的复杂计算过程。这一点由沃尔夫拉姆在1985年左右作出猜测，由他的公司雇员库克（Matthew Cook）在上个世纪90年代中期给出证明。
第十二章：The Principle of Computational Equivalence。
本章提出了一个猜想：计算等价性原理（The Principle of Computational Equivalence），也就是，作者认为宇宙的一切活动都是一种计算，几乎所有达到一定复杂程度的系统都等价于规则110元胞自动机，也即等价于一台通用图灵机。作者讨论了哥德尔定理、不可判定问题，并且认为对于第4类元胞自动机，我们除了运行它以外，根本无法判定它在未来的行为，即使在原则上，因为它具有不可化归性。
这是一条让人褒贬不一的大胆设想。他认为，所有过程，无论是由人力产生的还是自然界中自发的，都可以视作一种计算过程。在他看来，从山顶滚下的岩石、在角落里静静地生锈的一桶铁钉也是一台普适计算机，其相关特征与人的智能是可有一比的。
全本书大量的使用元胞自动机生成的图形来说明、叙述。字里行间作者表达了一个强烈的观点：宇宙的一切过程都仅仅遵循非常简单的运算，而且这个运算很可能就是110号元胞自动机，所有一切的奥秘也许就起源于这一种简单的规则。全书最有价值的是第九章和后面两章。我们可以看到，之所以作者称其为新科学，是因为也许复杂系统中的所有问题都仅仅是一条规律制约着，这至少是作者的一个信念。
前 面说过，弗雷德金和费曼等人都猜想，宇宙是一种计算机。而沃尔夫拉姆则沿着这条路走得更远。在他的“新科学”里，他提出了具体的模型―因果网络模型，说明 基本粒子只是一种偶发现象，物体的运动、几何学之类仅仅是幻象。时间和空间由离散的最小单元构成，就如元胞自动机的元胞。宇宙间的一切变化只是元胞之间的 信号传递。
在接受《福布斯》记者采访时沃尔夫拉姆作出了他的大胆预言：“50年内，更多的技术，将基于我的科学而不是传统科学，被创造出来。人们在学习代数之前将先学元胞自动机理论”。沃尔夫拉姆的一位朋友甚至建议《一种新科学》应该仿照牛顿的《自然哲学的数学原理》（Principia Mathematica）改名为《自然哲学的计算原理》（Principia Computatus）。
沃尔夫拉姆的观点在国外引起强烈轰动，但国内迄今为止关注的极少。
第五章 元胞自动机理论的思想意义
我们姑且不论那些研究元胞自动机的学者们所作的惊人之语的是否正确，至少，他们所做的工作，可以让我们更好的认识如下几对概念。
第一，确定性与随机性。
确定性和随机性是客观事物的两个方面。科学家们早就发现，确定性和不确定性之间并没有不可逾越的鸿沟，二者是辨证统一的关系。元胞自动机的行为提供了一个绝好的佐证。
一 方面，我们看到，对于某些初等元胞自动机来说，其初始构型是随机生成的，但是只要规则确定了，其演化规律却是一定的。这说明了，随机性当中可以产生确定 性。反过来，我们也能够发现，大量确定性的相互作用可以涌现不确定性，表面上看起来是随机的现象，其本质却是遵循着确定性的规则。比如第3类元胞自动机，就是一个确定运作的系统，它有着确定的规则，然而其在系统中的演化却产生了完全不确定的、随机的行为。严格的说，它是一种确定性混沌。
第二，过程与状态。
在 近代科学中，早已破除了那种以状态为主看待事物的思维方法，而逐步树立了以过程为视角的思维方法。这种视角认为，我们应该首先考虑系统的演化行为，而不是 此时的状态。在许多情况下，终极状态是什么并不知道，甚至是否存在这样的终极状态也并不是明确的。哲学家黑格尔曾说过，了解一门科学的历史，也就了解了这 门科学本身。朗顿也曾经说过这样一句话：“你应该观察系统是如何运作的，而不是观察它是由什么组成的”。
元胞自动机有时间维，所以，它表现为一个过程。在某一个静止的时刻，元胞自动机的特性是显示不出来的，它只能在动态的过程中显示出其特性。在对其特性进行分析的时候，比如对其进行动力学分类的时候，对某些元胞自动机，这个观察过程还必须足够长，才能真正找到其规律。
第三，集中控制与自组织。
元 胞自动机是由大量的元胞组成，其行为是这些元胞个体演化行为的一种涌现，这些元胞的地位是平等的，它们按规则并行的演化，而不需要中央的控制。在这种没有 中央控制的情况下，它们能够有效的“自组织”，因而在整体上涌现出各种各样复杂离奇的行为。这就启发我们，集中控制并不是操纵系统实现某种目的的唯一手 段。
第四，简单与复杂。
元 胞自动机让我们很惊讶的发现，一些简单的东西却可以产生如此复杂的现象。元胞状态是如此简单，规则是如此简单，然而它竟然可以“模拟整个宇宙”，从生物进 化，到股市涨落，到雪花形成，到铁钉生锈，等等一切。这更加深了我们“表面上看起来复杂的事物其本质可能很简单”这一信念，从而激发我们为从复杂性中发现 简单性而锲而不舍。
第五，连续与离散。
微分方程有着三百多年的发展历史，它已经成为现代科学的语言，也是科学研究中最为重要的研究工具之一，一大批重要的科学规律就是利用微分方程来推理和表达的。
微分方程的主要特点是时间、空间均连续(如果方程中有空间因子的话），这是建立在时空连续的哲学认识基础上的。而元胞自动机则是完全的空间离散、时间离散，在这个意义上，微分方程和元胞自动机一对相对的计算方法。
在人工计算的情况下，由符号组成的(偏)微 分方程可以灵活地进行约简等符号运算，而得到精确的定量解，这是其优势。但在现代计算机日益发展，已成为我们科学研究的重要工具时，微分方程却遇到了一个 尴尬的问题，即计算机是建立在离散的基础上的，微分方程在计算时不得不对自身进行时空离散化，建立差分方程等；或者展开成幂系列方程，截取部分展开式；或 者采用某种转换用离散结构来表示连续变量。这个改造过程不仅是繁杂的，甚至是不可能解决的，但最重要的是在这个过程中，微分方程也失去了它的自身最重要的 特性―精确性、连续性。甚至，我们可能因变数太多而根本无法得到合适的方程式，要么方程式本身极其复杂难以求解。
而对于元胞自动机来讲，脱离计算机环境来进行运算几乎是不可能的，但是借助计算机进行计算，却非常自然而合理，甚至它还是下一代并行计算机的原型。因此，在现代计算机的计算环境下，以元胞自动机为代表的离散计算方式在求解方面，尤其是动态系统模拟方面有着更大的优势。
因 为元胞自动机的计算能力等价于图灵机，所以元胞自动机在理论上具备计算的完备性。但是，其满足特定目的的构模尚无完备的理论支持，其构造往往是一个直觉过 程。用元胞自动机得到一个定量的结果非常困难，即便是可能的话，元胞自动机也将陷入一个尴尬，元胞自动机的状态、规则等构成必然会复杂化，从而不可避免地 失去其简单、生动的特性。
然而，诚如物理学家玻尔所说，“相对的并不一定是矛盾的，有可能是相互补充和相互完善的”。二者互有优缺点，相互补充，都有其存在的理由。在现代计算机环境下，对于元胞自动机这一类相对来讲还处于幼年阶段的离散计算方式，需要予以更多的关注和支持。
总之，元胞自动机的出现，促使了人们对于离散与连续的重新认识。
美国洛斯阿拉莫斯国家实验所的物理学家拉里·希尔创造了一种元胞自动机，这一模型成功创造了一段动画，这也许是对超热流体进行计算机模拟的第一步。希尔指出，这种流体的动力学过程太复杂，基于传统方程式的仿真手段无法满足要求，而元胞自动机模型能很好的解决这一问题。这也许很好的说明了这一点。
第六，并行与串行。
前面说过，若从计算视角理解元胞自动机，则元胞自动机可能是下一代并行计算机的雏形。元胞自动机的出现，让人们更好的展望并行计算的前景。
第六章 元胞自动机与计算主义
6．1 元胞自动机理论对计算主义的支持
前面，我们谈到了图灵机，生命游戏，元胞自动机运行的第四等级，混沌边缘，生命等各不相同的概念，并揭示了它们之间的本质上存在某种等价性，而沃尔夫拉姆在《一种新科学》里面，将这些成果集大成。他认为，宇宙的一切都可以归结为“110号元胞自动机”，它等价于通用图灵机，它运行于“混沌边缘”，它孕育出生命，它也等价于宇宙中的所有具有一定复杂性的事物。而且难能可贵的是，他通过形形色色的例子来证明了这一点。从某种程度上说，沃尔夫拉姆就是一个不折不扣的计算主义者。
显然，元胞自动机理论的发展以及沃尔夫拉姆的结论强有力的支持了计算主义的观点。
第一，元胞自动机理论的某些研究者们在“宇宙是计算机”的观点的基础上进一步指出“宇宙是元胞自动机”。反对计算主义的人们认为，计算机和元胞自动机太简单，不能把任何事物都加以模拟，除非把宇宙的面容做一些简化。然而，计算主义者说，图灵早在20世纪30年代就已证明，图灵机原则上可以计算任何可计算的东西。为了说明他的结论，图灵让他的装置具有无限大的容量。根据同样的道理，对元胞自动机来说，如果我们设想它有无限大的尺寸，那它就能模拟任何物理客体。
第二，元胞自动机理论的研究者们用“元胞自动机”成功的模拟了自然界的多种事物，为世界是一台元胞自动机提供了部分证据。许许多多的例子在前面都有所提及。
第三，元胞自动机理论的研究者们用“元胞自动机”成功的模拟了生命，并由此催生了“人工生命”科学的诞生，为揭示生命的计算本质作出了巨大贡献。这一点在前面已经有详尽的介绍。
第 四，沃尔夫拉姆提出了可逆元胞自动机的模型，给了反对计算主义的人们迎头痛击。反对计算主义的人们常常反驳说：“计算机不可能描述世界，因为物理定律的可 逆性与计算机的运算的不可逆性是矛盾的”。我们知道，经典力学和量子力学的规律相对于时间都是可逆的。也就是说，如果在描述这些规律的公式中把时间反转， 即把t变为-t， 公式的结果并不会改变。或者说，如果我们能把时间反转，我们的行星照样会在原来的轨道上绕太阳旋转，原子的性质也不会有什么改变。但计算机的运算却不是这 样，计算机的运算是不可逆的，因为组成计算机的中央处理器的逻辑门具有不可逆性。无论什么时候，逻辑门接通或关掉，有些能量便无可挽回地以热的形式损失掉 了。因此，必然提出这样的问题：如果物理定律是可逆的，而计算机的运算是不可逆的，那么宇宙怎么可能是一部计算机呢？IBM的工作者兰多尔（R. Landauer）和本奈特（C. Bennett） 曾经证明，在信息形式的改变过程中的计算并不需要任何能量，但信息的消除却需要能量。也就是说，完成计算所需的最小能量和丢弃的信息量直接有关。因此，如 果我们在进行计算时，保留所有的中间结果，那么我们就可以进行逆运算。如果我们毁掉中间结果，则计算就失去其可逆性，其能量也将随之消耗。弗雷德金从这里 受到启发，他设想了一种没有信息量损失的方案。一般的逻辑门，比如“与”门，通常有一个输入和两个输出。这样的门是不可逆转的。但弗雷德金设想，如果人们 作出安排，使它既能传递“与”门的输出值，也能传递它的输入值，即现在使它具有三种输出值，那么，“与”门就变成可逆的了。因为信息在这里不会有损失。理 论上这种计算机能计算常规计算机所能计算的任何事情。弗雷德金找到了使计算可逆的方法，更进一步，沃尔夫拉姆在《一种新科学》中找到了这一元胞自动机模型24。这给予计算主义者们极大鼓舞。
6．2 评价
元 胞自动机理论的研究领域是滋生计算主义观点的温床。弗雷德金和沃尔夫拉姆等人正是在对元胞自动机理论的研究中形成了自己的计算主义观点。许许多多计算主义 的观点也在元胞自动机理论的发展中被进一步加强。但是由元胞自动机滋生的计算主义的某些观点并不令人信服。至少，在笔者看来，这些观点存在着以下不足：
第一，思维过于跳跃，缺乏逻辑上的证据。
沃 尔夫拉姆和他前面那些热衷于用元胞自动机来得到类似于自然界各种事物的学者们，在用元胞自动机解释了雪花的特性后，就得出雪花是由元胞自动机产生的，在解 释了树叶的特性后，就得出树叶是用元胞自动机产生的，进而就说宇宙中万事万物都是元胞自动机产生的。显然，这种思维方式过于跳跃。这一飞跃，并没有任何逻 辑的通道，也没有任何科学理论为其提供有说服力的辩护。实际他论证的是元胞自动机的表现和我们观察到的不矛盾，但凭这个就说实际情况一定是元胞自动机吗？ 而且，用元胞自动机描述雪花，需要六角形的元胞，可是如果没有对冰的晶体结构的了解，我们怎么可能知道这一点？可以说，对水分子之间的相互作用的认识，是 经验性的知识；用元胞自动机描述雪花，是一种数学模型，是事后的拟合。元胞自动机就和含混晦涩的中国古籍《易经》似的，在形形色色的学者生搬硬套下，什么 都可以套上，怎么理解都行，但却得不到什么新的有意义的成果。
沃尔夫拉姆10多年来闭门造车，远离了学术圈子的监督和评价，因而没有把“他证明了的”、“用实验演示了的”和“仅仅是一种推测”这三种情况明确区别开来。的确，诚如某个批评者所说，元胞自动机从来没有产生出一种比一条蚯蚓更复杂的生物来。
诺贝尔物理学奖获得者、得克萨斯大学教授史蒂文·温伯格（S. Weinberg） 在一篇书评中写道：沃尔弗拉姆的书尽管有趣，却是一个“失败”，真实世界中没有一个复杂现象是能通过他的计算机实验令人信服地阐释清楚的。甚至有一位评论 者这样写道：“沃尔夫拉姆极端狂妄自大地把他的关于元胞自动机的书取名为《一种新科学》，但这不是新的，这也不是科学。”
第二，带着浓厚的悲观色彩。
抛 开哲学层面上的意义不谈，沃尔夫拉姆想借助元胞自动机理论建立其“新科学”，人们显然期望它有更为具体的含义和更为实在的用途。但是沃尔夫拉姆在《一种新 科学》正文最后一章最后一个段落里表达的意思把人们的期望变成了失望：“最后，‘计算等价原理’真正浓缩了科学的极端威力和科学的根本缺点。因为它意味 着，所有宇宙间的奇迹都成了几条简单规则的俘虏，然而它也表明，除了实实在在地注视、观看这些规则会如何呈现其结果之外，没有任何办法去预先知道这些结 果。”
第4级别的元胞自动机的一个属性就是它具有不可化归性，它即将生成的图案是不可预测的。既然属于第四类规则的规则110元胞自动机是普适的，任何相当复杂的系统又都等价于规则110元 胞自动机。因此，大到宇宙，小到一桶生锈的铁钉，所有这些复杂系统的行为都不可能被预测。“新科学”家们所能做的就是像植物学家一样瞪大眼睛观察。想知道 明天的宇宙是什么样子的？那么耐心地等到明天吧，因为没有比实际运行宇宙这台元胞自动机更快的方法来让你知道明天的宇宙是什么样子的。
沃尔夫拉姆的“新科学”就这样把人类置于不能预测、只能被动观察的境地，它除了在可能会兴起的“观测数学”这样一种学科中有所作用外，实在看不出“新科学”相对于“传统科学”有什么优势。
伽利略说过：“大自然这本书是用数学这种语言写成的。”伽利略首创把从实验中观察到的规律用数学公式表达出来，被尊为现代科学的奠基人。1638年 伽利略出版《关于两种新科学的谈话》，那里的科学才是真正意义上的新科学。此后，从牛顿到爱因斯坦，“传统科学”极大地满足了人类探索宇宙的好奇心，极大 地改善了人类的生活。是从行星的运动，到恒星的演化，到宇宙的膨胀，人类靠数学方程式一步一个脚印地推进了对宇宙本质的认识。“真正的科学应该是有预测能 力的，而不只是描述性的。……‘新科学’应该给出可证实的或可证伪的预言。”波普尔（Popper）作如是说。而沃尔夫拉姆的元胞自动机除了告诉人们“等着瞧”之外，还能做什么呢？
计算主义如此悲观的结论让人们对它的信服度大打折扣。
第三，对生命的理解不完备。
计 算主义有夸张的嫌疑。不同学科的人在定义生命时，往往从本学科出发，把生命的某一方面加以强调，把某一方面作为生命的本质。比如，生理学往往把能够完成诸 如消化、新陈代谢、排泄、呼吸、运动、生长、发育和对外界刺激做出反应的功能的系统定义为生命系统。生物化学和分子生物学又往往把生命有机体看作是可传递 编码在DNA和RNA中 的遗传信息的系统。进化论往往把一个能够通过自然选择进化的系统看作是生命系统。热力学则又把生命看作是一个与它的环境交换物质和能量的开放系统，以负熵 为生。人工智能认为能思维就是生命。人工生命的信息定义强调生命在生长和繁殖过程中信息的传递作用。但其实，物质和能量同样是生命的不可或缺的部分。把生 命简单归结为信息，归结为计算，不恰当。而且，生命有很多特征，比如能思维，能自我繁殖，能学习，有适应性，具有七情六欲等等一切，都是不可或缺的。
根 据这种对完备性的要求，我们能说人工生命和人工智能等科学创造的所谓“生命”可以作为真实世界生物体形式的一种模型吗？我们能说元胞自动机能构造出自我复 制的机器就表明生命是元胞自动机吗？问题似乎并不那么简单。虽然这些计算机形态与我们今天在地球上看到的真实生物在某些方面非常相似，但也有很多差异。真 实生物体是三维的对象，有丰富的内部结构，然而，人工的数字生物形态仅仅是二维创造物，根本没有体积，而且实际上什么都不能做，它们仅仅是数学对象。所 以，当这些计算机创造物面对“可信度”问题时，无一幸免地遭到了失败。
生命科学说明是生命过程是计算，这种倾向是好的，但是生命科学从来就没有承认生命完全只是计算。假如生命过程纯粹就是DNA的计算，那么参与计算的DNA实体又是什么呢？
第四，盲目相信计算机模拟方法，而这种方法本身存在极限。
在沃尔夫拉姆看来，计算机模拟这种新型的研究方法似乎是万能的。而所有元胞自动机模型，无一不是在计算机上进行模拟。但是至少有如下三点使我们感觉到计算机模拟这种研究方法存在着极限。
1．目前计算机能力有限。
冯·诺伊曼曾经计算过，他的能自我复制的元胞自动机，如果要实现的话，将需要20万个元胞。威廉·庞德斯通（William Poundstone）发现在生命游戏中构造自我复制的元胞自动机需要大约1013个元胞。这是现在的任何计算机都不可能处理的。前面我们说过，计算主义认为，只要设计一个无限大的元胞空间，就可以用元胞自动机模拟宇宙，但是显然我们根本无法设计一个无限大的元胞空间。
2．模拟系统是封闭系统，不具开放性。
我 们还忽视了一个很重要的问题，那就是人们用任何计算机或者元胞自动机来模拟生命时，都是在设置好基本的参数和规则后让程序自发的演化，这样的系统整体上就 是一个封闭系统了。也就是，在没有人的干预下，该系统没有新的信息被注入。按照耗散结构理论的观点，这样的孤立系统会走向无序状态。因为，我们可以想见， 这样的计算机模拟系统能够涌现出来的复杂性也不是永恒增长的，即便它能够得到类似生命这样的现象，但是无论这样的系统多么复杂，它必然存在一个极限。而我 们的生命系统是开放的，正是由于其开放性，它避免了熵和无序性恒增导致的热寂。如果用计算机模拟系统无法得到真正类似生命的现象，我们何以相信生命就是计 算机呢？
其实，计算主义者很早就考虑过这个问题。他们早就发现了程序固定的图灵机不能等价于人脑，于是他们设想了一个“时刻都在改变自己程序的图灵机”25，以应付反对者们的驳斥。但是，这种设想还只能停留在设想阶段。而在元胞自动机领域里，有着开放特征的元胞自动机（即在演化过程中可以人为干涉），能够在演化过程中改变规则的元胞自动机26还从来没有被人所提出和实现。
3．模拟方法本身存在极限。
1994年2月，《科学》（Science）杂志发表了奥米·奥雷斯克（Naomi Oreskes）、肯尼斯·贝尼兹（Kenneth Belitz）、克里斯丁·施雷特·弗雷谢特（Kristin Shrader Frechette）三人合作的文章《地球科学中数值模型的验证及其有效性》，指出计算机模型具有一个极限，当一个模型精确的拟合了一个真实的行为时，甚至对这个行为作出了准确的预测，我们仍然不能说模型已经得到验证。因为我们无法确定这种吻合是否是一种巧合。27
按照这个观点，即使前面我们的元胞自动机模型（显然是在计算机演示的模型）能够在设计者极其巧妙的设计下演化出跟真实世界一样的图案，我们却仍然不能理直气壮的宣布元胞自动机模型就代表了真实的世界。
6．3 小结
计算主义已经在各个领域遭到批判。28对 计算主义形成起着重要作用的某些学者就清醒的反对计算主义，比如朗顿本身就明确表明自己是神秘主义者，认为对意识的解释超越于科学之外。此外，即使是同属 计算主义阵营的、或者对于计算主义观点的形成有着重要作用的各个不同领域的学者们也往往坚持用自己的理论来诠释计算主义，而不一定赞同对方的观点。比如霍 兰德坚持用“受限生成过程”解释世界，而沃尔夫拉姆坚信“元胞自动机”是宇宙之本。此外，反对计算主义的人认为，计算主义者对计算、算法和可计算概念存在 误读，对计算功能和局限性的估计不足，计算主义这种极端还原主义的哲学信念与其所能提供的证据的确凿证据程度显然不成比例，从而必然在实践和理论两个方面 都遭遇困难。从上面我们也看到，元胞自动机理论虽然有力的支持了计算主义，但是这种支持作用有一部分是经不起严格推敲的，而且也很难让人信服。
总之，虽然元胞自动机理论和计算主义的观点给我们指出了一条好的思路，给了我们诸多启发，但是我们要警惕局限在“计算”这个思路之内而束缚了我们的思维和视野。
致谢
七年前，在故土成为水乡泽国的时刻，我却幸运的在社会各界的关怀下，来到向往已久的中国人民大学，圆了自己的大学梦。六年学习生涯，弹指一挥间，人大也发生了翻天覆地的变化。今天的论文，是我留给母校唯一的东西。
我 要感谢我的导师方美琪教授。她给我们创造了一个轻松活泼的科研环境，让我在经济科学实验室度过了三年愉快而又受益匪浅的岁月。在我生病的时候，她特意批准 了我漫长的假期，让我安心休养，恢复健康。她的平易近人、宽厚仁慈、渊博学识和饱满的工作热情深刻地体现了“学为人师，行为师范”的准则。
我 要感谢陈禹教授，是他引导我走进复杂性研究这片神奇的天地。我的论文选题直接源于他对我的引导。他是一位有着神奇魅力的教师，他给我上的每一节课，都让我 痴迷不已、终生难忘。我尤其要感谢他对我论文的指导。起初在我一次次萌生出一些幼稚想法的时候，他总是能够点头肯定我的想法，并给我积极的建议，这给了我 极大的鼓励。他花费大量的时间来读我不成样式的涂鸦般的初稿，并提出修改意见。他的个人魅力、治学风范和领导才能让我见识了一位真正的学者。
我要感谢我的父母兄弟，他们的辛劳和奉献让我体会到了家庭的温暖和世界上最无私的亲情之爱。没有他们的辛勤劳作，就没有一个能在大学校园里中的我，遑论今天的硕士学术论文。
我 要感谢王阿姨。在我家乡受水灾后，是她一直在资助我读大学。她的不带任何功利心的善举，减轻了我家庭的负担，也让我得以安心学习。此外，她还在生活上给予 我无微不至的关心，在思想上给予我的悉心诚恳的教导。她在我人生成长中永远扮演着极其重要的角色。我的论文也是为她而作。
我要感谢我的女朋友，她也一直关心着我的论文。因为她的存在，我永远都以一颗快乐的心去键入论文的每一个字。
我 要感谢经济科学实验室的其他老师和同学，包括已经离校的师兄师姐们和尚在就读的师弟师妹们，尤其是我的两位室友陈起和兰兴伟，他们让我汲取了知识，增长了 见识，体会到了深深的师生之情，同门之情。他们的学识，他们的人格，都深深的影响和感染了我，使我在几年的学习生涯中不会有空虚，不会有寂寞，只有徜徉知 识的充足，享受关爱和幸福的温情和永不褪色的感激。
参考文献
1．《复杂―诞生于秩序与混沌边缘的科学》（美）米歇尔·沃尔德罗著 陈玲译 三联书店 1997年4月北京第一版
2．《沃尔夫勒姆和他的“新科学”》钮卫星 载《文景》2003年3月号
3．《A new kind of science》Stephen Wolfram 2001（国家图书馆外文图书馆藏）
4．《计算主义质疑》作者刘晓力 载于《哲学研究》2003年4月（作者邮箱：liuxiaoli@263.net.cn）
5．《地理元胞自动机研究》 周成虎 孙战利 谢一春著 科学出版社1999年12月第一版
6．《科学的终结》（美）约翰·霍根著 远方出版社 1997年10月第一版
7．《系统科学》 许国志主编 上海科技教育出版社 2000年9月第一版
8．《走向计算主义——数字时代人工创造生命的哲学》 李建会著 中国书籍出版社 2004年1月第一版
9．《与真理为友》 李建会著 上海科技教育出版社 2002年第一版
10．《皇帝的新脑》（英）彭罗斯著 许明贤 吴忠超译 湖南科学技术出版社 1996年10月第一版
11．《数学·计算·逻辑》陆汝钤著 湖南教育出版社 1993年4月第一版
12．《图灵机与计算问题》张江著 见集智俱乐部网站
13．《物理系统的元胞自动机模拟》 2003年8月第一版 （美）Bastien著 清华大学出版社
14．网站：www.wolfram.com
15．网站：www.swarmagents.com（集智俱乐部）
16．《life at the edge of chaos》Langton 1992，国家图书馆的第二届人工生命论文集（artificial life II）
17．《细观元胞自动机与三分子反应模拟》作者李才伟 吴金平 计算机与应用化学（COMPUTERS AND APPLIED CHEMISTRY ） 2000年
18．《涌现－从混沌到有序》（美）约翰·霍兰著 陈禹等译 方美琪校 上海科学技术出版社 2001年11月第一版
19． 《Quantum Cellular Automata》, Bassam Aoun and Mohamad Tarifi ,2005
20．《statistical mechanics of cellular automata》,Stephen Wolfram , Reviews of modern physics, Vol. 55 NO. 3, July 1983