Authors: Jordan Cotler, Semon Rezchikov
Abstract: 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 universal 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.
Source: http://arxiv.org/abs/2409.12179v1
