A study on the composition of elementary cellular automata
Alonso Castillo-Ramirez and Maria G. Magaña-Chavez
基本蜂窝自动机(ECA)是具有小内存集的单维离散计算模型,自Stephen Wolfram的先驱工作以来,该模型已经引起了极大的兴趣,后者将它们作为时间离散的动力学系统进行研究。 256 ECA 中的每个都标记为规则 X,其中 X 是 0 到 255 之间的整数。 在计算研究中通常忽略的一个重要特性是,任何两个一维细胞自动机的组成再次是一个一维细胞自动机。 在本章中,我们开始对非洲经委会的组成进行系统研究。 直观地说,如果组合物X∘Y和Y∘X具有小的最小内存集,则规则X具有低复杂性,对于许多规则Y。 因此,我们根据其中的组合提出非洲经委会的新分类。 我们还描述了ECA的所有半组(即ECA的构成封闭集),并从半群论的角度分析其基本结构。 特别是,我们确定ECA最大的半组有9个元素,并且有一个顺序8的子组,即R-trivial,该属性最近用于定义随机行走和马尔可夫链。
Elementary cellular automata (ECA) are one-dimensional discrete models of computation with a small memory set that have gained significant interest since the pioneer work of Stephen Wolfram, who studied them as time-discrete dynamical systems. Each of the 256 ECA is labeled as rule X, where X is an integer between 0 and 255. An important property, that is usually overlooked in computational studies, is that the composition of any two one-dimensional cellular automata is again a one-dimensional c...