元胞自动机

来自集智百科
跳转到: 导航搜索

元胞自动机(Cellular Automata,也有人翻译为细胞自动机、点格自动机)是一种在空间和时间上都离散的演化动力系统。系统由正方形、三角形或者立方体等基本几何元素的元胞(Cell)组成,这些元胞按照一定规则排列可以形成一个空间区域,然后每个元胞之上都有若干种离散或者连续的状态,这些状态在每一个时间步都会按照相同的规则发生变化,于是形成了整个元胞自动机的演化过程。人们通常通过元胞自动机来研究从局部简单的规则到整体复杂动态的涌现过程。

从元胞自动机的状态来说,分为有限状态和无限状态两种。所谓的无限状态是指每个元胞的状态都可以由一个或者一组实数构成。从运行的规则来说,可以分为确定型元胞自动机和随机型元胞自动机。从元胞以及构成的空间来说,可以有一维、二维甚至高维。从元胞的形状来说,可以有四边形、三角形、六边形等等。

Stephen Wolfram曾针对一维基础的元胞自动机根据其运行结果进行了分类,包括稳定点(fixed point)、周期(cycle)、混沌(chaos)和复杂(complex)四种类型。其中,复杂类型的元胞自动机通常同时具备局部的结构,以及这些局部结构在长程空间上的传递。因此,这种类型的元胞自动机可以支持非常复杂的运算。Wolfram曾证明,110号元胞自动机可以支持通用计算,也就是模拟任意一台图灵机的运算。

在复杂系统研究中,元胞自动机是一种很好的离散模拟模型,可以用于森林火灾、交通、股票市场等复杂系统的模拟之中。另外,元胞自动机也是一种常用的物理学研究手段,例如著名的格子气自动机就可以模拟气体系统。

目录

研究历史

早在1940年,洛斯阿拉莫斯国家实验室的数学家Stanislaw Ulam就在研究晶体生长的过程中,提出了一个简单的网格网络模型。与此同时,Ulam的同事John von Neumann正在研究生命系统的自复制问题,在Ulam的建议下,冯诺依曼采用了一种具有29个状态的二维元胞自动机模型,这应该是一种最早的元胞自动机。在这个自动机中,冯诺依曼构造出了一种结构,这种结构可以像原始细胞那样不断地进行自我复制并分裂。

到了1960年,元胞自动机被视为一种特定的动力学系统,这种系统与符号动力学有着深刻的联系。1969年,Gustav A. Hedlund采用这种观点作出了元胞自动机数学研究的开创性工作。其中最主要的结果就是Curtis–Hedlund–Lyndon定理,它将元胞自动机全局规则视为一组转移空间(shift spaces)上的连续自同态。1969年,德国计算机先驱Zuse出版了“计算空间(Calculating Space)一书,提出了宇宙中的物理定律是离散的,整个宇宙就是一台确定性的元胞自动机的计算结果。现在,”Zuse理论“被认为是数字物理学的基础。1969年,Alvy Ray Smith在博士论文中将元胞自动机视为一种通用计算机。在他的博士论文中,Alvy做了大量的理论分析,确定了各种等价类。1970年,著名的二维元胞自动机“生命游戏”被数学家John Conway提出来,并且由于Martin Gardner在“科学美国人”写作了一篇介绍该元胞自动机的文章,这使得生命游戏开始流行起来。

到了1983年,Stephen Wolfram在Reviews of Modern Physics上发表了探索基础元胞自动机(一维,每个元胞仅仅有两种状态,以及左右两个邻居)的文章,并提出了四种分类。1990年代,Wolfram的助手Matthew Cook证明了110号基础元胞自动机是支持通用计算的。到了2002年,Wolfram出版了一本厚达1280页的巨著”一种新科学“(A New Kind of Science),并指出元胞自动机绝不是一种鼓励的现象,而是对于其它学科都有很重要作用的模型。我们从元胞自动机中得到的结论,例如内在随机性和计算不可约简性是宇宙中的通用规律。

元胞自动机举例

生命游戏

生命游戏是英国数学家约翰·康威(John Conway)在1970年发明的细胞自动机。它最初于1970年10月在《科学美国人》杂志中马丁·加德纳(Martin Gardner,1914年11月21日-2010年5月22日)的“数学游戏”专栏出现。

