細胞自動機
维基百科，自由的百科全书
生命遊戲:細胞自動機的例子。
細胞自動機，又稱格狀自動機、元胞自動機，是一種離散模型，在可算性理論、數學及理論生物學都有相關研究。它是由無限個有規律、堅硬的方格組成，每格均處於一種有限狀態。整個格網可以是任何有限維的。同時也是離散的。每格於t時的態由 t-1時的一集有限格（這集叫那格的鄰域）的態決定。 每一格的「鄰居」都是已被固定的。（一格可以是自己的鄰居。）每次演進時，每格均遵從同一規矩一齊演進。
就形式而言，細胞自動機有三個特徵：
- 平行計算（parallel computation）：每一個細胞個體都同時同步的改變
- 局部的（local）：細胞的狀態變化只受周遭細胞的影響。
- 一致性的（homogeneous）：所有細胞均受同樣的規則所支配
目录 |
构成 [编辑]
一个标准的細胞自動機（A）由元胞、元胞状态、邻域和状态更新规则构成。用数学表示为[1]：
其中L为元胞空间；d为元胞自动机内元胞空间的维数；S是元胞有限的、离散的状态集合；N为某个邻域内所有元胞的集合；f为局部映射或局部规则。
元胞空间是元胞所分布的空间网点的集合。理论上元胞空间在各个维向上是无限延伸的，为了能够在计算机上实现，而定义了边界条件，包括周期型、反射型和定值型[2]。
一个元胞通常在一个时刻只有取自一个有限集合的一种状态，例如{0,1}。元胞状态可以代表个体的态度，特征，行为等[3]。在空间上与元胞相邻的细胞称为邻元，所有邻元组成邻域。
历史 [编辑]
細胞自動機最早由冯·诺依曼在1950年代为模拟生物细胞的自我复制而提出的。但是并未受到学术界重视。直到1970年，剑桥大学的约翰·何顿·康威设计了一个电脑游戏《生命游戏》后才吸引了科学家们的注意。此后，S.Wolfram 对初等元胞机256种规则所产生的模型进行了深入研究，并用熵來描述其演化行为，将細胞自動機分为平稳型、周期型、混沌型和复杂型[4]。
參照 [编辑]
参考文献 [编辑]
- ^ 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.
- ^ 周成虎; 孙战利 谢一春. 地理元胞自动机研究. 北京: 科学出版社. 2000: 26–51. ISBN 9787030081209.
- ^ 宣慧玉; 高宝俊. 管理与社会经济系统仿真. 武汉: 武汉大学出版社. 2000. 98-114. ISBN 9787307034075.
- ^ 陈国宏; 蔡彬清,李美娟. 元胞自动机：一种探索管理系统复杂性的有效工具. 中国工程科学. 2007, 9 (1): 28~32 [2010年7月28日].
外部連結 [编辑]
