1,526
个编辑
更改
无编辑摘要
}}
}}
'''元胞自动机'''(中文也译作细胞自动机，英文名称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或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>
<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 name="Schiff">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>元胞自动机由规则的元胞网格组成，每个单元格都处于有限状态中的一种，例如打开状态和关闭状态（与耦合映象晶格 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》这一著作，文中指出元胞自动机已在许多科学领域得到应用，包括计算机处理器和密码学。
==概述==
==概述==
==分类==
==分类==
Wolfram在[https://en.wikipedia.org/wiki/A_New_Kind_of_Science 《[[a New Kind of Science]]》]和20世纪80年代中期的几篇论文中，将元胞自动机和其他几种简单的计算模型根据其行为进行分为四个类别。早期关于元胞自动机研究倾向于识别特定规则的模式类型，而沃尔弗拉姆的分类是首次尝试对规则本身进行分类。按照复杂程度的顺序，类别如下:
Wolfram在[https://en.wikipedia.org/wiki/A_New_Kind_of_Science 《[[a New Kind of Science]]》]和20世纪80年代中期的几篇论文中，将元胞自动机和其他几种简单的计算模型根据其行为进行分为四个类别:
(1)平稳型：自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。
(2)周期型：经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Perlodical Patterns)。由于这些结构可看作是一种滤波器(Filter)，故可应用到图像处理的研究中。
(3)混沌型：自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变化，通常表现为分形分维特征。
(4)复杂型：出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。从另一角度，元胞自动机可视为动力系统，因而可将初试点、轨道、不动点、周期轨和终极轨等一系列概念用到元胞自动机的研究中。
从另一角度，元胞自动机可视为动力系统，因而可将初始点、轨道、不动点、周期轨和终极轨等一系列概念用到元胞自动机的研究中，上述分类，又可以分别描述为：
(1)均匀状态，即点态吸引子，或称不动点；
(2)简单的周期结构，即周期性吸引子，或称周期轨；
(3)混沌的非周期性模式，即混沌吸引子；
(4)这第四类行为可以与生命系统等复杂系统中的自组织现象相比拟，但在连续系统中没有相对应的模式。
但从研究元胞自动机的角度讲，最具研究价值的具有第四类行为的元胞自动机，因为这类元胞自动机被认为具有"突现计算"(Emergent Computation）功能，研究表明，可以用作广义计算机（Universal Computer）以仿真任意复杂的计算过程。另外，此类元胞自动机在发展过程中还表现出很强的不可逆（lrreversibility）特征，而且，这种元胞自动机在若干有限循环后，有可能会 "死"掉，即所有元胞的状态变为零。
这是早期关于元胞自动机研究倾向于识别特定规则的模式类型，而沃尔弗拉姆的分类是首次尝试对规则本身进行分类。按照复杂程度的顺序，类别如下:
<br>第1类: 几乎所有初始模式都迅速演变为稳定的均匀状态。初始模式中的任何随机性都会消失。<ref name = " Ilachinski " ></ref>
<br>第1类: 几乎所有初始模式都迅速演变为稳定的均匀状态。初始模式中的任何随机性都会消失。<ref name = " Ilachinski " ></ref>
<br>第2类: 几乎所有初始模式都迅速演变为稳定或振荡的结构。初始模式中的某些随机性可能会被滤除，但仍然存在。初始模式的局部更改倾向于保持局部。<ref name = " Ilachinski " ></ref>
<br>第2类: 几乎所有初始模式都迅速演变为稳定或振荡的结构。初始模式中的某些随机性可能会被滤除，但仍然存在。初始模式的局部更改倾向于保持局部。<ref name = " Ilachinski " ></ref>
<br>划分4类动力系统的想法最初来自诺贝尔奖获得者化学家[https://en.wikipedia.org/wiki/Ilya_Prigogine 伊利亚·普里高津 Ilya Prigogine]，他确定了这4类热力学系统: (1)热力学平衡系统，(2)空间 / 时间均匀系统，(3)混沌系统，(4)具有耗散结构的复杂远离平衡系统。<ref name = "Nicolis">{{Cite journal|title= Dissipative Structures, Catastrophes, and Pattern Formation: A Bifurcation Analysis |author1= Nicolis |journal= PNAS |date=1974|volume=71|issue=7|pages=2748-2751|url= http://www.complex-systems.com/pdf/04-3-3.pdf }} </ref>
<br>划分4类动力系统的想法最初来自诺贝尔奖获得者化学家[https://en.wikipedia.org/wiki/Ilya_Prigogine 伊利亚·普里高津 Ilya Prigogine]，他确定了这4类热力学系统: (1)热力学平衡系统，(2)空间 / 时间均匀系统，(3)混沌系统，(4)具有耗散结构的复杂远离平衡系统。<ref name = "Nicolis">{{Cite journal|title= Dissipative Structures, Catastrophes, and Pattern Formation: A Bifurcation Analysis |author1= Nicolis |journal= PNAS |date=1974|volume=71|issue=7|pages=2748-2751|url= http://www.complex-systems.com/pdf/04-3-3.pdf }} </ref>
=== 可逆的 ===
=== 可逆的 ===