細胞自動機

维基百科,自由的百科全书
跳转至: 导航搜索
生命遊戲:細胞自動機的例子。

細胞自動機英语Cellular automaton),又稱格狀自動機元胞自動機,是一種離散模型,在可算性理論數學理論生物學都有相關研究。它是由無限個有規律、堅硬的方格組成,每格均處於一種有限狀態。整個格網可以是任何有限維的。同時也是離散的。每格於t時的態由 t-1時的一集有限格(這集叫那格的鄰域)的態決定。 每一格的「鄰居」都是已被固定的。(一格可以是自己的鄰居。)每次演進時,每格均遵從同一規矩一齊演進。

就形式而言,細胞自動機有三個特徵:

  • 平行計算(parallel computation):每一個細胞個體都同時同步的改變
  • 局部的(local):細胞的狀態變化只受周遭細胞的影響。
  • 一致性的(homogeneous):所有細胞均受同樣的規則所支配

构成[编辑]

一个标准的細胞自動機(A)由元胞、元胞状态、邻域和状态更新规则构成。用数学表示为[1]

A = ( L, d, S, N, f)

其中L为元胞空间;d为元胞自动机内元胞空间的维数;S是元胞有限的、离散的状态集合;N为某个邻域内所有元胞的集合;f为局部映射或局部规则。

元胞空间是元胞所分布的空间网点的集合。理论上元胞空间在各个维向上是无限延伸的,为了能够在计算机上实现,而定义了边界条件,包括周期型、反射型和定值型[2]

一个元胞通常在一个时刻只有取自一个有限集合的一种状态,例如{0,1}。元胞状态可以代表个体的态度,特征,行为等[3]。在空间上与元胞相邻的细胞称为邻元,所有邻元组成邻域。

历史[编辑]

細胞自動機最早由美籍數學家冯·诺依曼John von Neumann)在1950年代为模拟生物细胞的自我复制而提出的。但是并未受到学术界重视。直到1970年,任教於剑桥大学的英國數學家约翰·何顿·康威(John Horton Conway)设计了一个电脑游戏《生命游戏》后才吸引了科学家们的注意。此后,英國學者史蒂芬·沃爾夫勒姆(Stephen Wolfram)对初等元胞机256种规则所产生的模型进行了深入研究,并用來描述其演化行为,将細胞自動機分为平稳型、周期型、混沌型和复杂型[4]

分类[编辑]

史蒂芬·沃爾夫勒姆在《一种新科学》和几篇从80年代中期开始的论文中定义了四类,细胞自动机和其他几个简单的计算模型可分为根据他们的行为。元胞自动机的早期研究往往试图确定具体规则的模式类型,他提出的分类是对规则本身分类的第一次尝试。按照复杂性分类的秩序:

  • 1类:几乎所有的初始模式迅速演变成一个稳定的,均匀的状态。在初始模式的任何随机性会消失。[5]
  • 2类:几乎所有的初始模式迅速演化为稳定或振荡结构。一些在初始模式的随机性可能会被过滤掉,但是还有一些保留。在初始模式的局部变化倾向于继续保持局部性。[5]
  • 3类:几乎所有的初始形态将会演变成一个伪随机或混沌的形式。任何稳定的结构很快会被周围的噪音破坏。在初始模式的局部变化有无限蔓延的倾向。[5]
  • 4类:几乎所有的初始模式将会演变成相互作用的复杂和有趣的方式结构,并且局部结构的形成能够长时间存在。[6] 2类的稳定或振荡的结构可能是最终的结果,但需要达到这个状态的步骤数目可能是非常大的,即使在初始模式比较简单的情况下。初始模式的局部变化可能会无限蔓延。史蒂芬·沃爾夫勒姆已推测不是所有的4类细胞自动机能够进行通用计算。这已被证明对于规则110和约翰·何顿·康威生命游戏

根据史蒂芬·沃爾夫勒姆的說法,这些定义在本质上是定性的但是任有解释一些空间。 “……几乎任何一般的分类方案都有不可避免的情况,比如说根据不同的定义会被分配到不同的类里。因此细胞自动机也是这样:偶尔有规则……显示不同类的一些特点。”[7]他的分类已经与一个类具有压缩长度输出的元胞自动机相匹配。[8]

已经有人在尝试进行细胞自动机的正式严格分类根据史蒂芬·沃爾夫勒姆的分类。例如,Culik和Yu提出三种定义的类(并且第四个和它们不同),有时被称为Culik-Yu 类;能够被分到这种类里的问题被证明是不可判定的。[9][10][11] 史蒂芬·沃爾夫勒姆的2类可划分为稳定(定点)和振荡(周期)规则两个小组。[12]

參照[编辑]

参考文献[编辑]

  1. ^ S. Amoroso; Y.N. Patt. Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. Journal of Computer and System Sciences. October 1972, 6 (5): 448–464 [2010年7月28日]. doi:10.1016/S0022-0000(72)80013-8. 
  2. ^ 周成虎; 孙战利 谢一春. 地理元胞自动机研究. 北京: 科学出版社. 2000: 26–51. ISBN 9787030081209. 
  3. ^ 宣慧玉; 高宝俊. 管理与社会经济系统仿真. 武汉: 武汉大学出版社. 2000: 98-114. ISBN 9787307034075. 
  4. ^ 陈国宏; 蔡彬清,李美娟. 元胞自动机:一种探索管理系统复杂性的有效工具. 中国工程科学. 2007, 9 (1): 28~32 [2010年7月28日]. 
  5. ^ 5.0 5.1 5.2 Ilachinsky 2001,第12页
  6. ^ Ilachinsky 2001,第13页
  7. ^ Wolfram 2002,第231页
  8. ^ Zenil, Hector. Compression-based investigation of the dynamical properties of cellular automata and other systems. Complex Systems. 2010, 19 (1). 
  9. ^ G. Cattaneo, E. Formenti, L. Margara. Topological chaos and CA. (编) M. Delorme, J. Mazoyer. Cellular automata: a parallel model. Springer. 1998: 239. ISBN 978-0-7923-5493-2. 
  10. ^ Burton H. Voorhees. Computational analysis of one-dimensional cellular automata. World Scientific. 1996: 8. ISBN 978-981-02-2221-5. 
  11. ^ Max Garzon. Models of massive parallelism: analysis of cellular automata and neural networks. Springer. 1995: 149. ISBN 978-3-540-56149-1. 
  12. ^ Li, Wentian; Packard, Norman. The structure of the elementary cellular automata rule space. Complex Systems. 1990, 4: 281–297 [January 25, 2013]. 

外部連結[编辑]