Inducing an order on cellular automata by a grouping operation
| Autor: | Jacques Mazoyer, Ivan Rapaport |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Cellular automata
Discrete mathematics Applied Mathematics Preorder 0102 computer and information sciences 02 engineering and technology Nonlinear Sciences::Cellular Automata and Lattice Gases 01 natural sciences Cellular automaton Intrinsic universality Set (abstract data type) Combinatorics 010201 computation theory & mathematics Bounded function Grouping 0202 electrical engineering electronic engineering information engineering Dynamical classification Discrete Mathematics and Combinatorics Embedding Order (group theory) Order 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | Discrete Applied Mathematics. 91:177-196 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/s0166-218x(98)00125-5 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect