A note on universality in multidimensional symbolic dynamics

Pages: 301 - 314, Volume 2, Issue 2, June 2009

doi:10.3934/dcdss.2009.2.301       Abstract        Full Text (191.9K)       Related Articles

Michael Hochman - Department of Mathematics, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544, United States (email)

Abstract: We show that in the category of effective $\mathbb{Z}$-dynamical systems there is a universal system, i.e. one that factors onto every other effective system. In particular, for $d\geq3$ 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 $\mathbb{Z}^{d}$-system for $d\geq2$, and in particular SFTs cannot be universal for subactions of rank $\geq2$. 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:  Shift of finite type, Cellular automaton, Decidability, Medvedev degree, Topological dynamics.
Mathematics Subject Classification:  37B15, 37B40, 37B50, 94A17, 03D45.

Received: February 2008;      Revised: September 2008;      Published: April 2009.