Hostname: page-component-55f67697df-gmt7q Total loading time: 0 Render date: 2025-05-10T01:40:29.664Z Has data issue: false hasContentIssue false
  • English
  • Français

Effective dynamical systems beyond dimension zero and factors of SFTs

Part of: Special aspects of infinite or finite groups Computability and recursion theory Topological dynamics

Published online by Cambridge University Press:  11 October 2024

SEBASTIÁN BARBIERI Open the ORCID record for SEBASTIÁN BARBIERI [Opens in a new window] ,
NICANOR CARRASCO-VARGAS Open the ORCID record for NICANOR CARRASCO-VARGAS [Opens in a new window]  and
CRISTÓBAL ROJAS Open the ORCID record for CRISTÓBAL ROJAS [Opens in a new window]
SEBASTIÁN BARBIERI*
Affiliation:
Departamento de Matemática y Ciencia de la Computación, Universidad de Santiago de Chile, Santiago, Chile
NICANOR CARRASCO-VARGAS
Affiliation:
Departamento de Matemática, Pontificia Universidad Católica de Chile, Santiago, Chile (e-mail: [email protected])
CRISTÓBAL ROJAS
Affiliation:
Instituto de Ingeniería Matemática y Computacional, Pontificia Universidad Católica de Chile, Santiago, Chile (e-mail: [email protected])
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Using tools from computable analysis, we develop a notion of effectiveness for general dynamical systems as those group actions on arbitrary spaces that contain a computable representative in their topological conjugacy class. Most natural systems one can think of are effective in this sense, including some group rotations, affine actions on the torus and finitely presented algebraic actions. We show that for finitely generated and recursively presented groups, every effective dynamical system is the topological factor of a computable action on an effectively closed subset of the Cantor space. We then apply this result to extend the simulation results available in the literature beyond zero-dimensional spaces. In particular, we show that for a large class of groups, many of these natural actions are topological factors of subshifts of finite type.

Keywords

computable analysissymbolic dynamicssimulationtopological factors of SFTs

MSC classification

