Topological entropy of Turing complete dynamics
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _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 |