1,526
个编辑
更改
跳到导航
跳到搜索
第125行：
第125行： − + 第131行：
第131行： − +
→可逆的
=== 可逆的 ===
=== 可逆的 ===
''主条目：[https://en.wikipedia.org/wiki/Reversible_cellular_automaton 可逆元胞自动机]''
'''主条目：[https://en.wikipedia.org/wiki/Reversible_cellular_automaton 可逆元胞自动机]'''
<br>如果对于元胞自动机的每个当前结构，恰好有一个过去的结构([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>
<br>如果对于元胞自动机的每个当前结构，恰好有一个过去的结构([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/Jarkko_Kari 贾科·卡里 Jarkko Kari]的证明与[https://en.wikipedia.org/wiki/Wang_tile 王浩平铺]的拼贴问题有关。<ref name=" Kari "> Kari, Jarkko (1990). "Reversibility of 2D cellular automata is undecidable". Physica D. 45 (1–3): 379–385. Bibcode:1990PhyD...45..379K. doi:10.1016/0167-2789(90)90195-U.</ref>
然而，对于二维及更高维元胞自动机，其可逆性是无法判定的；换言之，没有一种以自动机规则作为输入，并保证正确地判断自动机是否可逆的算法。[https://en.wikipedia.org/wiki/Jarkko_Kari 贾科·卡里 Jarkko Kari]的证明与[https://en.wikipedia.org/wiki/Wang_tile 王浩平铺]的拼贴问题有关。<ref name=" Kari "> Kari, Jarkko (1990). "Reversibility of 2D cellular automata is undecidable". Physica D. 45 (1–3): 379–385. Bibcode:1990PhyD...45..379K. doi:10.1016/0167-2789(90)90195-U.</ref>
<br>由于可逆的元胞自动机遵循[https://en.wikipedia.org/wiki/Thermodynamics 热力学]定律原理，因此可用于模拟诸如气体和流体动力学等物理现象。这种元胞自动机具有专门构造的可逆规则。[https://en.wikipedia.org/wiki/Tommaso_Toffoli 托玛索·托佛利 Tommaso Toffoli]，[https://en.wikipedia.org/wiki/Norman_Margolus 诺曼·马戈卢斯 Norman Margolus]等人已经研究过这样的系统。有几种技术可以用来准确地构造具有已知的可逆元胞自动机。 常见的有[https://en.wikipedia.org/wiki/Second-order_cellular_automaton 二阶元胞自动机]和[https://en.wikipedia.org/wiki/Block_cellular_automaton 分区元胞自动机]，两者都是以某种方式修改元胞自动机的定义。虽然这种自动机并不严格满足上面给出的定义，但是它们可以由拥有足够大的邻域和状态数的传统元胞自动机来模拟，因此它们可以被认为是常规元胞自动机的子集。它们还证明了每一个可逆的元胞自动机都可以被一个分区元胞自动机模拟。<ref name=" Kari2 "> Kari, Jarkko (1999). "On the circuit depth of structurally reversible cellular automata". Fundamenta Informaticae. 38: 93–107.</ref><ref name=" Durand-Lose ">Durand-Lose, Jérôme (2001). "Representing reversible cellular automata with reversible block cellular automata". Discrete Mathematics and Theoretical Computer Science. AA: 145–154. Archived from the original on 15 May 2011.</ref>
<br>由于可逆的元胞自动机遵循[https://en.wikipedia.org/wiki/Thermodynamics 热力学]原理，因此可用于模拟诸如气体和流体动力学等物理现象。这种元胞自动机具有专门构造的可逆规则。[https://en.wikipedia.org/wiki/Tommaso_Toffoli 托玛索·托佛利 Tommaso Toffoli]，[https://en.wikipedia.org/wiki/Norman_Margolus 诺曼·马戈卢斯 Norman Margolus]等人已经研究过这样的系统。有几种技术可以用来准确地构造具有已知的可逆元胞自动机。 常见的有[https://en.wikipedia.org/wiki/Second-order_cellular_automaton 二阶元胞自动机]和[https://en.wikipedia.org/wiki/Block_cellular_automaton 分区元胞自动机]，两者都是以某种方式修改元胞自动机的定义。虽然这种自动机并不严格满足上面给出的定义，但是它们可以由拥有足够大的邻域和状态数的传统元胞自动机来模拟，因此它们可以被认为是常规元胞自动机的子集。它们还证明了每一个可逆的元胞自动机都可以被一个分区元胞自动机模拟。<ref name=" Kari2 "> Kari, Jarkko (1999). "On the circuit depth of structurally reversible cellular automata". Fundamenta Informaticae. 38: 93–107.</ref><ref name=" Durand-Lose ">Durand-Lose, Jérôme (2001). "Representing reversible cellular automata with reversible block cellular automata". Discrete Mathematics and Theoretical Computer Science. AA: 145–154. Archived from the original on 15 May 2011.</ref>
=== 完全的 ===
=== 完全的 ===