Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.07288 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915924550877184 |
|---|---|
| author | Bruera, Renzo Cardona, Robert Miranda, Eva Peralta-Salas, Daniel Salo, Ville |
| author_facet | Bruera, Renzo Cardona, Robert Miranda, Eva Peralta-Salas, Daniel Salo, Ville |
| contents | 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 "branching Turing machines" (which includes most of the known examples of universal Turing machines) has positive topological entropy. Motivated by the recent construction of Turing complete Euler flows, we deduce that any Turing complete dynamics with a continuous encoding that simulates a universal branching machine is chaotic. On the other hand, we show that, unexpectedly, universal Turing machines with zero topological entropy (and even zero speed) can be constructed, unveiling the independence of chaos and universality at the symbolic level. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07288 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Topological entropy of Turing complete dynamics Bruera, Renzo Cardona, Robert Miranda, Eva Peralta-Salas, Daniel Salo, Ville Dynamical Systems Computational Complexity 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 "branching Turing machines" (which includes most of the known examples of universal Turing machines) has positive topological entropy. Motivated by the recent construction of Turing complete Euler flows, we deduce that any Turing complete dynamics with a continuous encoding that simulates a universal branching machine is chaotic. On the other hand, we show that, unexpectedly, universal Turing machines with zero topological entropy (and even zero speed) can be constructed, unveiling the independence of chaos and universality at the symbolic level. |
| title | Topological entropy of Turing complete dynamics |
| topic | Dynamical Systems Computational Complexity |
| url | https://arxiv.org/abs/2404.07288 |