Topological entropy of Turing complete dynamics
This addresses a foundational problem in dynamical systems and computability theory by clarifying the connection between computational universality and chaotic behavior.
The paper investigates the relationship between Turing completeness and topological entropy in dynamical systems, proving that a natural class of universal Turing machines has positive topological entropy while constructing counterexamples with zero topological entropy, revealing that chaos and universality are independent at the symbolic level.
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.