1,526
个编辑
更改
无编辑摘要
[[File:CA3D.gif|400px|right|thumb|基于元胞自动机的三维展示]]
[[File:CA3D.gif|400px|right|thumb|基于元胞自动机的三维展示]]
<br>元胞自动机由规则的元胞网格组成，散布在规则格网（Lattice Grid）中的每一元胞（Cell）取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。
<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 异步元胞自动机]。
首先每个单元格都处于有限状态中的一种，例如打开状态和关闭状态（与耦合映象晶格 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 沃尔弗拉姆对一维元胞自动机进行了系统的研究，他称其为[https://en.wikipedia.org/wiki/Elementary_cellular_automaton 初等元胞自动机]。他的研究助理马修·库克（Matthew Cook）指出，这些规则是'''图灵完备 Turing-complete'''的。沃尔弗拉姆在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 沃尔弗拉姆对一维元胞自动机进行了系统的研究，他称其为[https://en.wikipedia.org/wiki/Elementary_cellular_automaton 初等元胞自动机]。他的研究助理马修·库克（Matthew Cook）指出，这些规则是'''图灵完备 Turing-complete'''的。沃尔弗拉姆在2002年发表了《[[一种新科学 a New Kind of Science]]》这一著作，文中指出元胞自动机已在许多科学领域得到应用，包括计算机处理器和密码学。
==概述==
==概述==
沃尔弗拉姆在[https://en.wikipedia.org/wiki/A_New_Kind_of_Science 《[[一种新科学 a New Kind of Science]]》]和20世纪80年代中期的几篇论文中，将元胞自动机和其他几种简单的计算模型根据其行为进行分为四个类别:
沃尔弗拉姆在[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)复杂型：出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。从另一角度，元胞自动机可视为动力系统，因而可将初试点、轨道、不动点、周期轨和终极轨等一系列概念用到元胞自动机的研究中。
从另一角度，元胞自动机可视为动力系统，因而可将'''初始点、轨道、不动点、周期轨和终极轨'''等一系列概念用到元胞自动机的研究中，上述分类，又可以分别描述为：
从另一角度，元胞自动机可视为动力系统，因而可将'''初始点、轨道、不动点、周期轨和终极轨'''等一系列概念用到元胞自动机的研究中，上述分类，又可以分别描述为：