Computational Dynamical Systems

We study the computational complexity theory of smooth, finite-dimensional dynamical systems. Building off of previous work, we give definitions for what it means for a smooth dynamical system to simulate a Turing machine. We then show that ‘chaotic’ dynamical systems (more precisely, Axiom A systems) and ‘integrable’ dynamical systems (more generally, measure-preserving systems) cannot robustly simulate univer-sal Turing machines, although such machines can be robustly simulated by other kinds of dynamical systems. Subsequently, we show that any Turing machine that can be encoded into a structurally stable one-dimensional dynamical system must have a decidable halting problem, and moreover an explicit time complexity bound in instances where it does halt. More broadly, our work elucidates what it means for one ‘machine’ to simulate another, and emphasizes the necessity of defining low-complexity 'encoders' and 'decoders' to translate between the dynamics of the simulation and the system being simulated. We highlight how the notion of a computational dynamical system leads to questions at the intersection of computational complexity theory, dynamical systems theory, and real algebraic geometry.

Authors

• Jordan Cotler
• Semon Rezchikov

Keywords

• Geometry
• Computer science
• Turing machines
• Buildings
• Decoding
• Dynamical systems
• Time complexity
• System Dynamics
• Dynamics Simulations
• Computational Complexity
• Computer System
• Integrable
• Universal Machine
• Complexity Theory
• Computational Theory
• Turing Machine
• Finite-dimensional Systems
• Continuous System
• Examples Of Systems
• State Machine
• Open Set
• Shift Operator
• Configuration Space
• Chaotic System
• Discrete Space
• Discrete System
• Continuous Dynamical Systems
• Topological Transition
• Diffeomorphism
• Open Subset
• Hamiltonian System
• Computational Robustness
• Lyapunov Exponent
• Continuous-time Systems
• Smooth Manifold
• Continuum Mechanics
• computability