更改

元胞自动机 (查看源代码)

2024年6月3日 (一) 14:31的版本

删除27字节、 2024年6月3日 (星期一)

无编辑摘要

第5行：第5行：

}}

−

'''元胞自动机 ~~cellular automata~~'''（CA），中文也译作细胞自动机、点格自动机、分子自动机或单元自动机，是一种时间、空间、状态都离散，空间相互作用和时间因果关系为局部的网格动力学模型，具有模拟复杂系统时空演化过程的能力。由冯·诺依曼创始，经数学家[[约翰·何顿·康威 John Horton Conway]]、物理学家[[斯蒂芬·沃尔夫勒姆 Stephen Wolfram]]等人的贡献后迅速发展。'''元胞自动机'''广泛应用于'''计算机科学'''、物理学、[[复杂系统 Complex Systems]]，理论生物学和微观结构模型等领域。元胞自动机同时也被称为元胞空间，棋盘自动机 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），中文也译作细胞自动机、点格自动机、分子自动机或单元自动机，是一种时间、空间、状态都离散，空间相互作用和时间因果关系为局部的网格动力学模型，具有模拟复杂系统时空演化过程的能力。由冯·诺依曼创始，经数学家[[约翰·何顿·康威 John Horton Conway]]、物理学家[[斯蒂芬·沃尔夫勒姆 Stephen Wolfram]]等人的贡献后迅速发展。'''元胞自动机'''广泛应用于'''计算机科学'''、物理学、[[复杂系统 Complex Systems]]，理论生物学和微观结构模型等领域。元胞自动机同时也被称为元胞空间，棋盘自动机 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|基于元胞自动机的三维展示]]

第17行：第17行：

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

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

−

