Inducing an order on cellular automata by a grouping operation

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 less than or equal to on the set of one-dimensional cellular automata is introduced. We denote by (CA*, less than or equal to) the canonical order induced by less than or equal to. We prove that (CA*, less than or equal to) admits a global minimum and that very natural equivalence classes are located at the bottom of (CA*, less than or equal to). 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 less than or equal to and the existence of bounded infinite chains are also proved. Finally, it is shown that (CA*, less than or equal to) admits no maximum. This result allows us to conclude that, in a "grouping sense", there is no universal CA. (C) 1999 Published by Elsevier Science B.V. All rights reserved.