American Institute of Mathematical Sciences

Advanced
June  2009, 2(2): 301-314. doi: 10.3934/dcdss.2009.2.301

A note on universality in multidimensional symbolic dynamics

Michael Hochman 1,

1. 

Department of Mathematics, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544, United States

Received  February 2008 Revised  September 2008 Published  April 2009

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: Topological dynamics., Shift of finite type, Decidability, Cellular automaton, Medvedev degree.
Mathematics Subject Classification: 37B15, 37B40, 37B50, 94A17, 03D4.
Citation: Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 301-314. doi: 10.3934/dcdss.2009.2.301
[1]

Petr Kůrka. On the measure attractor of a cellular automaton. Conference Publications, 2005, 2005 (Special) : 524-535. doi: 10.3934/proc.2005.2005.524
[2]

Mike Boyle, Sompong Chuysurichay. The mapping class group of a shift of finite type. Journal of Modern Dynamics, 2018, 13: 115-145. doi: 10.3934/jmd.2018014
[3]

Gelasio Salaza, Edgardo Ugalde, Jesús Urías. Master--slave synchronization of affine cellular automaton pairs. Discrete & Continuous Dynamical Systems, 2005, 13 (2) : 491-502. doi: 10.3934/dcds.2005.13.491
[4]

Akane Kawaharada. Singular function emerging from one-dimensional elementary cellular automaton Rule 150. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021125
[5]

James Kingsbery, Alex Levin, Anatoly Preygel, Cesar E. Silva. Dynamics of the $p$-adic shift and applications. Discrete & Continuous Dynamical Systems, 2011, 30 (1) : 209-218. doi: 10.3934/dcds.2011.30.209
[6]

Sébastien Guisset. Angular moments models for rarefied gas dynamics. Numerical comparisons with kinetic and Navier-Stokes equations. Kinetic & Related Models, 2020, 13 (4) : 739-758. doi: 10.3934/krm.2020025
[7]

Chris Good, Sergio Macías. What is topological about topological dynamics?. Discrete & Continuous Dynamical Systems, 2018, 38 (3) : 1007-1031. doi: 10.3934/dcds.2018043
[8]

Yusra Bibi Ruhomally, Muhammad Zaid Dauhoo, Laurent Dumas. A graph cellular automaton with relation-based neighbourhood describing the impact of peer influence on the consumption of marijuana among college-aged youths. Journal of Dynamics & Games, 2021, 8 (3) : 277-297. doi: 10.3934/jdg.2021011
[9]

Marc Chamberland, Victor H. Moll. Dynamics of the degree six Landen transformation. Discrete & Continuous Dynamical Systems, 2006, 15 (3) : 905-919. doi: 10.3934/dcds.2006.15.905
[10]

Marcelo Sobottka. Right-permutative cellular automata on topological Markov chains. Discrete & Continuous Dynamical Systems, 2008, 20 (4) : 1095-1109. doi: 10.3934/dcds.2008.20.1095
[11]

Le Yin, Ioannis Sgouralis, Vasileios Maroulas. Topological reconstruction of sub-cellular motion with Ensemble Kalman velocimetry. Foundations of Data Science, 2020, 2 (2) : 101-121. doi: 10.3934/fods.2020007
[12]

Marc Henrard. Homoclinic and multibump solutions for perturbed second order systems using topological degree. Discrete & Continuous Dynamical Systems, 1999, 5 (4) : 765-782. doi: 10.3934/dcds.1999.5.765
[13]

Anna Capietto, Walter Dambrosio. A topological degree approach to sublinear systems of second order differential equations. Discrete & Continuous Dynamical Systems, 2000, 6 (4) : 861-874. doi: 10.3934/dcds.2000.6.861
[14]

Jian Lu, Huaiyu Jian. Topological degree method for the rotationally symmetric $L_p$-Minkowski problem. Discrete & Continuous Dynamical Systems, 2016, 36 (2) : 971-980. doi: 10.3934/dcds.2016.36.971
[15]

Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete & Continuous Dynamical Systems, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191
[16]

Bernard Host, Alejandro Maass, Servet Martínez. Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete & Continuous Dynamical Systems, 2003, 9 (6) : 1423-1446. doi: 10.3934/dcds.2003.9.1423
[17]

Purshottam Narain Agrawal, Şule Yüksel Güngör, Abhishek Kumar. Better degree of approximation by modified Bernstein-Durrmeyer type operators. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021024
[18]

Roger Metzger, Carlos Arnoldo Morales Rojas, Phillipe Thieullen. Topological stability in set-valued dynamics. Discrete & Continuous Dynamical Systems - B, 2017, 22 (5) : 1965-1975. doi: 10.3934/dcdsb.2017115
[19]

Philipp Gohlke, Dan Rust, Timo Spindeler. Shifts of finite type and random substitutions. Discrete & Continuous Dynamical Systems, 2019, 39 (9) : 5085-5103. doi: 10.3934/dcds.2019206
[20]

Bing Li, Tuomas Sahlsten, Tony Samuel. Intermediate $\beta$-shifts of finite type. Discrete & Continuous Dynamical Systems, 2016, 36 (1) : 323-344. doi: 10.3934/dcds.2016.36.323

2020 Impact Factor: 2.425

Tools

Metrics

  • PDF downloads (65)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences