更改

|description=元胞自动机,复杂系统

|description=元胞自动机,复杂系统

}}

}}

<br>元胞自动机由规则的元胞网格组成，散布在规则格网中的每一元胞取有限的离散状态，例如打开状态和关闭状态（与耦合映象晶格 coupled map lattice相反），遵循某种同样的作用规则并依据确定的局部规则作同步更新，通过相互作用而构成动态系统的演化。

 

<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 异步元胞自动机]。

网格可以是任意有限维数。对于每个单元格，都有一组定义为其邻域的单元格。 每个单元格都将被定义一种状态来作为初始状态（时间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]]》这一著作，文中指出元胞自动机已在许多科学领域得到应用，包括计算机处理器和密码学。

==概述==

==概述==

[[File:摩尔邻域.png|150px|thumb|红色单元格是蓝色单元格的摩尔邻域]]

[[File:摩尔邻域.png|150px|thumb|红色单元格是蓝色单元格的摩尔邻域]]

[[File:冯诺依曼邻域.png|150px|thumb|红色单元格是蓝色单元格的冯·诺依曼邻域。扩展的邻域也包括粉色单元格]]

[[File:冯诺依曼邻域.png|150px|thumb|红色单元格是蓝色单元格的冯·诺依曼邻域。扩展的邻域也包括粉色单元格]]

