Inducing an order on cellular automata by a grouping operation Original Research Article

Let X be a one-dimensional cellular automaton. A “power of X” is another cellular automaton obtained by grouping several states of X into blocks and by considering as local transitions the “natural” interactions between neighbor blocks. Based on this operation a preorder ⩽ on the set of one-dimensional cellular automata is introduced. We denote by (CA∗, ⩽) the canonical order induced by ⩽. We prove that (CA∗, ⩽) admits a global minimum and that very natural equivalence classes are located at the bottom of (CA∗, ⩽). These classes remind us the first two well-known Wolfram ones because they capture global (or dynamical) properties as nilpotency or periodicity. Non-trivial properties as the undecidability of ⩽ and the existence of bounded infinite chains are also proved. Finally, it is shown that (CA∗, ⩽) admits no maximum. This result allows us to conclude that, in a “grouping sense”, there is no universal CA.