模拟二维元胞自动机的一种方法是用一张无限大的方格纸，加上一套元胞规则来构成。每个正方形被称为“单元格” ，每个单元格有两种可能的状态，黑色和白色。单元格的邻域是指周围的单元格。最常见的两种邻域类型有[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(29)种可能的自动机模式。对于每一种模式，规则表将确定在下一个时间段中中心单元格是黑色还是白色。[[康威的生命游戏 Conway's Game of Life]]就是这种模式的一个流行版本。另一种常见的邻域类型是扩展的冯诺依曼邻域，它包括每个正交方向上最近的2个单元格，总共8个单元格。<ref name = " Kier "></ref>这种规则的一般方程是 kks，其中 k 是一个单元格可能状态的数目，s 是用来确定单元格下一个状态的相邻单元格的数目(包括要计算的单元格本身)。<ref >Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0198531005.

+

模拟二维元胞自动机的一种方法是用一张无限大的方格纸，加上一套元胞规则来构成。每个正方形被称为“单元格” ，每个单元格有两种可能的状态，黑色和白色。单元格的邻域是指周围的单元格。最常见的两种邻域类型有[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(29)种可能的自动机模式。对于每一种模式，规则表将确定在下一个时间段中中心单元格是黑色还是白色。[[康威的生命游戏 Conway's Game of Life]]就是这种模式的一个流行版本。另一种常见的邻域类型是扩展的冯诺依曼邻域，它包括每个正交方向上最近的2个单元格，总共8个单元格。<ref name = " Kier "></ref>这种规则的一般方程是 kks，其中 k 是一个单元格可能状态的数目，s 是用来确定单元格下一个状态的相邻单元格的数目(包括要计算的单元格本身)。<ref>Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0198531005.

</ref>

因此，在二维的摩尔邻域中，可能出现的自动机模式共有229个，即1.34*10154个。

第23行：第23行： −

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

+

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

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

第32行：第32行：

==研究历史==

−

20世纪40年代，乌拉姆在洛斯阿拉莫斯国家实验室工作时，以简单的晶格网络为模型，研究了晶体的生长。<ref name = " Pickover " >Pickover, Clifford A. (2009). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics. Sterling Publishing Company, Inc. p. 406. ISBN 978-1402757969.</ref>与此同时，乌拉姆在洛斯阿拉莫斯的同事[[约翰·冯·诺依曼 John von Neumann]]正在研究自复制系统的问题。他最初的设计是基于“一个机器制造另一个机器”的概念。这种设计被称为运动学模型。<ref name = " von Neumann " >John von Neumann, "The general and logical theory of automata," in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.</ref><ref name = " Kemeny " >Kemeny, John G. (1955). "Man viewed as a machine". Sci. Am. 192 (4): 58–67. Bibcode:1955SciAm.192d..58K. doi:10.1038/scientificamerican0455-58.; Sci. Am. 1955; 192:6 (errata)</ref>冯·诺依曼在开发这一设计时，逐渐意识到制造一个自我复制的机器人非常困难，并且需要花费巨大成本为机器人提供“一大堆零件”来制造复制品。冯·诺依曼在1948年的[https://en.wikipedia.org/wiki/Lloyd_A._Jeffress#The_Hixon_Symposium 希克森研讨会 Hixon Symposium]上写了一篇题为《The general and logical theory of automata》的论文。<ref name=" Schiff"></ref>乌拉姆建议使用离散系统来创建自我复制的还原论模型。<ref name=" Schiff"></ref><ref name = " Ilachinski " >Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific. ISBN 9789812381835.</ref>尼尔斯·阿尔·巴里切利对这些人工生命模型进行了许多早期的探索。

+

20世纪40年代，乌拉姆在洛斯阿拉莫斯国家实验室工作时，以简单的晶格网络为模型，研究了晶体的生长。<ref name="Pickover">Pickover, Clifford A. (2009). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics. Sterling Publishing Company, Inc. p. 406. ISBN 978-1402757969.</ref>与此同时，乌拉姆在洛斯阿拉莫斯的同事[[约翰·冯·诺依曼 John von Neumann]]正在研究自复制系统的问题。他最初的设计是基于“一个机器制造另一个机器”的概念。这种设计被称为运动学模型。<ref name = " von Neumann " >John von Neumann, "The general and logical theory of automata," in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.</ref><ref name = " Kemeny " >Kemeny, John G. (1955). "Man viewed as a machine". Sci. Am. 192 (4): 58–67. Bibcode:1955SciAm.192d..58K. doi:10.1038/scientificamerican0455-58.; Sci. Am. 1955; 192:6 (errata)</ref>冯·诺依曼在开发这一设计时，逐渐意识到制造一个自我复制的机器人非常困难，并且需要花费巨大成本为机器人提供“一大堆零件”来制造复制品。冯·诺依曼在1948年的[https://en.wikipedia.org/wiki/Lloyd_A._Jeffress#The_Hixon_Symposium 希克森研讨会 Hixon Symposium]上写了一篇题为《The general and logical theory of automata》的论文。<ref name=" Schiff"></ref>乌拉姆建议使用离散系统来创建自我复制的还原论模型。<ref name=" Schiff"></ref><ref name="Ilachinski">Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific. ISBN 9789812381835.</ref>尼尔斯·阿尔·巴里切利对这些人工生命模型进行了许多早期的探索。

−

乌拉姆和冯·诺依曼在20世纪50年代后期创造了一种计算流体运动的方法。该方法的驱动概念是将流体视为一组离散单元格，根据其相邻单元格的行为计算其运动。<ref name = " Ilachinski " ></ref> 因此诞生了第一个元胞自动机系统。与乌拉姆的晶格网络一样，冯·诺依曼的[[元胞自动机 Cellular Automata]]是二维的，其自复制器通过算法实现。这样的设计使得一个通用复制和构造器在具有很小邻域的元胞自动机内工作(只有那些接触的单元格是邻域；对于冯·诺依曼的元胞自动机而言，只有正交的单元格是邻域)，其中，每个单元格有29个状态。<ref name = "Wolfram2" >Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080.</ref>冯·诺依曼通过设计一个20万个元胞的结构，证明了在特定的模式下，单元格可以在给定的网格中无止境地自我复制。这种设计被称为棋盘模型，也被称为冯·诺依曼通用构造器。<ref name = " von Neumann2 " >von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press.</ref>

+

乌拉姆和冯·诺依曼在20世纪50年代后期创造了一种计算流体运动的方法。该方法的驱动概念是将流体视为一组离散单元格，根据其相邻单元格的行为计算其运动。<ref name = " Ilachinski " ></ref> 因此诞生了第一个元胞自动机系统。与乌拉姆的晶格网络一样，冯·诺依曼的[[元胞自动机 Cellular Automata]]是二维的，其自复制器通过算法实现。这样的设计使得一个通用复制和构造器在具有很小邻域的元胞自动机内工作(只有那些接触的单元格是邻域；对于冯·诺依曼的元胞自动机而言，只有正交的单元格是邻域)，其中，每个单元格有29个状态。<ref name="Wolfram2">Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080.</ref>冯·诺依曼通过设计一个20万个元胞的结构，证明了在特定的模式下，单元格可以在给定的网格中无止境地自我复制。这种设计被称为棋盘模型，也被称为冯·诺依曼通用构造器。<ref name = " von Neumann2 " >von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press.</ref>

第115行：第115行：

这些定义本质上是定性的，有一定解释空间。根据沃尔弗拉姆的说法：“...几乎所有的通用分类方案都是一种定义对应一个类别。元胞自动机的分类也是如此: 偶尔会有一些规则来展示出一个类的某些特征和另一个类的某些特征。”<ref name = "Wolfram2" ></ref>沃尔弗拉姆的分类是已根据经验与元胞自动机输出压缩长度的聚类相匹配而得出的。<ref name = " Zenil" >{{ Cite journal|title=Compression-based investigation of the dynamical properties of cellular automata and other systems|author1= Zenil, Hector | journal=Complex Systems|date=2010|volume=19|issue=1|url=http://www.complex-systems.com/pdf/19-1-1.pdf}} </ref>

−

受沃尔弗拉姆分类法的启发，人们已多次尝试将元胞自动机以严格的形式分类。例如，Culik 和 Yu 提出了三个具有明确定义的类(没有一种对应自动机的第四类)，这些类有时被称为 Culik-Yu 类; 这些类之间的关系已被证明是[https://en.wikipedia.org/wiki/Undecidable_problem 难以确定的]。<ref name=" G. Cattaneo "> G. Cattaneo; E. Formenti; L. Margara (1998). "Topological chaos and CA". In M. Delorme; J. Mazoyer (eds.). Cellular automata: a parallel model. Springer. p. 239. ISBN 978-0-7923-5493-2.</ref><ref>{{cite book

+

受沃尔弗拉姆分类法的启发，人们已多次尝试将元胞自动机以严格的形式分类。例如，Culik 和 Yu 提出了三个具有明确定义的类(没有一种对应自动机的第四类)，这些类有时被称为 Culik-Yu 类; 这些类之间的关系已被证明是[https://en.wikipedia.org/wiki/Undecidable_problem 难以确定的]。<ref name="G. Cattaneo"> G. Cattaneo; E. Formenti; L. Margara (1998). "Topological chaos and CA". In M. Delorme; J. Mazoyer (eds.). Cellular automata: a parallel model. Springer. p. 239. ISBN 978-0-7923-5493-2.</ref><ref>{{cite book

|author= Burton H. Voorhees

|title=Computational analysis of one-dimensional cellular automata.

第122行：第122行：

|pages=8

|year=1996}}</ref>

−

<ref name=" Max "> Max Garzon (1995). Models of massive parallelism: analysis of cellular automata and neural networks. Springer. p. 149. ISBN 978-3-540-56149-1.</ref> 沃尔弗拉姆的第2类可以划分为稳定(不动点)和具有振荡(周期)规则的两个子类。<ref name = " Wentian " >{{ Cite journal|title=The structure of the elementary cellular automata rule space|author1= Li, Wentian|author2= Packard, Norman | journal=Complex Systems|date=1990|volume=4| pages= 281–297|url=http://www.complex-systems.com/pdf/04-3-3.pdf}} </ref>

+

<ref name="Max"> Max Garzon (1995). Models of massive parallelism: analysis of cellular automata and neural networks. Springer. p. 149. ISBN 978-3-540-56149-1.</ref> 沃尔弗拉姆的第2类可以划分为稳定(不动点)和具有振荡(周期)规则的两个子类。<ref name = " Wentian " >{{ Cite journal|title=The structure of the elementary cellular automata rule space|author1= Li, Wentian|author2= Packard, Norman | journal=Complex Systems|date=1990|volume=4| pages= 281–297|url=http://www.complex-systems.com/pdf/04-3-3.pdf}} </ref>

划分4类动力系统的想法最初来自诺贝尔化学奖获得者[https://en.wikipedia.org/wiki/Ilya_Prigogine 伊利亚·普里高津 Ilya Prigogine]，他确定了热力学系统可划分为四类: (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>

第129行：第129行：

=== 可逆的 ===

'''主条目：[https://en.wikipedia.org/wiki/Reversible_cellular_automaton 可逆元胞自动机]'''

−

如果对于元胞自动机的每个当前结构，恰好有一个过去的结构([https://en.wikipedia.org/wiki/Image_(mathematics)#Inverse_image 原像])，则元胞自动机是可逆的。<ref name=" Gutowitz "> Gutowitz, Howard, ed. (1991). Cellular Automata: Theory and Experiment. MIT Press. ISBN 9780262570862.</ref>如果我们把元胞自动机看作是从结构映射到结构的函数，那么可逆性就意味着这个函数是[https://en.wikipedia.org/wiki/Bijection 双射]的。<ref name=" Gutowitz "></ref>如果元胞自动机是可逆的，那么其时间逆转行为也可以被描述为元胞自动机; 这个事实是[https://en.wikipedia.org/wiki/Curtis%E2%80%93Hedlund%E2%80%93Lyndon_theorem Curtis-Hedlund-Lyndon定理]的结果，该定理是元胞自动机的拓扑特征。<ref name=" Richardson "> Richardson, D. (1972). "Tessellations with local transformations". J. Computer System Sci. 6 (5): 373–388. doi:10.1016/S0022-0000(72)80009-6.</ref><ref name=" Margenstern "> Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces – Tome I, Volume 1. Archives contemporaines. p. 134. ISBN 978-2-84703-033-4.</ref>对于不是每个结构都有预映像的元胞自动机，这些没有预映像的结构称为[https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) 初始]模式。<ref name = " Schiff " ></ref>

+

如果对于元胞自动机的每个当前结构，恰好有一个过去的结构([https://en.wikipedia.org/wiki/Image_(mathematics)#Inverse_image 原像])，则元胞自动机是可逆的。<ref name="Gutowitz"> Gutowitz, Howard, ed. (1991). Cellular Automata: Theory and Experiment. MIT Press. ISBN 9780262570862.</ref>如果我们把元胞自动机看作是从结构映射到结构的函数，那么可逆性就意味着这个函数是[https://en.wikipedia.org/wiki/Bijection 双射]的。<ref name=" Gutowitz "></ref>如果元胞自动机是可逆的，那么其时间逆转行为也可以被描述为元胞自动机; 这个事实是[https://en.wikipedia.org/wiki/Curtis%E2%80%93Hedlund%E2%80%93Lyndon_theorem Curtis-Hedlund-Lyndon定理]的结果，该定理是元胞自动机的拓扑特征。<ref name=" Richardson "> Richardson, D. (1972). "Tessellations with local transformations". J. Computer System Sci. 6 (5): 373–388. doi:10.1016/S0022-0000(72)80009-6.</ref><ref name="Margenstern"> Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces – Tome I, Volume 1. Archives contemporaines. p. 134. ISBN 978-2-84703-033-4.</ref>对于不是每个结构都有预映像的元胞自动机，这些没有预映像的结构称为[https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) 初始]模式。<ref name = " Schiff " ></ref>

对于一维元胞自动机，已知有一些可以确定规则是否可逆的算法。<ref name=" Amoroso "> Amoroso, Serafino; Patt, Yale N. (1972). "Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures". J. Comput. Syst. Sci. 6 (5): 448–464. doi:10.1016/s0022-0000(72)80013-8.</ref><ref name = " Sutner " >{{Cite journal |title= De Bruijn Graphs and Linear Cellular Automata |author1= Sutner, Klaus |journal= Complex Systems |date=1991|volume=5|pages= 19-30| url=http://wpmedia.wolfram.com/uploads/sites/13/2018/02/05-1-3.pdf}} </ref>

第176行：第176行：

元胞以相邻的8个元胞为邻居。即Moore邻居；一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态所决定。

−

最简单的元胞自动机是一维的，每个单元格具有两种状态，并且单元格的邻域定义为在其任一侧的相邻单元格。一个单元格及其两个相邻单元格形成一个3个单元格的邻域，因此邻域有23 = 8个可能的模式。规则包括为每种模式确定单元格在下一代中是1还是0。然后有28 = 256个可能的规则。 <ref name=" Bialynicki ">Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0198531005.

+

最简单的元胞自动机是一维的，每个单元格具有两种状态，并且单元格的邻域定义为在其任一侧的相邻单元格。一个单元格及其两个相邻单元格形成一个3个单元格的邻域，因此邻域有23 = 8个可能的模式。规则包括为每种模式确定单元格在下一代中是1还是0。然后有28 = 256个可能的规则。 <ref name="Bialynicki">Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0198531005.

</ref>

13944556914

88

个编辑