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 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast dynamical similarity analysis
Understanding how nonlinear dynamical systems (e.g., artificial neural networks and neural circuits) process information requires comparing their underlying dynamics at scale, across diverse architectures and large neura…
A Low-complexity Structured Neural Network to Realize States of Dynamical Systems
Data-driven learning is rapidly evolving and places a new perspective on realizing state-space dynamical systems. However, dynamical systems derived from nonlinear ordinary differential equations (ODEs) suffer from limit…
Computational EfficiencySafety of Dynamical Systems with Multiple Non-Convex Unsafe Sets Using Control Barrier Functions
This paper presents an approach to deal with safety of dynamical systems in presence of multiple non-convex unsafe sets. While optimal control and model predictive control strategies can be employed in these scenarios, t…
Model Predictive ControlRobot NavigationPhysics-Informed Solution of The Stationary Fokker-Plank Equation for a Class of Nonlinear Dynamical Systems: An Evaluation Study
The Fokker-Planck (FP) equation is a linear partial differential equation which governs the temporal and spatial evolution of the probability density function (PDF) associated with the response of stochastic dynamical sy…
Transfer LearningIf consciousness is dynamically relevant, artificial intelligence isn't conscious
We demonstrate that if consciousness is relevant for the temporal evolution of a system's states--that is, if it is dynamically relevant--then AI systems cannot be conscious. That is because AI systems run on CPUs, GPUs,…