生命游戏是一种二维的元胞自动机,每个元胞都有黑白两种不同的状态,每个元胞都有周围八个方格作为邻居。生命游戏的规则如下:

  1. 如果一个元胞周围有3个元胞为生,则该元胞为生(即该元胞若原先为死,则转为生,若原先为生,则保持不变) 。
  2. 如果一个元胞周围有2个元胞为生,则该元胞的生死状态保持不变;
  3. 在其它情况下,该元胞为死(即该元胞若原先为生,则转为死,若原先为死,则保持不变)

当所有的元胞都按照这个规则检查它的邻居,并运行起来后,我们可以得到非常复杂的动态过程。

Gospers glider gun.gif

另外,生命游戏中还会诞生出一种被称为“滑翔机”的局部结构,它的动态运行情况如下图所示:

Glider.png

“滑翔机”可以作为一种局部传递信息的结构。可以利用“滑翔机”搭建更加复杂的动态结构。

一维基础元胞自动机

最简单的元胞自动机就是一维的元胞自动机。在其上,每个元胞都有黑、白两种颜色,每个元胞都有左右两个邻居。由于每个元胞有两个状态,这样,当前元胞加上左右两个邻居一共就有8种状态:

屏幕快照 2015-12-11 23.34.46.png

他们表示的状态分别是:000,001,010,011,100,101,110,111,其中0表示白色,1表示黑色。

下面考虑规则,由于元胞自动机的规则就是根据每个元胞和它的邻居的当前状态转移到下一个时刻该元胞的状态。无论规则是什么样的黑箱,它的输入就是上面列出的8种组合之一,因为表示的是每个元胞下一时刻的状态,而状态只可能有0、1两种,则规则的输出要么是0,要么是1。这样,任何一个规则都是一个或者一组转换,比如下图表示的就是一条规则:

屏幕快照 2015-12-11 23.36.07.png

另外,若有一个规则是:“如果输入的三个元胞中黑色方格只有1个,那么下一时刻当前元胞就是黑色”可以表示成下面的图:

屏幕快照 2015-12-11 23.36.54.png

下面我们再把目光转到规则集上。由于每一条规则都是一个状态或一组状态的转换,那么把输入的8种可能情况转换到当前元胞的下一状态。我们可以用一个转换表表示一组规则集,例如:

屏幕快照 2015-12-11 23.37.37.png

这个规则集也可以用下面的一组数字表示为:

屏幕快照 2015-12-12 00.36.36.png

每一组规则集也可以表示成类似于上面的图和表,例如下面的另外一组规则

屏幕快照 2015-12-12 00.36.43.png

由于邻居加上当前元胞一共8种状态,每一个状态对应两种可能转换规则,所以规则一共就有2^8=256种,我们可以为每一个规则编码,然后对其进行穷举。

下面我们来考察这256中元胞自动机所具备的可能动态行为。对于一维的情况,我们假设所有的元胞都分布在一条直线上,并且直线的长度为300,也就是说有300个元胞在这条直线上,那么一条断续的横线就是当前所有细胞状态的一种分布。这些方格随着时间变化,就形成了不同的横线。我们把这些随着时间变化的线纵向拼在一起形成了一个网格区域。其中纵轴表示时间的流逝(往下为正),横轴为“元胞自动机在对应时刻的状态,就能得到一幅图像:

屏幕快照 2015-12-12 00.42.38.png

这个元胞的每一行都是某一个时刻元胞自动机的状态。因而从上到下数第1、2、3、4、5、6行可以分别表示第1、2、3、4、5、6时间步的元胞自动机状态。因此这里的一个平面的图案就是元胞自动机在时间上的发展动态。下面我们分别挑选几种典型的动态情况示于下图(下方的数字是元胞自动机的编码):


屏幕快照 2015-12-12 00.42.44.png

屏幕快照 2015-12-12 00.44.21.png

110号元胞自动机属于复杂类型,它的运行图如下所示:

Fig7.jpg

从图中我们可以看出,110号元胞自动机存在着大量的局域化的结构,有些结构可以在元胞之间传递。它的动态行为既非秩序亦非随机,属于介于秩序与混沌边缘的复杂类型。

参考文献

  1. von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press.
  2. Wolfram, Stephen (1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55 (3): 601–644.
  3. Gardner, Martin (1970). "Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"". Scientific American (223): 120–123.
  4. Ilachinski, Andrew (2001). Cellular automata: a discrete universe. World Scientific. pp. 44–45.
  5. Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080.
  6. Gutowitz, Howard, ed. (1991). Cellular Automata: Theory and Experiment. MIT Press.
  7. Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific.
个人工具
名字空间
操作
导航
工具箱