更改

==研究历史==

==研究历史==

<br>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>与此同时，乌拉姆在洛斯阿拉莫斯的同事[[冯·诺依曼]]正在研究自复制系统的问题。他最初的设计是基于一个机器制造另一个机器的概念。这种设计被称为运动学模型。<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>尼尔斯·阿尔·巴里切利对这些人工生命模型进行了许多早期的探索。

<br>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>与此同时，乌拉姆在洛斯阿拉莫斯的同事[[冯·诺依曼]]正在研究自复制系统的问题。他最初的设计是基于“一个机器制造另一个机器”的概念。这种设计被称为运动学模型。<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>尼尔斯·阿尔·巴里切利对这些人工生命模型进行了许多早期的探索。

<br>乌拉姆和冯·诺依曼在20世纪50年代后期创造了一种计算流体运动的方法。该方法的驱动概念是将流体视为一组离散单元格，根据其相邻单元格的行为计算其运动。<ref name = " Ilachinski " ></ref> 因此诞生了第一个元胞自动机系统。 与乌拉姆的晶格网络一样，冯·诺依曼的[[元胞自动机]]是二维的，其自复制器通过算法实现。这样设计的结果是一个通用复制和构造器在具有很小邻域的元胞自动机内工作(只有那些接触的单元格是邻域；对于冯·诺依曼的元胞自动机而言，只有正交的单元格是邻域)，其中，每个单元格有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>

<br>乌拉姆和冯·诺依曼在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>

[[File:John von Neumann ID badge.png|200px|thumb|left|冯·诺依曼在实验室的身份证照片]]

[[File:John von Neumann ID badge.png|200px|thumb|left|冯·诺依曼在实验室的身份证照片]]

<br>同样在20世纪40年代，[[诺伯特·维纳]]和阿图罗·罗森布鲁斯开发了一种具有元胞自动机特征的可激发介质模型。<ref name = " Wiener " >Wiener, N.; Rosenblueth, A. (1946). "The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle". Arch. Inst. Cardiol. México. 16: 205.</ref>它用于心脏系统脉冲传导的数学描述。 然而该模型并不属于元胞自动机，因为信号传播的介质是连续的，波前是曲线。<ref name = " Wiener " ></ref><ref name = " Letichevskii " >Letichevskii, A. A.; Reshodko, L. V. (1974). "N. Wiener's theory of the activity of excitable media". Cybernetics. 8 (5): 856–864. doi:10.1007/bf01068458.</ref>1978年，J.m. Greenberg和S. P. Hastings发展并研究出了一个真正的种可激发介质的元胞自动机，请参阅元胞自动机。维纳和罗森布鲁斯的原始著作中包含了许多见解，在现代关于心律失常和兴奋系统的研究出版物中仍被经常引用。<ref name = " Davidenko " >Davidenko, J. M.; Pertsov, A. V.; Salomonsz, R.; Baxter, W.; Jalife, J. (1992). "Stationary and drifting spiral waves of excitation in isolated cardiac muscle". Nature. 355 (6358): 349–351. Bibcode:1992Natur.355..349D. doi:10.1038/355349a0. PMID 1731248.</ref>

<br>同样在20世纪40年代，诺伯特·维纳和阿图罗·罗森布鲁斯开发了一种具有元胞自动机特征的可激发介质模型。<ref name = " Wiener " >Wiener, N.; Rosenblueth, A. (1946). "The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle". Arch. Inst. Cardiol. México. 16: 205.</ref>它用于心脏系统脉冲传导的数学描述。 然而该模型并不属于元胞自动机，因为信号传播的介质是连续的，波前是曲线。<ref name = " Wiener " ></ref><ref name = " Letichevskii " >Letichevskii, A. A.; Reshodko, L. V. (1974). "N. Wiener's theory of the activity of excitable media". Cybernetics. 8 (5): 856–864. doi:10.1007/bf01068458.</ref>1978年，J.m. Greenberg和S. P. Hastings发展并研究出了一个真正的种可激发介质的元胞自动机。维纳和罗森布鲁斯的原始著作中包含了许多见解，在现代关于心律失常和兴奋系统的研究出版物中仍经常被引用。<ref name = " Davidenko " >Davidenko, J. M.; Pertsov, A. V.; Salomonsz, R.; Baxter, W.; Jalife, J. (1992). "Stationary and drifting spiral waves of excitation in isolated cardiac muscle". Nature. 355 (6358): 349–351. Bibcode:1992Natur.355..349D. doi:10.1038/355349a0. PMID 1731248.</ref>

