We study the dynamics of (synchronous) one-dimensional cellular automata with cyclical boundary conditions that evolve according to the majority rule with radius $ r $. We introduce a notion that we term cell stability with which we express the structure of the possible configurations that could emerge in this setting. Our main finding is that apart from the configurations of the form $ (0^r0^* + 1^r1^*)^* $, which are always fixed-points, the other configurations that the automata could possibly converge to, which are known to be either fixed-points or 2-cycles, have a particular spatially periodic structure. Namely, each of these configurations is of the form $ s^* $ where $ s $ consists of $ O(r^2) $ consecutive sequences of cells with the same state, each such sequence is of length at most $ r $, and the total length of $ s $ is $ O(r^2) $ as well. We show that an analogous result also holds for the minority rule.
翻译:我们研究的是(同步的)一维细胞自动成像的动态,其周期性边界条件根据多数规则而变化,以美元半径演变。我们引入了一种概念,即我们用细胞稳定性来表达在这个环境中可能出现的配置结构。我们的主要发现是,除了以美元(0°0 ⁇ +1°r1 ⁇ )+美元($)的形态外,每个这种形态的长度最多为美元,总长度为美元(O°2美元),而且总长度为美元(O°2美元)。我们发现,该自动成像可能汇合的其他组合有特定的空间周期结构,即每个这些配置都以美元为单位,以美元为单位,以美元为单位,以美元为单位,以美元为单位,以美元为单位,以美元为单位,以美元为单位,以美元为单位,以美元为单位,总长度为美元(O(r ⁇ 2)美元)为单位。我们发现,少数规则也有类似的结果。