论文标题
产生无限的细胞自动机
Generating infinite monoids of cellular automata
论文作者
论文摘要
对于组$ g $和set $ a $，令$ \ text {end}（a^g）$是$ a^g $上所有蜂窝自动机的单体，然后让$ \ text {aut}（a aut}（a^g）为其单位组。通过建立曲面组的表征，根据himoid $ \ text {end}（a^g）$，我们证明$ \ text {end}（a^g）$的等级（即生成集的最小基数）等于$ \ text {aut} $ plus $ \ aut} $ plus $ \ aut等级的等级$ \ text {end}（a^g）$，而当$ g $具有无限的有限索引的普通亚组的无限链链时，后者是无限的，例如，对于任何无限残留有限的有限型组，都可以满足该条件。此外，当$ a = v $是字段$ \ mathbb {f} $上的矢量空间时，我们研究了所有线性蜂窝的$ v^g $及其$ v^g $组的单线性蜂窝automata的monoid $ \ text {end} _ {\ mathbb {f}}（v^g）$ $ \ text {aut} _ {\ mathbb {f}}（v^g）$。我们表明，如果$ g $是一个指示的组，而$ v $是有限的，则$ \ text {end} _ {\ mathbb {f}}}}}（v^g）$不是有限生成的；但是，对于任何有限生成的指示组$ g $，组$ \ text {aut} _ {\ mathbb {f}}}（\ mathbb {f}^g）$是有限生成的，仅当$ \ mathbb {f} $是有限的。
For a group $G$ and a set $A$, let $\text{End}(A^G)$ be the monoid of all cellular automata over $A^G$, and let $\text{Aut}(A^G)$ be its group of units. By establishing a characterisation of surjunctuve groups in terms of the monoid $\text{End}(A^G)$, we prove that the rank of $\text{End}(A^G)$ (i.e. the smallest cardinality of a generating set) is equal to the rank of $\text{Aut}(A^G)$ plus the relative rank of $\text{Aut}(A^G)$ in $\text{End}(A^G)$, and that the latter is infinite when $G$ has an infinite decreasing chain of normal subgroups of finite index, condition which is satisfied, for example, for any infinite residually finite group. Moreover, when $A=V$ is a vector space over a field $\mathbb{F}$, we study the monoid $\text{End}_{\mathbb{F}}(V^G)$ of all linear cellular automata over $V^G$ and its group of units $\text{Aut}_{\mathbb{F}}(V^G)$. We show that if $G$ is an indicable group and $V$ is finite-dimensional, then $\text{End}_{\mathbb{F}}(V^G)$ is not finitely generated; however, for any finitely generated indicable group $G$, the group $\text{Aut}_{\mathbb{F}}(\mathbb{F}^G)$ is finitely generated if and only if $\mathbb{F}$ is finite.
