Large semigroups of cellular automata
Large semigroups of cellular automata
复制标题
元胞自动机的大半群
DOI：
10.1017/s0143385711000551
复制
发表时间：
2010
影响因子：
0.9
通讯作者：
Yair Hartman
中科院分区：
文献类型：
--
作者：
Yair Hartman
本文考虑了作用在固定移位空间上的元胞自动机的变换半群。特别是，我们感兴趣的两个性质，这些半群涉及到“大”：第一，半群有ID（无限是密集的）性质，如果唯一的无限不变闭集（相对于半群行动）是整个空间;第二个属性是最大交换性（MC）。我们将考虑半群的两个例子：一个是由表示一维环面上整数乘法的元胞自动机变换构成的，另一个是由所有线性的元胞自动机变换构成的（当符号集是环/s时）。我们将证明这些半群的这两个性质依赖于符号s的个数。乘法半群是ID和MC当且仅当s不是素数的幂。所述环上的线性半群总是MC但是ID当且仅当s是素的。当符号集被赋予有限域结构时（如果可能的话），线性半群既是ID又是MC。此外，我们与每个作用在单侧移位空间上的半群相关联，作用在双侧移位空间上的半群，反之亦然，以保持ID和MC性质的方式。
Abstract In this article, we consider semigroups of transformations of cellular automata which act on a fixed shift space. In particular, we are interested in two properties of these semigroups which relate to ‘largeness’: first, a semigroup has the ID (infinite is dense) property if the only infinite invariant closed set (with respect to the semigroup action) is the entire space; the second property is maximal commutativity (MC). We shall consider two examples of semigroups: one is spanned by cellular automata transformations that represent multiplications by integers on the one-dimensional torus, and the other one consists of all the cellular automata transformations which are linear (when the symbols set is the ring ℤ/sℤ). It will be shown that these two properties of these semigroups depend on the number of symbols s. The multiplication semigroup is ID and MC if and only if s is not a power of a prime. The linear semigroup over the mentioned ring is always MC but is ID if and only if s is prime. When the symbol set is endowed with a finite field structure (when possible), the linear semigroup is both ID and MC. In addition, we associate with each semigroup which acts on a one-sided shift space a semigroup acting on a two-sided shift space, and vice versa, in a way that preserves the ID and the MC properties.