Universality in Multidimensional Symbolic Dynamics
Preprint
Abstract
We show that in the category of effective $Z$ dynamical systems there is a universal system, i.e. one that factors onto every other effective system. In particular, for d $\geq 3$ there exist d-dimensional shifts of finite type which are universal for 1-dimensional subactions of SFTs. On the other hand, we show that there is no universal effective $Z^d$-system for $d>1$, and in particular SFTs cannot be universal for subactions of rank $d>1$. As a consequence, a decrease in entropy and Medvedev degree and periodic data are not sufficient for a factor map to exists between SFTs. We also discuss dynamics of cellular automata on their limit sets and show that (except for the unavoidable presence of a periodic point) they can model a large class of physical systems.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- A characterization of the entropies of multidimensional shifts of finite typeAnnals of Mathematics, 2010
- Theory of cellular automata: A surveyTheoretical Computer Science, 2005
- Factoring higher-dimensional shifts of finite type onto the full shiftErgodic Theory and Dynamical Systems, 2005
- Introduction to automata theory, languages, and computation, 2nd editionACM SIGACT News, 2001
- Tilings, substitution systems and dynamical systems generated by themJournal d'Analyse Mathématique, 1989
- Endomorphisms and automorphisms of the shift dynamical systemTheory of Computing Systems, 1969
- The undecidability of the domino problemMemoirs of the American Mathematical Society, 1966