更改

}}

}}

'''元胞自动机'''（中文也译作细胞自动机，英文名称Cellular Automata或Cellular Automaton，缩写成CA）是一种离散模型，广泛应用于[[计算机科学]]、物理学、[[复杂系统]]，理论生物学和微观结构模型等领域。元胞自动机同时也被称为元胞空间，棋盘自动机 tessellation automata，同质结构，元胞结构，棋盘结构和迭代数组。<ref name="Wolfram">Wolfram, Stephen (1983) [https://pattern.swarma.org/paper?id=72996efc-6f19-11ea-a943-0242ac1a0005 "Statistical Mechanics of Cellular Automata"].Reviews of Modern Physics.55.(601--644)</ref>

‘’‘元胞自动机 cellular automata’‘’（CA） 是一种时间、空间、状态都离散，空间相互作用和时间因果关系为局部的网格动力学模型，具有模拟复杂系统时空演化过程的能力。由冯·诺依曼创始，经数学家Conway、物理学家Wolfram等人的贡献后迅速发展。中文也译作细胞自动机、点格自动机、分子自动机或单元自动机，广泛应用于[[计算机科学]]、物理学、[[复杂系统]]，理论生物学和微观结构模型等领域。元胞自动机同时也被称为元胞空间，棋盘自动机 tessellation automata，同质结构，元胞结构，棋盘结构和迭代数组。<ref name="Wolfram">Wolfram, Stephen (1983) [https://pattern.swarma.org/paper?id=72996efc-6f19-11ea-a943-0242ac1a0005 "Statistical Mechanics of Cellular Automata"].Reviews of Modern Physics.55.(601--644)</ref>

[[File:CA3D.gif|400px|right|thumb|基于元胞自动机的三维展示]]

[[File:CA3D.gif|400px|right|thumb|基于元胞自动机的三维展示]]

<br>元胞自动机由规则的元胞网格组成，每个单元格都处于有限状态中的一种，例如打开状态和关闭状态（与耦合映象晶格 coupled map lattice相反）。网格可以是任意有限维数。对于每个单元格，都有一组定义为其邻域的单元格。 每个单元格都将被定义一种状态来作为初始状态（时间t = 0）。根据一些固定的规则（通常是一种数学函数）<ref name=" Toffoli">Tommaso; Margolus Norman, Toffoli (1987) [https://pattern.swarma.org/paper?id=af01ed74-6f19-11ea-b9a1-0242ac1a0005 "Cellular Automata Machines: A New Environment for Modeling"].27.</ref>，产生新的状态（t增加1个单位）。单元格当前状态及其附近单元格的状态共同决定了该单元格的新状态。一般而言，更新单元格状态的规则对于每个单元格都是相同的，不随时间变化，适用于整个网格。<ref>Schiff, Joel L (2011) [https://pattern.swarma.org/paper?id=37fb6b22-6f1b-11ea-bbca-0242ac1a0005 "Cellular Automata: A Discrete View of the World"].(40)</ref>然而也有例外，例如[https://en.wikipedia.org/wiki/Stochastic_cellular_automaton 随机元胞自动机]和[https://en.wikipedia.org/wiki/Asynchronous_cellular_automaton 异步元胞自动机]。

 

<br>元胞自动机由规则的元胞网格组成，散布在规则格网（Lattice Grid）中的每一元胞（Cell）取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。

 

首先每个单元格都处于有限状态中的一种，例如打开状态和关闭状态（与耦合映象晶格 coupled map lattice相反）。网格可以是任意有限维数。对于每个单元格，都有一组定义为其邻域的单元格。 每个单元格都将被定义一种状态来作为初始状态（时间t = 0）。根据一些固定的规则（通常是一种数学函数）<ref name=" Toffoli">Tommaso; Margolus Norman, Toffoli (1987) [https://pattern.swarma.org/paper?id=af01ed74-6f19-11ea-b9a1-0242ac1a0005 "Cellular Automata Machines: A New Environment for Modeling"].27.</ref>，产生新的状态（t增加1个单位）。单元格当前状态及其附近单元格的状态共同决定了该单元格的新状态。一般而言，更新单元格状态的规则对于每个单元格都是相同的，不随时间变化，适用于整个网格。<ref>Schiff, Joel L (2011) [https://pattern.swarma.org/paper?id=37fb6b22-6f1b-11ea-bbca-0242ac1a0005 "Cellular Automata: A Discrete View of the World"].(40)</ref>然而也有例外，例如[https://en.wikipedia.org/wiki/Stochastic_cellular_automaton 随机元胞自动机]和[https://en.wikipedia.org/wiki/Asynchronous_cellular_automaton 异步元胞自动机]。

<br>20世纪40年代，这个概念最初是由当时在[https://en.wikipedia.org/wiki/Los_Alamos_National_Laboratory 洛斯阿拉莫斯国家实验室] （Los Alamos National Laboratory）工作的[https://en.wikipedia.org/wiki/Stanislaw_Ulam 斯坦尼斯瓦夫•乌拉姆]（Stanislaw Ulam）和[[约翰·冯·诺依曼 John von Neumann]]发现的。尽管20世纪50年代到60年代一直有学者在研究这个问题，但直到20世纪70年代，随着[[康威的生命游戏 Conway's Game of Life]]的问世（一个二维的元胞自动机），这个问题才引起学术界的关注。20世纪80年代，史蒂芬·沃尔夫勒姆 Stephen Wolfram对一维元胞自动机进行了系统的研究，他称其为[https://en.wikipedia.org/wiki/Elementary_cellular_automaton 初等元胞自动机]。他的研究助理马修·库克（Matthew Cook）指出，这些规则是'''图灵完备 Turing-complete'''的。Wolfram在2002年发表了《一种新科学 A New Kind of Science》这一著作，文中指出元胞自动机已在许多科学领域得到应用，包括计算机处理器和密码学。

<br>20世纪40年代，这个概念最初是由当时在[https://en.wikipedia.org/wiki/Los_Alamos_National_Laboratory 洛斯阿拉莫斯国家实验室] （Los Alamos National Laboratory）工作的[https://en.wikipedia.org/wiki/Stanislaw_Ulam 斯坦尼斯瓦夫•乌拉姆]（Stanislaw Ulam）和[[约翰·冯·诺依曼 John von Neumann]]发现的。尽管20世纪50年代到60年代一直有学者在研究这个问题，但直到20世纪70年代，随着[[康威的生命游戏 Conway's Game of Life]]的问世（一个二维的元胞自动机），这个问题才引起学术界的关注。20世纪80年代，史蒂芬·沃尔夫勒姆 Stephen Wolfram对一维元胞自动机进行了系统的研究，他称其为[https://en.wikipedia.org/wiki/Elementary_cellular_automaton 初等元胞自动机]。他的研究助理马修·库克（Matthew Cook）指出，这些规则是'''图灵完备 Turing-complete'''的。Wolfram在2002年发表了《一种新科学 A New Kind of Science》这一著作，文中指出元胞自动机已在许多科学领域得到应用，包括计算机处理器和密码学。