一维周期边界可逆元胞自动机研究

理论计算机科学电子笔记252（2009）205-227www.elsevier.com/locate/entcs一维周期边界可逆元胞自动机Sukanta Das1孟加拉工程和科学大学信息技术系，希布普尔印度西孟加拉邦豪拉，邮编711103比普拉湾Sikdar2孟加拉工程与科学大学计算机科学技术系摘要本文研究了一维三邻域周期边界元胞自动机（CA）的特征。它的目标是表征CA规则，以有效地合成可逆CA。可达树的概念，因为它已经在[5，6，7]中提出，被重新定义为分类CA规则，可以形成一个可逆CA这样的分类也使得能够在线性时间中合成可逆的周期性边界CA关键词：非均匀细胞自动机，可逆CA，可达树，周期边界，规则类。1引言自诞生以来，元胞自动机（CA）的同构结构一直用于建模物理系统。CA结构在20世纪80年代显著简化[16]。为了有效地分析CA状态空间，提出了CA的一维结构，每个胞元具有两个状态（0/1）。CA细胞的均匀3-邻域（自身、左邻居和右邻居）依赖性引入了结构模块性。然而，已经表明[17]，1维3邻域CA表现出优异的1电子邮件：sukanta@it.becs.ac.in2电子邮件：biplab@cs.becs.ac.in3这项研究工作得到了赞助的元胞自动机研究项目的支持，孟加拉工程和科学大学，Shibpur，印度-711103。1571-0661 © 2009 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2009.09.022206S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205我在对物理系统进行建模时，很难看到动态系统中相互作用的对象在其演化过程中遵循相同的局部规则（同质性）为了模拟各种各样的物理系统，非齐次CA结构（也称为混合/非均匀CA）作为一种替代方案。自20世纪80年代以来，许多研究人员将注意力集中在混合CA上[3，4，8 特别是在VLSI领域[4]，一维混合元胞自动机得到了广泛的应用。 混合元胞自动机的详细特性及其在VLSI领域的应用[2，8]已在[4]中报道。尽管可逆性CA的变化范围很广，但它仍是CA研究的主要焦点。可逆元胞自动机的有趣性质吸引了研究人员长期以来在流体力学、动力系统、热传导、波散射、成核、枝晶生长、物理系统建模等方面的大量应用。[14 ]第10段。文献[9，10]研究了可逆元胞自动机的动力学性质对于超大规模集成电路应用，可逆线性/加法CA结构也已开发[4]。CA状态的可逆性问题在[1，13]中得到了解决。 在这项工作中，我们提出了一种替代方法来表征可逆CA。所提出的表征有利于这类CA的有效分析和合成。256个3邻域CA规则的集合基于其形成可逆CA的潜力进行分类。这有效地使得能够在线性时间内合成这样的CA本文的结构如下。以下部分提供了元胞自动机的基本概念。第三节介绍了可达树的概念。第4节识别可逆CA，第5节利用可达树的结构合成可逆CA参与可逆CA形成的规则见第6节。在第7节中报告了有效合成可逆CA的这些规则的分类。2元胞自动机元胞自动机（CA）由许多以下列形式组织的单元组成： 格子。它在离散的空间和时间中演化。CA的每个单元在时间t存储一个离散变量，该变量指的是单元的当前状态。单元在（t+ 1）处的下一个状态是由其状态和其邻居在时间t处的状态确定的。 在这项工作中，我们集中在这样的3-邻域（自我，左，右邻居）CA，其中CA细胞有两个状态-0或1。因此，下一个状态St+1由下一个状态函数fi指定为（一）St+1=fi（St，St，St）ii−1i i+1ST，ST和ST是左邻居，自我和右邻居的当前状态i−1i i+1在时间t的第i个CA单元。在时间t处的单元状态的集合St=（St，St，···，St）是当前状态。1 2NCA的状态。因此，n-cellCA的下一个状态被确定为（二）St+1=（f1（St，St，St），f2（St，St，St），···，fn（St，St，St ））0121 23n−1n n+1S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205207小区nn−1单元格电池2电池1小区nn−1单元格电池2电池1Fig. 1. n-胞元周期边界CA的框图00图二. n-cell null boundaryCA的框图表1规则90、150和75的真值表现状： 111 110 101 100011 010 001000（RMT）（七）（六）（五）（四）（三）（二）（一）（0）(i)下一个状态： 0101101090(ii)下一个状态： 10010110150(iii)下一个状态：0100101175注：RMT代表规则最小期限。第3/4/ 5行上标注的值0/1表示三变量开关功能的输出如果St=St且St=St（即，最左侧像元的左侧相邻像元是最右侧像元0n n+1 1细胞，反之亦然），那么CA被称为周期性边界CA（图。①的人。另一方面，如果St= 0（null）且St= 0（null），则CA为空边界0n +1(Fig.2）。 本文主要研究周期边界约如果第i个单元的下一个状态函数以真值表的形式表示，则其输出的十进制等价物通常被称为 在两状态3邻域CA中，可以存在总共28（256）个规则。在表1中示出了三个这样的规则90、150和75。第一排的表列出了在时间t时第（i-1）、第i和第（i+ 1）个单元的当前状态的可能的2× 3（8）组合。最后三行分别指示规则90、150和75的第i个单元在（t定义2.1规则集R=构成CA的单元，称为规则向量。定义2.2如果R1=R2=···=Rn，则CA是一致的;否则CA是混合/非均匀。规则最小项（RMT）：从切换理论的观点来看，当前状态的组合（如表1的第一行所示）可以被视为最小项3-变量（St，St，St）的项）切换功能。 因此，每列i−1i i+1表1的第一行被称为规则最小项（RMT）。 列真值表（表1）中的011是第三个RMT。 接下来的状态对应208S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）20519425861012图三. 可逆CA的状态转换202， 195， 105， 165>规则90和75的RMT值为1，规则150的RMT值为0。下一节中报告的表征基于对CA规则的RMT的分析。规则90和150的下一个状态函数采用XOR逻辑。 这些规则称为线性规则。 第75章是非线性的 在总共256条规则中，有14条只使用XOR/XNOR逻辑。这些被称为线性/加法规则。其他规则采用非线性逻辑函数（AND，OR，等等）。定义2.3当规则向量R的所有Ris（i= 1， 2，···，n）都是线性/可加性时，CA被称为线性/可加性CA，否则CA是非线性CA。定义2.4一个规则是平衡的，如果它在8位二进制表示中包含相等数量的1和0;否则它是一个不平衡的规则。表1所示的规则是平衡规则。另一方面，规则171在其8位表示（10101011）中有五个1是一个不平衡的规则。在其随时间演化期间生成的状态序列（状态转换）指导CA行为（图3和图4）。状态转换图CA的状态可以包含循环状态和非循环状态（如果状态位于 在一个循环中），并且基于此，CA可以被分类为可逆或不可逆CA。定义2.5CA是可逆的，如果它在其状态转移图中只包含循环状态;否则CA是不可逆的。在可逆CA中，初始CA状态在一定数量的时间步长后重复（图3）。因此，可逆CA的所有状态都可以从其他状态到达，并且每个状态只有一个前驱。 另一方面在在不可逆CA（图4）中，存在一些不能从任何其它状态到达的状态（不可到达状态）。此外，这种CA的一些状态是有一个以上的前任[11，12]。例如，图4的标记为2、4、5、10和15的状态是不可达状态，而3、6、11和14具有多于一个的前驱。13371511014S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）2052095423087610115131114912图四、不可逆CA的状态转换165，171，75，202>3可达树可达树是我们在文献[5，6，7]中提出的一种表示CA的可达状态的二叉树。树的每个节点都是用规则的RMT构造的（第2节）。节点的左边缘称为0-边缘，右边缘称为1-边缘（图5）。对于一个n-cellCA，可达树的层数是（n+ 1）。根节点位于级别0，叶节点位于级别n。处的节点级别i是从第（i+1）个CA单元规则Ri+1的RMT构造的。 可达性树中的叶节点的数量表示CA的可达状态的数量。从根节点到叶节点的一系列边，表示一个n位二进制字符串，是可达状态，0边表示0，1边表示1。任意两个相邻单元的RMT规则Ri和Ri+1，导致CA的下一个状态的形成。由于RMT是3位的，因此可以考虑使用3位窗口来获得CA的下一个状态[6]。例如，具 有 值 （ 101 ） 的窗口在单元格中被映射到 R i的RMT5 。 如 果 对 于 h 细 胞（bi−1bibi+1），bi=0/1时，对于（i+1）单元，其向下的方向是（bibi+10）或（bibi+11）。我不在这换句话说，如果第i个CA信元在规则Ri的RMT k（bi−1bibi+1的十进制等效值）之后改变其状态，则（i+1）信元将基于规则Ri + 1的RMT2kmod8 （ bibi+10）或（2k+1）mod8（bibi+11）来 计 算 其 扩 展。在计算CA的下一个状态时，Ri和Ri +1的RMT之间的所有关系如表2所示。表中指出的关系起着重要作用在表征CA行为与不同的细胞规则相一致。定义3.1如果两个RMT是由可达性树第i层的相同RMT产生的，则它们在第i+1层是兄弟RMT0和1是兄弟RMT，因为这两个RMT是从RMT0或从RMT4（表2）产生的，并且这些兄弟RMT与单个节点相关联。因此，如果可达性树的节点关联RMT k，则它也关联k的兄弟。CA<165、 171、 75、 202>的可达性树如图5所示。CA规则的RMT如表3所示。图中节点内的十进制数。在级别i处，表示CA小区规则Ri+1的RMT，210S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）2051{0，1}，{5} {3}，{0，1}，{4，5}，{2，3}，{6，7}{0，1，2，3}，{2，3}，{6，7}，{6，7}{0，1}，{}{}，{0，1}，{}，{}{}，{}，{2，3}，{2，3}{0，1}，{0，1}，{}，{}{}，{}，{}，{2，3}{}，{0，1}，{4，5}，{4，5}00表2用于下一状态计算的单元i和单元（i+ 1）的RM Ts之间的关系RMT在第i规则RMT在第（i+ 1）规则00、1个1二、三2四、五3六、七40、1个5二、三6四、五7六、七一{1}，{3}0{4}、{6}1{0}，{2}{5}、{7}0级{2}、{6}0{}、{4}B{3}、{7}1{0，1}，{5}{}、{4} C{2}、{6}01级{6，7}，{6，7}，{0，1，2，3}，{2，3}级别2{4}、{4}{}，{}0D{}、{}1{}，{1}{}、{}{}、{}JE{6}、{6}{}、{}F1{1，3}，{3}{5}，{5}{}，{0}{}、{}{2}、{2}G{7}、{7}{0}，{}{}、{}3级{0}，{}H1{}、{1}{}、{}I{}、{}{4}，{5}0K1{}，{}{}，{}0L1{}，{}{}、{}M1{}、{1} {4}、{5}0N1{}、{}{0}，{}0O{}，{}{}，{}0{}，{}{}，{}1{}、{3}{2}、{}{6}，{7}{2}，{}{}，{3}{}，{}{}，{}{}，{}{6}，{7}{}，{}{}，{}{0，1}，{}{}，{}{}，{2，3}R{}，{}{}，{}，{}，{6，7}{0，1}，{2，3}{4 5}，{}{}，{}{}，{}{4，5}，{6，7}{45}，{}{}，{}X{}，{6，7}{}，{}{4，5}，{6，7}{0，1}，{}{}，{}C' 4级POSTVWYZA图五、CA165、 171、 75、 202的可达性树>单元格（i+ 1）可以改变其状态。例如，根节点（0级）由所有8个RMT（0、1、2、3、4、5、6和7）兄弟RMT（定义3.1）根的集合被分组以形成集合 RMTS(of规则），我们遵循边（0-边或1-边）。规则的RMT是第i个集合的成员，意味着RMT是从根的集合i导出的（0≤i≤3并{4，5}，{4，5}，{6，7}，{6，7}{4，5}，{4，5}，{4，5}，{4，5}，{}，{0，1}{0，1}，{2，3}，{4，5}，{6，7}{2，3}，{6，7}，{0，1}，{4，5}11{}，{2，3}{0，1}，{2，3}{}，{}{}，{}S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205211且集合0是{0，1}，集合1是{2，3}，集合2是{4，5}，{6，7}是集合3）。这样的分组便于周期性边界CA的表征。对于165个RMT1（第0组）、3（第1组）、4（第2组）和6（第3组）（表3），212S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205表3CA105， 128， 171， 65>单元格规则的二进制值RMT 111 110 101 100 011 010 001 000（七）（六）（五）（四）（三）（二）（一）（0）第一细胞10100101165二小区10101011171T细胞0100101175F细胞11001010202接下来的状态是0，对于RMT0（集合0）、2（集合1）、5（集合2）和7（集合3），它是1。因此，在级别1处，级别0的0-边之后的节点（图5的节点B）包含RMT{2，3}、{6，7}、{0，1}和{4，5}（表2）。 同样，节点C在级别0的1-边之后，包含RMTs{ 0，1}，{4，5}，{2，3}和{6，7}。从m和node（nodeE，nodeI，· ··）中删除的数据包含nod es没有对应的边（0-edge）。节点E上的虚线0边表示任何以010开始的状态都是不可达的。从层（n-2）（图5的层2）和层（n-1）（即图5的层3）处的节点丢弃多个RMT在第（n-2）层的节点的RMTs对应于CA单元规则Rn-1。集合0和集合1的RMTs假设当我们计算下一个状态时，单元n总是0，而集合2的RMT s假设当我们计算下一个状态时，单元n总是0，而集合2而集合3假定小区n总是1。因此，集合0和集合1的奇数RMT以及集合2和集合3的偶数RMT是无效的，因此被删除。同样，第（n-1）层节点的RMTs对应于CA单元规则Rn。因此，集合0的RMT s对于Rn（在水平（n-1））应该生成集合0的RMTs对于R1，因为最后一个单元的旁边是第一个单元。然而，在（n-1）层的集合0的少数RMT可能不会为R1生成集合0，这些被标记为无效，并被删除。对其他集合采取类似的行动。在节点H（图5）中，集合0的RMT1被删除，因为它不能为R1（{0，1}）生成集合0。类似地，删除集合1的RMT可达树最初被定义为描述空边界CA[5，6，7]。然而，图5所示的结构可以对本工作中考虑的周期性约束CA进行可达性树的这种重新定义的结构提供了表征可逆性周期性边界CA的方法。4可逆CA本节报告了识别可逆周期性边界CA的理论背景。可达性树的概念，在前面的部分介绍，是用来开发的理论框架。定理4.1可逆CA的可达树是平衡的。证据 由于可逆CA的所有状态都是可达的，因此叶节点S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205213在可达性树中，对于n-cell可逆CA，为2n（状态数）。因此，该树是平衡的，因为它是（n+1）层的二叉树Q上面的定理指出了一个事实，即可逆CA的识别可以通过构造CA的可达树来完成。如果树中不存在不可达状态，则CA是可逆的.定理4.23-邻域周期边界CA的可达树是平衡的：(i) 每个叶边缘由单个RMT产生，(ii) 叶边缘的每个直接前驱（边缘）由两个RMT产生，并且(iii) 所有其它边缘由4个RMT产生。证据让我们考虑，规定边缘的RMT的数量小于（i）至（iii）中提到的数量。也就是说，i. 没有RMT来规定叶边缘。 这意味着树是不平衡的。ii. 叶边缘的边缘前驱由单个RMT产生。因此，该边的下一个节点由2个RMT构成。由于节点在（n-1）层，一个RMT必须被删除，因为它是另一个的兄弟，并且两者都是一个集合的成员。该单个有效RMT可以生成单个边缘。另一个是空的。因此，树是不平衡的。iii. 假设，中间边由3个RMT产生。因此，到该边缘的下一个节点（N）用6个RMT构造。在下一级，节点N可以具有两条边，这两条边可以由1和5、2和4或3和3个RMT产生。在最好的情况下，树可以保持平衡到第（n-2）层。在（n-2）层中，可以找到至少一个节点来自由1或2或3个RMT产生的边。因此，节点由2、4或6个RMT构成。由于节点处于（n-2）层，因此有一半的RMT无效。因此，相应地，节点被构造为具有1、2或3个RMT。如果RMT的个数是1，那么显然树是不平衡的。否则，该节点的至少一条边由单一的RMT，这将导致一个不平衡的树（ii）。另一方面，如果中间边缘由多于4个RMT产生，则可以找到由少于4个RMT产生的边缘。这意味着，树是不平衡的（iii）。现在，如果叶边缘的前趋边缘是由多于两个RMT产生的，则另一边缘是由少于两个RMT产生的RMTs，因为在第（n-1）层构造节点的RMTs的一半被删除出去因此，树是不平衡的（由二）。类似地，如果一个叶子边是由多于1个RMT产生的，那么树也是不平衡的。 因此，如果数字 的RMTs，其指示边缘，与在（i）至（iii）中提到的不同，可达性树是不平衡的。 所以才有证据。Q推论4.33-邻域可逆周期边界元胞自动机对应的可达树的节点构造为(i) 如果节点是叶节点，则为2个RMT(ii) 4个RMT，如果节点是叶子的直接前任，以及214S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205表4CA202， 195， 105， 165>单元格规则的二进制值RMT 111 110 101 100 011 010 001 000（七）（六）（五）（四）（三）（二）（一）（0）第一细胞11001010202二小区11000011195T细胞01101001105F细胞10100101165(iii) 8个RMT用于所有其他节点;其中节点的RMT可能不是唯一的。证据 根据定理4.2，对于可逆CA，(i) 叶边缘由单个RMT产生，(ii) 叶边缘的前导是由2个RMT产生的，并且(iii) 所有其它边缘由4个RMT产生。因此，（i）叶用2个RMT构造，（ii）叶的直接前代用4个RMT构造，以及（iii）所有其他节点由8个RMT产生。Q推论4.4可逆CA的可达树的节点在其RMT上是平衡的。证据由于可逆CA的可达性树是平衡的，因此每个节点具有 左子元素（0-edge）和右子元素（1-edge）。 从定理4.2可以明显看出，如果 一个孩子是由k个RMT产生的，另一个孩子也是由k个RMT产生的。 因此，节点在其RMT上平衡。Q例4.5考虑四胞CAR= 202， 195， 105， 165>。<图6是R.CA是可逆的。图6平衡。树的每个节点也在其RMT上平衡。基 于 上 述 讨 论 ， 我 们 接 下 来 提 出 了 一 种 识 别 可 逆 CA 的 方 法 。 以 下 算 法（CheckReversible）从左到右扫描CA规则向量，并虚拟地构建可达性树。然后验证定理是否成立对于给定的CA规则向量，满足4.2如果找到这样的边缘，则它是不可逆CA。算法替换具有相同RMT集合的重复节点（如果有的话）。算法1检查可逆输入：R1，R2，···，Ri，···，Rn>（n单元CA）<输出：可逆或不可逆。步骤1：设S0={s0，s1，s2，s3}和S1={s0，s1，s2，s3}为RMT0 0 0 0 1 1 1 1其中（i）对于R1，S0和S1的RMTs分别为0和1，以及（ii）S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205215{}，{4，5}{2，3}，{}{0，1}，{4，5}，{0，1，2，3}，{}{1}，{3}{}，{}，{6，7}{}，{6，7}{2，3}，{6，7}，{}，{4，5，6，7}{0，1，2，3}，{}，{0，1，2，3}，{}{}、{6}{}、{5}{}，{4，5}，{}，{2，3}{}，{0，1}，{}，{6，7}{}，{0，1，2，3}，{4，5，6，7}，{}{}、{}{}、{1}{}，{7}{}，{}{}，{}{}、{7}{}，{}{}，{2，3}{}，{6，7}{ }、{}{}，{}{}，{6，7}{4，5}，{6，7}{0，1}，{2，3}{4，5}，{}，{2，3}，{}{0，1}，{}，{6，7}，{}{}，{4，5}，{6，7}，{}{}，{0，1}，{2，3}{}JJ100100001{0}，{2}{4，5}，{}{0，1}，{2，3}，{4，5}，{6，7}{0，1}，{}{0，1}，{}{2，3}，{}{}，{4，5}1级2级{}、{2}{}，{0}{2}、{}{0}，{}{4}、{}{6}、{}{}、{4}{7}、{}{5}、{}{1}、{}{3}、{}{}、{1}{}、{3}{}、{7}3级{}，{}{}、{5}{}、{1}{}，{}{4}、{}{}，{}{}，{}{0}，{}{}，{}{0}，{}{4}、{}{}，{}{}、{5}{6}，{}{}，{}{}，{}{2}、{}{}、{}{2}、{}{6}、{}{}，{}{}、{3}{}，{}{}，{}{}、{3}{}，{}{1}、{}{4，5}，{}{}，{2，3}{}，{}{}，{2，3}，{}，{}{}，{}，{4，5}，{}{0，1}，{}，{}，{}{0，1}，{}{}，{}{}，{}{}，{6，7}{}，{}{}，{6，7}{}，{2，3}{}，{}图第六章可逆CA的可达性树202， 195， 105， 165>SK成员是φ，RMT2k，RMT（2k + 1）或RMTs2k（2k + 1），j = 0/1且k = 0、1、2或3。如果|s0|+的|S1|+的|S2|+的|S3|=/|+的|S1|+的|S2|+的|S3|，将CA报告为不可逆|, report theCA as irreversible0 0 0 0然后回来1 1 1 1步骤2：对于i= 2到n，重复步骤3到步骤6步骤3：对于RMT集合的每个集合，考虑表2，找到构造可达性树的下一级节点的RMT。步骤4：（i）如果i=n- 1，则从s0和s1中移除奇数RMTs，并且从s 1中移除偶数RMTs。J J从S2到S3。J J（ii）如果i=n，则从sk中移除那些RMTs 可以生成RMTs2k，（2 k+ 1），R1。步骤5：删除具有相同RMT集的重复节点（如果有的话）。步骤6：将每个节点的RMTs分配到两个集合Sj中而SJ基于Ri，J0J1J2J3JJ0J1J2J3JkJk其中S0 ={s0，s0，s0，s0}且S1 ={s1，s 1，s1，s1}，sj 来源于 SJ 和Sj和SJ的 RM T s 分别为0和1。0J1J2J3J0J1J2J3J如果|s0| + |s0| + |s0| + |s0|/= |S1| + |S1| + |S1| + |S1|，将CA报告为不可逆然后回来步骤7：报告CA是可逆CA并返回。复杂度：由于可能的RMT集的最大数量是固定的，算法1的执行时间仅取决于n（步骤2）。因此，算法1的复杂度为O（n）。示例4.6本示例说明了算法1的执行步骤。将4单元CA202、 195、 105、 165>视为算法1的输入。用于规则202（R1），s0 ={ 0}，s1={ 2}，s2={ 4， 5}s3= {}，{4，5，6，7}，{0，1，2，3}{}，{4，5，6，7}，{}，{4，5，6，7}{}，{}，{}，{}{4，{4 5}，{}{0，1}，{}{0，1}，{}{}，{}{}，{}216S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205且s0={ 1}，s1={ 3}，s2={}s3={ 6， 7}（表4）。这里，S0={{ 0}，{ 2}，{ 4， 5}，{}}，并且1 1 1S1={{1}，{3}，{}，{6，7}}。因 此 ，我们认为，|s0|+的|S1|+的|S2|+的|S3|为|s0|+的|S1|+的|S2|+的|S3|.0 0 0 0 1 1 1 1S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）2052170101JJ01作为下一步骤，对于集合S0和S1，该算法为级别1的节点找到RMTs节点为{{0，1}，{4，5}，{0，1，2，3}，{}}和{{2，3}，{6，7}，{}，{4，5，6，7}}（图6的级别1）。 对于每个节点，SJ而SJ构造(step（六）。 由于SJ中的RMT&SJ对于两个节点是相同的（4），无法下结论。在下一步中，我们得到4个节点，如图6的第2层所示。节点对应于Rn−1= 105。因此，每个节点的RMT的一半被删除（步骤4（i））。根据规则105，我们得到第3层的节点然后去除多个RMT（步骤4（ii））。然而，使用规则165，获得叶节点因此，在步骤7中声明CA是可逆的。5可逆CA可逆CA的合成是前面章节中报告的分析/鉴定的逆过程算法SynthesizeReversibleCA 1提出了一种高效的综合方案。算法的输入是n，即要合成的CA的单元数/大小，并且输出是n单元可逆CA。它通过检查为CA单元选择的规则Ri的RMTs来确定可逆CA的第（i+1）可达树的每条边由四个RMT（在某些特殊情况下，两个或一个RMT）产生，如定理4.2所指导的。算法2 SynthesizeReversibleCA 1输入：n（CA单元的数量）.输出：（n−cell可逆CA）。步骤1： 选择一个平衡规则作为R1.设S0 = {s0，s1，s2，s3}和S1={s0，s1，s2，s3}是RMT集合的两个集合，0 0 0 01 1 1 1(i) 对于R1， S0和 S1的RMTs分别为0和1，(ii) sk的成员是φ、RMT2k、RMT（2k + 1）或RMTs2k&（2k + 1），其中j = 0/1且k = 0、1、2或3。步骤2：对于i= 2至n，重复步骤3至步骤6步骤3：对于RMT集合的每个集合考虑表2，找到构造可达性树的下一级节点的RMT。步骤4：（i）如果i=n- 1，则从s0和s1中移除奇数RMTs，并且从s 1中移除偶数RMTs。J J从S2到S3。J J（ii）如果i=n，则从sk中移除那些RMTs 可以生成RMTs2k，（2 k+ 1），R1。步骤5：删除重复节点（如果有）。步骤6：找到将每个节点的RMTs划分为两个集合Sj的规则RiJ J0J1J2J3JJ0J1J2J3J0J1J和S1，其中S0 ={s0，s0，s0} &S1 ={s1，s 1，s1，s1}，并且|s0|+的|s0|+的2J3J0J1J2J3JkJkJ|+的|s 0|为|S 1|+的|S 1|+的|S 1|+的|S 1|; sj|; sj由sj导出 和S0的RMT和SJ分别为0和1。第7步：将报告为n−cell可逆CA。复杂性：由于可能的RMT集的最大数量是固定的，算法2的执行时间仅取决于n（步骤2）。因此，218S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205时间复杂度为O（n）。根据定理4.2和算法1，可以观察到CA的每个规则在确定CA的可逆行为中起重要作用。定义5.1[6]一个规则是不可逆规则，如果它在规则向量中的存在使得CA不可逆。否则，它是一个可逆的规则。例5.2规则向量为202， 195， 105， 165>的4-胞CA是可逆CA。<因此，这四个规则都是可逆规则。另一方面，具有规则向量202、 196、 105、 165>的CA是不可逆CA。<第196条规则使CA不可逆转。第196章这是不可逆转的规则196（11000100）是一个不平衡1 在RMT196中0的个数是5。可逆规则的表征还使得能够高效地合成任意长度的可逆CA下一节报告了这种特性。 在第7节中介绍了基于此表征的可逆CA合成方案。6可逆规则可逆规则被认为是合成可逆CA的基本构建块。本节探讨3-邻域依赖中可逆规则的属性。定理6.1不平衡规则是不可逆规则。证据考虑CAR=R1，，其中Ri是不平衡规则，RJJ=R1，是可逆CA.除第i条规则外，R和RJJ的所有规则R的可达树被平衡到第（i-1）层，因为RJJ是可逆的CA，并且对于第1至第（i-1）个单元，在R情况1：i n-1：由于Ri是不平衡的，因此在第（i-1）层至少存在一个节点，其子节点不是由正好4个RMT产生的。情况2：i=n- 1：在第n-2个节点上至少存在一个节点，其子节点由1个（或3个）RMTs产生。情况3：i=n：由于Rn是不平衡的，因此一些叶子边缘不是由精确的单个RMT产生的。上面的讨论意味着树是不平衡的（定理4.2）。因此，具有规则向量R的CA是不可逆的。 所以才有证据。Q在3-邻域依赖中，有8条C4= 70的平衡CA规则.在3-邻域周期边界元胞自动机的情况下，所有的平衡规则都是可逆规则。表5中列出了这些。可逆规则只能形成可逆CA。然而，CA规则向量中的可逆规则的任何序列不一定意味着所得到的CA是可逆CA。定理6.2只有可逆规则的特定序列形成可逆CA。S. Das，B.K.Sikdar/Electronic Notes in Theoretical Computer Science 252（2009）205219{}，{}{}，{5，7}{}，{4，5}，{}，{2，3}{}，{0，1}，{}，{6，7}{}，{4，5}2，3}，{}{1}，{3}{}，{2，3}，{6，7}，{}，{4，5，6，7}{}，{6，7}{}，{6，7}{}，{4，5，6，7}，{}，{4，5，6，7}我15 23 27 29 30 39 43 45 46 51 53 5457 58 60 71 75 77 78 83 85 86 89 9092 99 101 102 105 106 108 113 114 116 120 135139 141 142 147 149 150 153 154 156 163 165 166169 170 172 177 178 180 184 195 197 198 201 202204 209 210 212 216 225 226 228 232 240表5周期边界3-邻域依赖{0}，{2}{4，5}，{}{0，1}，{4，5}，{0，1，2，3}，{}{0，1}，{2，3}，{4，5}，{6，7}{0，1}，{}{{0，1}，{}{2，3}，{}{}，{4，5}{}，{0，1，2，3}，{4，5，6，7}，{}{0，1，2，3}，{}，{0，1，2，3}，{}{4，5，6，7}，{0，1，2，3}{}，{}{}，{0，2}{}，{}{0，2}，{}{4，6}，{}{}，{}{}，{4，6}{}，{}{5，7}，{}{1，3}，{}{}，{}{}，{1，3}{}，{}{}，{}{}，{0，1，4，5}，{0，1，4，5}，{}，{0，1，4，5}，{}{}，{}，{2，3，6，7}，{}{}、{1}{}、{5}{}，{}{}，{}{4}、{}{0}，{}{4}、{}{0}，{}{}，{}{}、{5}{2}，{}{6}、{}{7}、{}{3}、{}{}，{}{}，{}{}，{7}{}，{3}{}、{3}{}，{}{}，{2，3}，{4，5}，{}{}，{2，3}，{4，5}，{}{0，1}，{}{}，{}{0，1}，{}{}，{6，7}{0，1}，{}{}，{6，7}{}，{}{}，{6，7}{}，{2，3}{}，{}图第七章使用可逆规则设计的不可逆CA的可达性树202， 195， 165， 105>证据让我们考虑一个n-cellCA的可逆规则是这样确定的，即加载有任何种子的CA{· · ·didi+1· ··}和{· · ·dJdJ· ··}，其中di（=0/1）是细胞的状态，同时i i+1J是它的补充。因此，对于2n个当前状态，接下来的状态areS={· · ·didi+1· · ·，· · ·dJdJ· ··}。S的最大可压缩性为i i+12× 2n−2 = 2n−1。 由于下一个状态的数量小于当前状态在S中至少存在一个状态，它有一个以上的前驱。因此，CA是不可逆的。因此，任何可逆规则序列Q例6.3CA202、 195、 105、 165>是可逆的（例4.6）。然而，CAR= 202，195， 165， 105>是不可逆CA，即使R中的每个规则都是可逆规则（表5）。

下载后可阅读完整内容，剩余1页未读，立即下载