preprint · arXiv (Cornell University) · 2024

Topological entropy of Turing complete dynamics (with an appendix by Ville Salo)

Renzo Bruera, Robert Cardona, Eva Miranda, Daniel Peralta‐Salas

Cited by 0Open access

Abstract

We explore the relationship between Turing completeness and topological entropy of dynamical systems. We first prove that a natural class of Turing machines that we call "regular Turing machines" (which includes most of the examples of universal Turing machines) has positive topological entropy. We deduce that any Turing complete dynamics with a continuous encoding that simulates a universal machine in this class is chaotic. This applies to our previous constructions of Turing complete area-preserving diffeomorphisms of the disk and 3D stationary Euler flows. The article concludes with an appendix written by Ville Salo that introduces a method to construct universal Turing machines that are not regular and have zero topological entropy.

Cite this paper

APA 7

Bruera, R., Cardona, R., Miranda, E., & Peralta‐Salas, D. (2024). Topological entropy of Turing complete dynamics (with an appendix by Ville Salo). arXiv (Cornell University). https://doi.org/10.48550/arxiv.2404.07288

MLA 9

Bruera, Renzo, et al. “Topological entropy of Turing complete dynamics (with an appendix by Ville Salo).” arXiv (Cornell University), 2024, https://doi.org/10.48550/arxiv.2404.07288.

Chicago

Bruera, Renzo, Robert Cardona, Eva Miranda, and Daniel Peralta‐Salas. 2024. “Topological entropy of Turing complete dynamics (with an appendix by Ville Salo).” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2404.07288.

Harvard

Bruera, R. et al. (2024) ‘Topological entropy of Turing complete dynamics (with an appendix by Ville Salo)’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2404.07288.

BibTeX

@misc{bruera2024topological,
  title = {{Topological entropy of Turing complete dynamics (with an appendix by Ville Salo)}},
  author = {Bruera, Renzo and Cardona, Robert and Miranda, Eva and Peralta‐Salas, Daniel},
  journal = {arXiv (Cornell University)},
  year = {2024},
  doi = {10.48550/arxiv.2404.07288}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.