<br>到20世纪50年代末，人们已经注意到，元胞自动机可以被视为并行计算机，特别是在20世纪60年代，一系列形式越来越详细和技术性的定理（通常类似于图灵机的定理）被证明具有形式化的计算能力。<ref name = "Wolfram2" ></ref>

<br>到20世纪50年代末，人们已经注意到，元胞自动机可视为并行计算机，特别是在20世纪60年代，一系列形式越来越详细和技术性的定理（通常类似于图灵机的定理）被证明具有形式化的计算能力。<ref name = "Wolfram2" ></ref>

<br>20世纪60年代，人们将元胞自动机作为[[动力系统]]的一种特殊类型进行了研究，首次建立了其与符号动力学中的数学领域的联系。1969年， Gustav Arnold Hedlund根据这一观点<ref name = " Hedlund " >Hedlund, G. A. (1969). "Endomorphisms and automorphisms of the shift dynamical system". Math. Systems Theory. 3 (4): 320–3751. doi:10.1007/BF01691062.</ref>在论文中汇编了许多结果，至今该论文仍被认为是元胞自动机数学研究的开创性论文。最基本的结果是在Curtis-Hedlund-Lyndon 定理中将元胞自动机的全局规则集描述为移位空间]的连续自同态集。

<br>20世纪60年代，人们将元胞自动机作为'''动力系统'''的一种特殊类型进行了研究，首次建立了其与符号动力学中的数学领域的联系。1969年， Gustav Arnold Hedlund根据这一观点<ref name = " Hedlund " >Hedlund, G. A. (1969). "Endomorphisms and automorphisms of the shift dynamical system". Math. Systems Theory. 3 (4): 320–3751. doi:10.1007/BF01691062.</ref>在论文中汇编了许多结果，至今该论文仍被认为是元胞自动机数学研究的开创性论文。最基本的结果是在Curtis-Hedlund-Lyndon 定理中将元胞自动机的全局规则集描述为移位空间的连续自同态集。

<br>1969年，德国计算机先驱康拉德·楚泽 Konrad Zuse出版了《Calculating Space》，提出宇宙的物理定律本质上是离散的，整个宇宙是在一个元胞自动机的确定性计算的输出。 楚泽理论成为 数字物理学研究领域的基础。<ref name=" Schiff"></ref>

<br>1969年，德国计算机先驱康拉德·楚泽 Konrad Zuse出版了《Calculating Space》，提出宇宙的物理定律本质上是离散的，整个宇宙是在一个元胞自动机的确定性计算的输出。 '''楚泽理论'''成为数字物理学研究领域的基础。<ref name=" Schiff"></ref>

