1,526
个编辑
更改
无编辑摘要
<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>
<br>对于一维元胞自动机，已知有一些可以确定规则是否可逆的算法。<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>
<br>对于一维元胞自动机，已知有一些可以确定规则是否可逆的算法。<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>
然而，对于二维及更高维元胞自动机，其可逆性是无法判定的；换言之，没有一种以自动机规则作为输入，并保证正确地判断自动机是否可逆的算法。[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>