查看“︁細胞自動機”︁的源代码

[[File:Gospers glider gun.gif|frame|right|[[生命遊戲]]:細胞自動機的例子。]]
'''細胞自動機'''（{{lang-en|'''Cellular automaton'''}}），又稱'''格狀自動機'''、'''元胞自動機'''，是一種[[離散模型]]，在[[可计算性理論]]、[[數學]]及[[理論生物學]]都有相關研究。它是由無限個有規律、堅硬的方格組成，每格均處於一種有限[[狀態]]。整個格網可以是任何有限維的。同時也是[[離散]]的。每格於t時的態由t-1時的一集有限格（這集叫那格的鄰域）的態決定。每一格的「鄰居」都是已被固定的。（一格可以是自己的[[鄰居]]。）每次演進時，每格均遵從同一規矩一齊演進。

就形式而言，細胞自動機有三個特徵：

* 平行計算（parallel computation）：每一個細胞個體都同時同步的改變
* 局部的（local）：細胞的狀態變化只受周遭細胞的影響。
* 一致性的（homogeneous）：所有細胞均受同樣的規則所支配

==构成==
一个标准的細胞自動機（<math>A</math>）由元胞、元胞状态、邻域和状态更新规则构成。用数学表示为<ref>{{cite journal|author=S. Amoroso|coauthors=Y.N. Patt|title=Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures|journal=Journal of Computer and System Sciences|date=October 1972|volume=6|issue=5|pages=448-464|doi=10.1016/S0022-0000(72)80013-8|url=https://www.sciencedirect.com/science/article/pii/S0022000072800138?via%3Dihub|access-date=2022-05-06|archive-date=2022-05-06|archive-url=https://web.archive.org/web/20220506015054/https://www.sciencedirect.com/science/article/pii/S0022000072800138?via%3Dihub}}</ref>：
:<math>A = ( L, d, S, N, f)</math>
其中''L''为元胞空间；''d''为元胞自动机内元胞空间的维数；''S''是元胞有限的、离散的状态集合；''N''为某个[[邻域]]内所有元胞的集合；''f''为局部映射或局部规则。

元胞空间是元胞所分布的空间网点的集合。理论上元胞空间在各个维向上是无限延伸的，为了能够在计算机上实现，而定义了边界条件，包括周期型、反射型和定值型<ref>{{cite book|author= 周成虎|title=地理元胞自动机研究 |year=2000|publisher=科学出版社|isbn=9787030081209|pages=26-51|coauthors=孙战利 谢一春|location=北京}}</ref>。

一个元胞通常在一个时刻只有取自一个有限集合的一种状态，例如{0,1}。元胞状态可以代表个体的态度，特征，行为等<ref>{{cite book|author=宣慧玉|title=管理与社会经济系统仿真|year=2000|publisher=武汉大学出版社|isbn=9787307034075|coauthors=高宝俊|location=武汉|page=98-114}}</ref>。在空间上与元胞相邻的细胞称为邻元，所有邻元组成邻域。

==历史==
細胞自動機最早由美籍數學家[[冯·诺依曼]]（{{lang|en|John von Neumann}}）在1950年代为模拟生物细胞的自我复制而提出，但是并未受到学术界重视。直到1970年，英國數學家[[约翰·何顿·康威]]（John Horton Conway）设计了[[生命游戏]]並經[[馬丁·葛登]]在《[[科學美國人]]》雜誌上介紹，才吸引了科学家们的注意。此后，英國學者[[史蒂芬·沃爾夫勒姆]]（Stephen Wolfram）对初等元胞机256种规则所产生的模型进行了深入研究，并用[[熵]]來描述其演化行为，将細胞自動機分为平稳型、周期型、混沌型和复杂型<ref>{{cite journal|author=陈国宏|coauthors=蔡彬清,李美娟|title=元胞自动机：一种探索管理系统复杂性的有效工具|journal=中国工程科学|year=2007|volume=9|issue=1|pages=28~32|url=http://www.cqvip.com/qk/83379x/2007001/23690053.html}}</ref>。

==分类==
史蒂芬·沃爾夫勒姆在《[[一种新科学]]》和几篇从80年代中期开始的论文中定义了四类细胞自动机和其他几个简单的计算模型。元胞自动机的早期研究往往试图确定具体规则的模式类型，他提出的分类是对规则本身分类的第一次尝试。按照复杂性分类的秩序：
* 1类：几乎所有的初始模式迅速演变成一个稳定的，均匀的状态。在初始模式的任何随机性会消失。<ref name=ilachinski-12>{{Harvnb|Ilachinsky|2001|p=12|ref=ilachinski}}</ref>
* 2类：几乎所有的初始模式迅速演化为稳定或振荡结构。一些在初始模式的随机性可能会被过滤掉，但是还有一些保留。在初始模式的局部变化倾向于继续保持局部性。<ref name=ilachinski-12/>
* 3类：几乎所有的初始形态将会演变成一个伪随机或混沌的形式。任何稳定的结构很快会被周围的噪音破坏。在初始模式的局部变化有无限蔓延的倾向。<ref name=ilachinski-12/>
* 4类：几乎所有的初始模式将会演变成相互作用的复杂和有趣的方式结构，并且局部结构的形成能够长时间存在。<ref name=ilachinski-13>{{Harvnb|Ilachinsky|2001|p=13|ref=ilachinski}}</ref>2类的稳定或振荡的结构可能是最终的结果，但需要达到这个状态的步骤数目可能是非常大的，即使在初始模式比较简单的情况下。初始模式的局部变化可能会无限蔓延。[[史蒂芬·沃爾夫勒姆]]推测不是所有的4类细胞自动机都能够进行通用计算。这已經在规则110和[[约翰·何顿·康威]]的[[生命游戏]]中被證明。

根据史蒂芬·沃爾夫勒姆的說法，这些定义在本质上是定性的但是任有解释一些空间。“……几乎任何一般的分类方案都有不可避免的情况，比如说根据不同的定义会被分配到不同的类里。因此细胞自动机也是这样：偶尔有规则……显示不同类的一些特点。”<ref name=wolfram-231>{{Harvnb|Wolfram|2002|p=231|ref=wolfram}}</ref>他的分类已经与一个类具有压缩长度输出的元胞自动机相匹配。<ref>{{cite journal|last=Zenil|first=Hector|title=Compression-based investigation of the dynamical properties of cellular automata and other systems|journal=Complex Systems|year=2010|volume=19|issue=1|url=http://www.complex-systems.com/pdf/19-1-1.pdf|access-date=2013-12-03|archive-date=2017-08-09|archive-url=https://web.archive.org/web/20170809112524/http://www.complex-systems.com/pdf/19-1-1.pdf|dead-url=no}}</ref>

已经有人在尝试进行细胞自动机的正式严格分类根据史蒂芬·沃爾夫勒姆的分类。例如，Culik和Yu提出三种定义的类（并且第四个和它们不同），有时被称为Culik-Yu 类；能够被分到这种类里的问题被证明是不可判定的。<ref name="DelormeMazoyer1998">{{cite book|editor=M. Delorme, J. Mazoyer|title=Cellular automata: a parallel model|url=http://books.google.com/books?id=dGs87s5Pft0C&pg=PA239|year=1998|publisher=Springer|isbn=978-0-7923-5493-2|page=239|chapter=Topological chaos and CA|author=G. Cattaneo, E. Formenti, L. Margara|access-date=2013-12-03|archive-date=2021-04-14|archive-url=https://web.archive.org/web/20210414134152/https://books.google.com/books?id=dGs87s5Pft0C&pg=PA239|dead-url=no}}</ref><ref name="Voorhees1996">{{cite book|author=Burton H. Voorhees|title=Computational analysis of one-dimensional cellular automata|url=http://books.google.com/books?id=WcZTQHPrG68C&pg=PA8|year=1996|publisher=World Scientific|isbn=978-981-02-2221-5|page=8|access-date=2013-12-03|archive-date=2021-04-14|archive-url=https://web.archive.org/web/20210414134653/https://books.google.com/books?id=WcZTQHPrG68C&pg=PA8|dead-url=no}}</ref><ref name="Garzon1995">{{cite book|author=Max Garzon|title=Models of massive parallelism: analysis of cellular automata and neural networks |url=https://archive.org/details/modelsmassivepar00garz| year=1995 | publisher=Springer | isbn=978-3-540-56149-1 | page=[https://archive.org/details/modelsmassivepar00garz/page/n159 149]}}</ref>史蒂芬·沃爾夫勒姆的2类可划分为稳定（定点）和振荡（周期）规则两个小组。<ref name=li-packard>{{cite journal | url=http://www.complex-systems.com/pdf/04-3-3.pdf | author1=Li, Wentian | authorlink1=Wentian Li | author2=Packard, Norman | title=The structure of the elementary cellular automata rule space | journal=Complex Systems | pages=281–297 | volume=4 | year=1990 | accessdate=January 25, 2013 | archive-date=2016-06-25 | archive-url=https://web.archive.org/web/20160625222140/http://www.complex-systems.com/pdf/04-3-3.pdf | dead-url=no }}</ref>

== 參照 ==
* [[生命遊戲]]
* [[兰顿蚂蚁]]
* [[Wireworld]]
* [[格子气自动机]]

==参考文献==
<div class="references-small">
<references></references>
</div>

== 外部連結 ==
* [http://www.atlas-zone.com/complex/alife/ca/index.html 複雜性科學 - 複雜適應性系統 - 細胞自動機　Cellular Automata] {{Wayback|url=http://www.atlas-zone.com/complex/alife/ca/index.html |date=20200222234138 }}
* [https://web.archive.org/web/20071229092611/http://lab.geog.ntu.edu.tw/course/%E7%A9%BA%E9%96%93%E7%9F%A5%E8%AD%98%E7%AE%A1%E7%90%86/ch12.htm 第十二講 知識運作-細胞自動機(cellular automata; CA)（PPT網頁版）]

{{CPU technologies}}
{{Authority control}}

[[Category:細胞自動機| ]]
[[Category:动力系统]]
[[Category:系統理論]]
[[Category:计算领域研究]]