Inducing an order on cellular automata by a grouping operation.
Résumé
A grouped instance of a cellular automaton (CA) is another one obtained by grouping several states into blocks and by letting interact neighbor blocks. Based on this operation (and on the subautomaton notion), a preorder $\leq$ on the set of one dimensional CA is introduced. It is shown that (CA, leq) admits a global minimum and that on the bottom of (CA, leq) very natural equivalence classes are located. 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 leq and the existence of bounded infinite chains are also proved. Finally, it is shown that (CA, leq) admits no maximum. This result allows us to conclude that, in a ``grouping sense'', there is no universal CA.
Une instance groupée d'un automate cellulaire (AC) est un autre obtenu par groupage de plusieurs états en blocs et par l'interaction ``naturelle'' de ces blocs. Basé sur cette opération (et sur la notion de sous-automate), un préordre leq sur l'ensamble des AC à une dimension est introduit. Il est montré que (AC, leq) admet un minimum global et que des classes d'equivalence très naturelles se trouvent en bas de (AC, leq). On retrouve dans ces classes les deux premières bien connues de Wolfram qui capturent des proprietés globales (ou dynamiques) comme la nilpotence et la périodicité. Des proprietés non triviales comme l'indécidabilité de leq et l'existence de cha{î}nes infinies bornées sont aussi prouvées. Finalement il est montr{é} que (AC, leq) n'admet pas de maximum. Cet resultat nous permet de conclure qu'il n'existe pas de AC universel d'un point de vue ``groupage''.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...