Computational Dynamical Systems

• URL: http://arxiv.org/abs/2409.12179v1
• Date: Wed, 18 Sep 2024 17:51:48 GMT
• Title: Computational Dynamical Systems
• Authors: Jordan Cotler, Semon Rezchikov,
• Abstract summary: We give definitions for what it means for a smooth dynamical system to simulate a Turing machine. We show that 'chaotic' dynamical systems and 'integrable' dynamical systems cannot robustly simulate universal Turing machines. 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'
• Score: 0.6138671548064356
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• AI-Lorenz: A physics-data-driven framework for black-box and gray-box identification of chaotic systems with symbolic regression [2.07180164747172]
  We develop a framework that learns mathematical expressions modeling complex dynamical behaviors. We train a small neural network to learn the dynamics of a system, its rate of change in time, and missing model terms. This, in turn, enables us to predict the future evolution of the dynamical behavior.
  arXiv  Detail & Related papers  (2023-12-21T18:58:41Z)
• Data driven modeling for self-similar dynamics [1.0790314700764785]
  We introduce a multiscale neural network framework that incorporates self-similarity as prior knowledge. For deterministic dynamics, our framework can discern whether the dynamics are self-similar. Our method can identify the power law exponents in self-similar systems.
  arXiv  Detail & Related papers  (2023-10-12T12:39:08Z)
• Exploring Complex Dynamical Systems via Nonconvex Optimization [0.0]
  We present an alternative, optimization-driven approach using tools from machine learning. We apply this approach to a novel, fully-optimizable, reaction-diffusion model which incorporates complex chemical reaction networks. This allows us to systematically identify new states and behaviors, including pattern formation, dissipation-maximizing nonequilibrium states, and replication-like dynamical structures.
  arXiv  Detail & Related papers  (2023-01-03T01:35:39Z)
• Learning Individual Interactions from Population Dynamics with Discrete-Event Simulation Model [9.827590402695341]
  We will explore the possibility of learning a discrete-event simulation representation of complex system dynamics. Our results show that the algorithm can data-efficiently capture complex network dynamics in several fields with meaningful events.
  arXiv  Detail & Related papers  (2022-05-04T21:33:56Z)
• Capturing Actionable Dynamics with Structured Latent Ordinary Differential Equations [68.62843292346813]
  We propose a structured latent ODE model that captures system input variations within its latent representation. Building on a static variable specification, our model learns factors of variation for each input to the system, thus separating the effects of the system inputs in the latent space.
  arXiv  Detail & Related papers  (2022-02-25T20:00:56Z)
• Constructing Neural Network-Based Models for Simulating Dynamical Systems [59.0861954179401]
  Data-driven modeling is an alternative paradigm that seeks to learn an approximation of the dynamics of a system using observations of the true system. This paper provides a survey of the different ways to construct models of dynamical systems using neural networks. In addition to the basic overview, we review the related literature and outline the most significant challenges from numerical simulations that this modeling paradigm must overcome.
  arXiv  Detail & Related papers  (2021-11-02T10:51:42Z)
• DySMHO: Data-Driven Discovery of Governing Equations for Dynamical Systems via Moving Horizon Optimization [77.34726150561087]
  We introduce Discovery of Dynamical Systems via Moving Horizon Optimization (DySMHO), a scalable machine learning framework. DySMHO sequentially learns the underlying governing equations from a large dictionary of basis functions. Canonical nonlinear dynamical system examples are used to demonstrate that DySMHO can accurately recover the governing laws.
  arXiv  Detail & Related papers  (2021-07-30T20:35:03Z)
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms [74.17312533172291]
  We describe a method for mapping any finite nonlinear dynamical system to an infinite linear dynamical system (embedding) We then explore an approach for approximating the resulting infinite linear system with finite linear systems (truncation)
  arXiv  Detail & Related papers  (2020-12-12T00:01:10Z)
• Multiscale Simulations of Complex Systems by Learning their Effective Dynamics [10.52078600986485]
  We present a systematic framework that bridges large scale simulations and reduced order models to Learn the Effective Dynamics. LED provides a novel potent modality for the accurate prediction of complex systems. LED is applicable to systems ranging from chemistry to fluid mechanics and reduces computational effort by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2020-06-24T02:35:51Z)
• Euclideanizing Flows: Diffeomorphic Reduction for Learning Stable Dynamical Systems [74.80320120264459]
  We present an approach to learn such motions from a limited number of human demonstrations. The complex motions are encoded as rollouts of a stable dynamical system. The efficacy of this approach is demonstrated through validation on an established benchmark as well demonstrations collected on a real-world robotic system.
  arXiv  Detail & Related papers  (2020-05-27T03:51:57Z)
• Learning Stable Deep Dynamics Models [91.90131512825504]
  We propose an approach for learning dynamical systems that are guaranteed to be stable over the entire state space. We show that such learning systems are able to model simple dynamical systems and can be combined with additional deep generative models to learn complex dynamics.
  arXiv  Detail & Related papers  (2020-01-17T00:04:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.