论文标题
关于von Neumann的蜂窝自动机的规律性
On von Neumann regularity of cellular automata
论文作者
论文摘要
我们表明，有限的两侧混合次要换档上的细胞自动机是且仅当且只有当将史诗划分为Sofic Shifts and Shofic Shifts和block Map的类别中时，在细胞自动机的半群中是von Neumann的常规元件。从作者和Törmä的先前联合工作中，von Neumann的规律性是可决定的，我们为所有基本CA决定，为弱的广义倒置获得了最佳半径。非规范性的两个足够的条件是具有适当的Sofic图像或图像中的点，而没有同一时期的预先映射。我们表明，使用这些方法不能证明非规范的ECA 9和28不能证明非规范。我们还表明，随机细胞自动机是不规则的，概率很高。
We show that a cellular automaton on a one-dimensional two-sided mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from previous joint work of the author and Törmä that von Neumann regularity is a decidable condition, and we decide it for all elementary CA, obtaining the optimal radii for weak generalized inverses. Two sufficient conditions for non-regularity are having a proper sofic image or having a point in the image with no preimage of the same period. We show that the non-regular ECA 9 and 28 cannot be proven non-regular using these methods. We also show that a random cellular automaton is non-regular with high probability.
