更改

跳到导航 跳到搜索
删除1字节 、 2020年4月13日 (一) 10:52
无编辑摘要
第129行: 第129行:  
<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>
  
1,526

个编辑

导航菜单