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