Cellular automata can really solve the parity problem
Barbara Wolnik, Anna Nenca, Pedro Paulo Balbi, Bernard De Baets
如果只允许本地处理,确定任意二进制序列的属性是一项具有挑战性的任务。 在这些特性中,通过分布式共识确定1的均等是自动机网络背景下反复进行的努力。 在其最标准的配方中,一维细胞自动机规则应该处理任何奇数大小的循环配置,并引导晶格收敛到0的均匀固定点,如果1s的奇偶校验是偶数,则引导晶格收敛到0s的均匀固定点,否则。 唯一已知的单一规则解决这个问题的方法是Betel,de Oliveira和Flocchini(在作者的首字母缩写后被创造的BFO规则)。 然而,三年后,BFO规则的作者意识到该规则在某些特定配置中将失败,并提出了一个计算声音修复,但无法解决一个证据。 在这里,我们提供了BFO规则的另一个解决方案以及完整的证明,因此保证问题的真正存在单一规则解决方案。
Determining properties of an arbitrary binary sequence is a challenging task if only local processing is allowed. Among these properties, the determination of the parity of 1s by distributed consensus has been a recurring endeavour in the context of automata networks. In its most standard formulation, a one-dimensional cellular automaton rule should process any odd-sized cyclic configuration and lead the lattice to converge to the homogeneous fixed point of 0s if the parity of 1s is even and to ...