A note on universality in multidimensional symbolic dynamics

DOI10.3934/DCDSS.2009.2.301zbMATH Open1175.37019arXiv0901.3600OpenAlexW3103693582MaRDI QIDQ733816FDOQ733816

Authors: Michael Hochman 

Publication date: 19 October 2009

Published in: Discrete and Continuous Dynamical Systems. Series S (Search for Journal in Brave)

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 $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 $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.

Full work available at URL: https://arxiv.org/abs/0901.3600

Recommendations

• On the dynamics and recursive properties of multidimensional symbolic systems
• scientific article; zbMATH DE number 5117086
• On factor universality in symbolic spaces
• Machines, Computations, and Universality
• scientific article; zbMATH DE number 2158945

zbMATH Keywords

cellular automatondecidabilitytopological dynamicsshift of finite typeMedvedev degree

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Dynamical aspects of cellular automata (37B15) Topological entropy (37B40) Theory of numerations, effectively presented structures (03D45)

Cited In (9)

• Machines, Computations, and Universality
• On factor universality in symbolic spaces
• Universal bifurcation property of two- or higher-dimensional dissipative systems in parameter space: why does 1D symbolic dynamics work so well?
• On the dynamics and recursive properties of multidimensional symbolic systems
• Category theory of symbolic dynamics
• Universal form of renormalizable knots in symbolic dynamics of bimodal maps
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts
• Rohlin properties for \(\mathbb {Z}^{d}\) actions on the Cantor set
• Multiformity of inherent randomicity and visitation density in \(n\) symbolic dynamics

This page was built for publication: A note on universality in multidimensional symbolic dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733816)