×

Additive cellular automata over \(\mathbb{Z}_p\) and the bottom of \((CA,\leq)\). (English) Zbl 0914.68143

Brim, Luboš (ed.) et al., Mathematical foundations of computer science 1998. 23rd international symposium, MFCS ’98. Brno, Czech Republic, August 24–28, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1450, 834-843 (1998).
Summary: In a previous work we began to study the question of “how to compare” cellular automata \((CA)\). In that context it was introduced a preorder \((CA,\leq)\) admitting a global minimum and it was shown that all the \(CA\) satisfying very sinmle dynamical properties as nilpotency or periodicity are located “on the bottom of \((CA,\leq)\)”. Here we prove that also the (algebraically amenable) additive \(CA\) over \(\mathbb{Z}_p\) are located on the bottom of \((CA,\leq)\). This result encourages our conjecture that says that the “distance” from the minimum could represent a measure of “complexity” on \(CA\). We also prove that the additive \(CA\) over \(\mathbb{Z}_p\) with \(p\) prime are pairwise incomparable. This fact improves our understanding of \((CA,\leq)\) because it means that the minimum, even in the canonical order compatible with \(\leq\), has infinite outdegree.
For the entire collection see [Zbl 0895.00049].

MSC:

68Q80 Cellular automata (computational aspects)
PDFBibTeX XMLCite