<br>模拟二维元胞自动机的一种方法是用一张无限大的方格纸，加上一套元胞规则来构成。每个正方形被称为“单元格” ，每个单元格有两种可能的状态，黑色和白色。 单元格的邻域是指周围的单元格。 最常见的两种邻域类型有[https://en.wikipedia.org/wiki/Von_Neumann_neighborhood 冯诺依曼邻域]（von Neumann neighborhood）和[https://en.wikipedia.org/wiki/Moore_neighborhood 摩尔邻域]（Moore neighborhood）。前者由4个 正交相邻的单元格组成。 后者包括冯诺依曼领域和斜对角相邻的4个单元格。<ref name = "Kier" >Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modeling Chemical Systems using Cellular Automata. Springer. ISBN 9781402036576.</ref>对于每个单元格及其摩尔邻域，有512(2⁹)种可能的自动机模式。 对于每一种模式，规则表将确定在下一个时间段中中心单元格是黑色还是白色。[[康威生命游戏]]就是这种模式的一个流行版本。 另一种常见的邻域类型是扩展的冯诺依曼邻域，它包括每个正交方向上最近的2个单元格，总共8个单元格。<ref name = " Kier "></ref>这种规则的一般方程是 k^{k^s}，其中 k 是一个单元格可能状态的数目，s 是用来确定单元格下一个状态的相邻单元格的数目(包括要计算的单元格本身)。<ref >Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0198531005.

<br>模拟二维元胞自动机的一种方法是用一张无限大的方格纸，加上一套元胞规则来构成。每个正方形被称为“单元格” ，每个单元格有两种可能的状态，黑色和白色。 单元格的邻域是指周围的单元格。 最常见的两种邻域类型有[https://en.wikipedia.org/wiki/Von_Neumann_neighborhood 冯诺依曼邻域]（von Neumann neighborhood）和[https://en.wikipedia.org/wiki/Moore_neighborhood 摩尔邻域] Moore neighborhood。前者由4个正交相邻的单元格组成。 后者包括冯诺依曼领域和斜对角相邻的4个单元格。<ref name = "Kier" >Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modeling Chemical Systems using Cellular Automata. Springer. ISBN 9781402036576.</ref>对于每个单元格及其摩尔邻域，有512(2⁹)种可能的自动机模式。 对于每一种模式，规则表将确定在下一个时间段中中心单元格是黑色还是白色。[[康威的生命游戏 Conway's Game of Life]]就是这种模式的一个流行版本。 另一种常见的邻域类型是扩展的冯诺依曼邻域，它包括每个正交方向上最近的2个单元格，总共8个单元格。<ref name = " Kier "></ref>这种规则的一般方程是 k^{k^s}，其中 k 是一个单元格可能状态的数目，s 是用来确定单元格下一个状态的相邻单元格的数目(包括要计算的单元格本身)。<ref >Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0198531005.

  </ref>

  </ref>

因此，在二维的摩尔邻域中，可能出现的自动机模式共有2^2⁹个，即1.34*10¹⁵⁴个。

因此，在二维的摩尔邻域中，可能出现的自动机模式共有2^2⁹个，即1.34*10¹⁵⁴个。

<br>通常假设整个网格中除了有限数量的单元格处于不同状态之外，其他的每个单元格具有相同的初始状态。这些状态值的分配被称为配置（configuration）。<ref name = " Schiff " >Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World. Wiley & Sons, Inc. p. 40. ISBN 9781118030639. </ref>更笼统地说，人们有时假设整个网格从一开始时就具有周期性模式，只有有限数量的单元格违反了这个模式。这种假设在一维元胞自动机中很常见。

<br>通常假设整个网格中除了有限数量的单元格处于不同状态之外，其他的每个单元格具有相同的初始状态。这些状态值的分配被称为配置 configuration。<ref name = " Schiff " >Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World. Wiley & Sons, Inc. p. 40. ISBN 9781118030639. </ref>更笼统地说，人们有时假设整个网格从一开始时就具有周期性模式，只有有限数量的单元格违反了这个模式。这种假设在一维元胞自动机中很常见。

<br>元胞自动机通常是在有限网格上模拟的，而不是在无限网格上。在二维空间中，整个网格将是一个矩形而不是一个无限平面。有限网格最大的问题就是如何处理边缘的单元格。处理它们的方式将影响网格中所有单元格的值，一种方法是允许这些单元格中的值保持不变；另一种方法是为这些单元格定义不同的邻域。

<br>元胞自动机通常是在有限网格上模拟的，而不是在无限网格上。在二维空间中，整个网格将是一个矩形而不是一个无限平面。有限网格最大的问题就是如何处理边缘的单元格。处理它们的方式将影响网格中所有单元格的值，一种方法是允许这些单元格中的值保持不变；另一种方法是为这些单元格定义不同的邻域。

虽然可以认为边缘单元格的邻域较少，但是必须为其定义新规则。这些单元格通常以环形排列处理: 当一个单元格无上邻域时，将该单元格相应位置的网格底部单元格作为上邻域，当一个单元格无左邻域时，将该单元格相应位置的网格右侧单元格作为右邻域。(这实质上模拟了无限周期的拼接，在偏微分方程领域有时被称为周期边界条件。)这可以想象为用胶带把矩形的左右边缘粘在一起形成一个管状，然后把管的顶部和底部边缘粘在一起形成一个圆环(甜甜圈形状)。其他维度的网格也是这样处理的。这种方法不仅解决了邻域的边界问题，而且易于通过使用模块化计算功能编程。例如，在一维元胞自动机中，单元格 x_i^t 的邻居是{ x_i-1^t-1，x_i^t-1，x_i+1^t-1} ，其中 t 是时间步长(纵轴)，i 是一代中的索引(横轴)。

虽然可以认为边缘单元格的邻域较少，但是必须为其定义新规则。这些单元格通常以环形排列处理: 当一个单元格无上邻域时，将该单元格相应位置的网格底部单元格作为上邻域，当一个单元格无左邻域时，将该单元格相应位置的网格右侧单元格作为右邻域。(这实质上模拟了无限周期的拼接，在偏微分方程领域有时被称为周期边界条件。)这可以想象为用胶带把矩形的左右边缘粘在一起形成一个管状，然后把管的顶部和底部边缘粘在一起形成一个圆环(甜甜圈形状)。其他维度的网格也是这样处理的。这种方法不仅解决了邻域的边界问题，而且易于通过使用模块化计算功能编程。例如，在一维元胞自动机中，单元格 x_i^t 的邻居是{ x_i-1^t-1，x_i^t-1，x_i+1^t-1} ，其中 t 是时间步长(纵轴)，i 是一代中的索引(横轴)。

<br>[[File:圆环.png|150px|thumb|center|圆环]]

<br>[[File:圆环.png|150px|thumb|center|圆环:甜甜圈形状]]

==研究历史==

==研究历史==