Primary: 37B10: Symbolic dynamics 03D78: Computation over the reals
Secondary: 20F10: Word problems, other decision problems, connections with logic and automata
Type
Original Article
Information
Ergodic Theory and Dynamical Systems , Volume 45 , Issue 5 , May 2025 , pp. 1329 - 1369
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Aubrun, N., Barbieri, S. and Sablik, M.. A notion of effectiveness for subshifts on finitely generated groups. Theoret. Comput. Sci. 661 (2017), 35–55.Google Scholar
Aubrun, N. and Sablik, M.. Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Appl. Math. 126 (2013), 35–63.Google Scholar
Barbieri, S.. A geometric simulation theorem on direct products of finitely generated groups. Discrete Anal. 9 (2019), 25.Google Scholar
Barbieri, S. and Sablik, M.. A generalization of the simulation theorem for semidirect products. Ergod. Th. & Dynam. Sys. 39(12) (2019), 3185–3206.Google Scholar
Barbieri, S., Sablik, M. and Salo, V.. Groups with self-simulable zero-dimensional dynamics. Preprint, 2021, arXiv:2104.05141.Google Scholar
Barbieri, S., Sablik, M. and Salo, V.. Soficity of free extensions of effective subshifts. Discrete Continuous Dyn. Syst. doi: 10.3934/dcds.2024125. Published online September 2024.CrossRefGoogle Scholar
Berger, R.. The undecidability of the domino problem. Mem. Amer. Math. Soc. 66 (1966), 72pp.Google Scholar
Birman, J. S. and Brendle, T. E.. Braids: a survey. Handbook of Knot Theory. Ch. 2. Ed. Menasco, W. and Thistlethwaite, M.. Elsevier Science, Amsterdam, 2005, pp. 19–103.CrossRefGoogle Scholar
Bowen, R.. On Axiom A Diffeomorphisms (CBMS Regional Conference Series in Mathematics, 35). American Mathematical Society, Providence, RI, 1978.Google Scholar
Brattka, V. and Hertling, P.. Handbook of Computability and Complexity in Analysis. Springer Nature, Cham, 2021.Google Scholar
Cannon, J. W., Floyd, W. J. and Parry, W. R.. Introductory notes on Richard Thompson’s groups. Enseign. Math. (2) 42(3–4) (1996), 215–256.Google Scholar
Carrasco-Vargas, N.. Translation-like actions by ${\mathbb{Z}}$ , the subgroup membership problem, and Medvedev degrees of effective subshifts. Groups Geom. Dyn. doi: 10.4171/GGD/817. Published online 8 August 2024.CrossRefGoogle Scholar
Ceccherini-Silberstein, T. and Coornaert, M.. Cellular Automata and Groups. Springer, Berlin, 2009.Google Scholar
Cenzer, D., Dashti, S. A. and King, J. L. F.. Computable symbolic dynamics. MLQ Math. Log. Q. 54(5) (2008), 460–469.Google Scholar
Chung, N.-P. and Li, H.. Homoclinic groups, IE groups, and expansive algebraic actions. Invent. Math. 199(3) (2014), 805–858.Google Scholar
Coornaert, M. and Papadopoulos, A.. Symbolic Dynamics and Hyperbolic Groups (Lecture Notes in Mathematics, 1539), 1993 edition. Springer, Berlin, 2006.Google Scholar
Durand, B., Romashchenko, A. and Shen, A.. Effective closed subshifts in 1D can be implemented in 2D. Fields of Logic and Computation. Ed. Blass, A., Dershowitz, N. and Reisig, W.. Springer Nature, Heidelberg, 2010, pp. 208–226.Google Scholar
Hadamard, J.. Les surfaces à courbures opposées et leurs lignes géodésiques. J. Math. Pures Appl. (9) 4 (1898), 27–74.Google Scholar
Hanf, W.. Nonrecursive tilings of the plane. I. J. Symb. Log. 39(2) (1974), 283–285.Google Scholar
Hedlund, G. A.. Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory 3(4) (1969), 320–375.Google Scholar
Hedlund, G. A. and Morse, M.. Symbolic dynamics. Amer. J. Math. 60(4) (1938), 815–866.Google Scholar
Hochman, M.. On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176(1) (2009), 131–167.Google Scholar
Hochman, M. and Meyerovitch, T.. A characterization of the entropies of multidimensional shifts of finite type. Ann. of Math. (2) 171(3) (2010), 2011–2038.Google Scholar
Kerr, D. and Li, H.. Ergodic Theory. Springer International Publishing, Cham, 2016.CrossRefGoogle Scholar
Lind, D. and Schmidt, K.. Homoclinic points of algebraic ${\mathbb{Z}}^d$ -actions. J. Amer. Math. Soc. 12(4) (1999), 953–980.Google Scholar
Lind, D., Schmidt, K. and Ward, T.. Mahler measure and entropy for commuting automorphisms of compact groups. Invent. Math. 101(1) (1990), 593–629.Google Scholar
Morris, S. A.. Pontryagin Duality and the Structure of Locally Compact Abelian Groups (London Mathematical Society Lecture Note Series, 29). Cambridge University Press, Cambridge, 1977.Google Scholar
Myers, D.. Nonrecursive tilings of the plane. II. J. Symb. Log. 39(2) (1974), 286–294.CrossRefGoogle Scholar
Rettinger, R. and Weihrauch, K.. Products of effective topological spaces and a uniformly computable Tychonoff theorem. Log. Methods Comput. Sci. 9(4) (2013), article no 14.CrossRefGoogle Scholar
Robinson, R. M.. Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12 (1971), 177–209.CrossRefGoogle Scholar
Rogers, H. Jr. Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, MA, 1987.Google Scholar
Schmidt, K.. Dynamical Systems of Algebraic Origin. Birkhäuser, Basel, 1995.Google Scholar
Sipser, M.. Introduction to the Theory of Computation, 3rd edn. Wadsworth Publishing, Belmont, CA, 2012.Google Scholar
Turing, A. M.. On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. (2) 42 (1936), 230–265.Google Scholar
Wang, H.. Proving theorems by pattern recognition, II. Computation, Logic, Philosophy (Mathematics and Its Applications (China Series), 2). Springer Netherlands, Dordrecht, 1961, pp. 159–192.CrossRefGoogle Scholar