<br>也是在1969年，计算机科学家埃尔维·雷·史密斯Alvy Ray Smith完成了斯坦福大学关于元胞自动机理论的博士论文。许多论文都出自这篇论文: 他展示了各种形状邻域的等价性，如何把摩尔邻域归结为冯诺依曼邻域，或者如何把任何邻域归结为冯诺依曼邻域。<ref name = "Smith2" >{{Cite journal |title=Cellular Automata Complexity Trade-Offs |author=Smith, Alvy Ray |url= http://alvyray.com/Papers/CA/TradeOff.pdf }} </ref>

<br>也是在1969年，计算机科学家埃尔维·雷·史密斯 Alvy Ray Smith完成了斯坦福大学关于元胞自动机理论的博士论文。许多论文都出自这篇论文: 他展示了各种形状邻域的等价性，如何把摩尔邻域归结为冯诺依曼邻域，或者如何把任何邻域归结为冯诺依曼邻域。<ref name = "Smith2" >{{Cite journal |title=Cellular Automata Complexity Trade-Offs |author=Smith, Alvy Ray |url= http://alvyray.com/Papers/CA/TradeOff.pdf }} </ref>

他证明了二维元胞自动机具有计算通用性，通过引入一维元胞自动机，表明即使在简单的邻域内二维元胞自动机同样具有计算通用性，也是如此。<ref name = "Smith3" >{{Cite journal |title=Simple Computation-Universal Cellular Spaces |author=Smith, Alvy Ray |

他证明了二维元胞自动机具有计算通用性，通过引入一维元胞自动机，表明即使在简单的邻域内二维元胞自动机同样具有计算通用性，也是如此。<ref name = "Smith3" >{{Cite journal |title=Simple Computation-Universal Cellular Spaces |author=Smith, Alvy Ray |

url= http://alvyray.com/Papers/CA/UniversalCA_1D.pdf }} </ref>

url= http://alvyray.com/Papers/CA/UniversalCA_1D.pdf }} </ref>

他展示了如何将复杂的冯诺依曼结构普遍性证明(以及由此产生的自复制机器)纳入到一维元胞自动机计算普遍性的结果中。<ref name = "Smith4" >{{Cite journal |title=Simple Nontrivial Self-Reproducing Machines |author=Smith, Alvy Ray |url= http://alvyray.com/Papers/CA/alife2_optimized.pdf }} </ref>

他展示了如何将复杂的冯诺依曼结构普遍性证明(以及由此产生的自复制机器)纳入到一维元胞自动机计算普遍性的结果中。<ref name = "Smith4" >{{Cite journal |title=Simple Nontrivial Self-Reproducing Machines |author=Smith, Alvy Ray |url= http://alvyray.com/Papers/CA/alife2_optimized.pdf }} </ref>

作为冯·诺依曼关于元胞自动机的书的德文版介绍，他撰写了一份该领域的调查报告，其中引用了几十篇参考文献，这些文献是多个国家的多个作者在过去十年左右时间的研究成果，常常被现代元胞自动机研究者所忽视。<ref name = "Smith5" >{{Cite journal |title=Introduction to and Survey of Cellular Automata or Polyautomata Theory|author=Smith, Alvy Ray |url= http://alvyray.com/Papers/CA/PolyCA76.pdf }} </ref>

作为冯·诺依曼关于元胞自动机书的德文版介绍，他撰写了一份该领域的调查报告，其中引用了几十篇参考文献，这些文献是多个国家的多个作者在过去十年左右时间的研究成果，常常被现代元胞自动机研究者所忽视。<ref name = "Smith5" >{{Cite journal |title=Introduction to and Survey of Cellular Automata or Polyautomata Theory|author=Smith, Alvy Ray |url= http://alvyray.com/Papers/CA/PolyCA76.pdf }} </ref>

<br>在20世纪70年代，一种名为[[生命游戏]]的两态、二维元胞自动机广为人知，尤其是在早期的计算机界。该元胞自动机是[[约翰·何顿·康威 John Horton Conway]]发明的，马丁·加德纳 Martin Gardner在《Scientific American》的一篇文章中推广<ref name=" Gardner ">

<br>在20世纪70年代，一种名为[[康威的生命游戏 Conway's Game of Life]]的两态、二维元胞自动机广为人知，尤其是在早期的计算机界。该元胞自动机是[[约翰·何顿·康威 John Horton Conway]]发明的，马丁·加德纳 Martin Gardner在《Scientific American》的一篇文章中推广<ref name=" Gardner ">

{{Cite journal

{{Cite journal

|last= Gardner

|last= Gardner

<br>尽管简单，该系统实现了令人印象深刻的多样性行为，在表观随机性和顺序之间波动。 生命游戏最明显的特征之一就是“滑翔机”的频繁出现，滑翔机的排列实质上是使自己在网格上移动。也可以安排自动机使滑翔机相互作用来执行计算。经过大量的努力，已经证明生命游戏可以模仿通用图灵机。<ref name = "Paul" >{{Cite journal|author1=Paul Chapman | journal=Life universal computer|date=2002|title="Life Universal Computer"|url= http://www.igblan.free-online.co.uk/igblan/ca/}} </ref>

<br>尽管简单，该系统实现了令人印象深刻的多样性行为，在表观随机性和顺序之间波动。 生命游戏最明显的特征之一就是“滑翔机”的频繁出现，滑翔机的排列实质上是使自己在网格上移动。也可以安排自动机使滑翔机相互作用来执行计算。经过大量的努力，已经证明生命游戏可以模仿通用图灵机。<ref name = "Paul" >{{Cite journal|author1=Paul Chapman | journal=Life universal computer|date=2002|title="Life Universal Computer"|url= http://www.igblan.free-online.co.uk/igblan/ca/}} </ref>

<br>[[史蒂芬·沃尔弗拉姆 Stephen Wolfram]]在考虑了自然界中如何形成违反[https://en.wikipedia.org/wiki/Second_law_of_thermodynamics 热力学第二定律]的复杂模式后，于1981年中开始独立从事元胞自动机的研究。<ref name = "Wolfram2" ></ref>他的研究源于对[https://en.wikipedia.org/wiki/Neural_network 神经网络]等建模系统的兴趣。<ref name = "Wolfram2" ></ref>1983年6月，他在[https://en.wikipedia.org/wiki/Reviews_of_Modern_Physics 《Reviews of Modern Physics》]上发表了他的第一篇论文，研究了[https://en.wikipedia.org/wiki/Elementary_cellular_automaton 初等元胞自动机](特别是[https://en.wikipedia.org/wiki/Rule_30 第30条规则])。<ref name=" Wolfram"></ref><ref name = "Wolfram2" ></ref>这些简单规则行为的意想不到的复杂性使得沃尔弗拉姆怀疑自然界的复杂性可能是由于类似的机制造成的。<ref name = "Wolfram2" ></ref>然而，他的研究使他认识到元胞自动机在模拟神经网络方面的效果很差。此外，Wolfram还阐述了内在随机性和计算不可约性的概念，<ref name = "Wolfram2" ></ref>并提出[https://en.wikipedia.org/wiki/Rule_110 第110条规则]，这条规则可能是通用的——在20世纪90年代，Wolfram的研究助手[https://en.wikipedia.org/wiki/Matthew_Cook 马修·库克 Matthew Cook]证明了这一事实。<ref name=" Mitchell, "> Mitchell, Melanie (4 October 2002). "Is the Universe a Universal Computer?". Science. 298 (5591): 65–68. doi:10.1126/science.1075073.</ref>

<br>[[斯蒂芬·沃尔夫勒姆 Stephen Wolfram]]在考虑了自然界中如何形成违反[https://en.wikipedia.org/wiki/Second_law_of_thermodynamics 热力学第二定律]的复杂模式后，于1981年中开始独立从事元胞自动机的研究。<ref name = "Wolfram2" ></ref>他的研究源于对[https://en.wikipedia.org/wiki/Neural_network 神经网络]等建模系统的兴趣。<ref name = "Wolfram2" ></ref>1983年6月，他在[https://en.wikipedia.org/wiki/Reviews_of_Modern_Physics 《Reviews of Modern Physics》]上发表了他的第一篇论文，研究了[https://en.wikipedia.org/wiki/Elementary_cellular_automaton 初等元胞自动机](特别是[https://en.wikipedia.org/wiki/Rule_30 第30条规则])。<ref name=" Wolfram"></ref><ref name = "Wolfram2" ></ref>这些简单规则行为的意想不到的复杂性使得沃尔弗拉姆怀疑自然界的复杂性可能是由于类似的机制造成的。<ref name = "Wolfram2" ></ref>然而，他的研究使他认识到元胞自动机在模拟神经网络方面的效果很差。此外，Wolfram还阐述了内在随机性和计算不可约性的概念，<ref name = "Wolfram2" ></ref>并提出[https://en.wikipedia.org/wiki/Rule_110 第110条规则]，这条规则可能是通用的——在20世纪90年代，Wolfram的研究助手[https://en.wikipedia.org/wiki/Matthew_Cook 马修·库克 Matthew Cook]证明了这一事实。<ref name=" Mitchell, "> Mitchell, Melanie (4 October 2002). "Is the Universe a Universal Computer?". Science. 298 (5591): 65–68. doi:10.1126/science.1075073.</ref>

<br>2002年，Wolfram发表了一篇1280页的文章《[[a New Kind of Science]]》 其中详细论述了关于元胞自动机的发现不是孤立的事实，而是可靠的，并且对所有科学学科都有重要意义。<ref name = "Wolfram2" ></ref>尽管出版很混乱<ref name = " Johnson " >{{ Cite journal|

<br>2002年，Wolfram发表了一篇1280页的文章《[[一种新科学 a New Kind of Science]]》 其中详细论述了关于元胞自动机的发现不是孤立的事实，而是相互依靠的，并且对所有科学学科都有重要意义。<ref name = "Wolfram2" ></ref>尽管书中的内容很混乱<ref name = " Johnson " >{{ Cite journal|

title="'A New Kind of Science': You Know That Space-Time Thing? Never Mind

title="'A New Kind of Science': You Know That Space-Time Thing? Never Mind

|author1= Johnson, George | journal=The New York Times|date=2002|

|author1= Johnson, George | journal=The New York Times|date=2002|

url=https://www.nytimes.com/2002/06/09/books/review/09JOHNSOT.html}} </ref>

url=https://www.nytimes.com/2002/06/09/books/review/09JOHNSOT.html}} </ref>

<ref name = " Economist " >{{ Cite journal|title= The Science of Everything|journal= The Economist|date=2002|url=http://www.economist.com/printedition/displayStory.cfm?Story_ID=1154164}} </ref>但该书并未对基于元胞自动机的物理学基本理论进行论证，尽管它描述了一些基于元胞自动机的具体物理模型，它也提供了基于性质不同而形成的抽象系统模型。<ref name = "Wolfram2" ></ref>

<ref name = " Economist " >{{ Cite journal|title= The Science of Everything|journal= The Economist|date=2002|url=http://www.economist.com/printedition/displayStory.cfm?Story_ID=1154164}} </ref>但它描述了一些基于元胞自动机的具体物理模型，它也提供了基于性质不同而形成的抽象系统模型。<ref name = "Wolfram2" ></ref> 而且该书并未对基于元胞自动机的物理学基本理论进行论证。

==分类==

==分类==