Noise vs computational intractability in dynamics

DOI10.1145/2090236.2090247MaRDI QIDQ2826049zbMATH OpenOpenAlexWikidataFDO

Authors Mark Braverman, A. Grigo, Cristobal Rojas

Publication date 7 October 2016

Published in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.0488

zbMATH Keywords

invariant distributionsperturbationpredictabilityrobustnessuncomputability

Mathematics Subject Classification ID

Ergodicity, mixing, rates of mixing (37A25) General topics in the theory of computing (68Q01) Analysis of algorithms and problem complexity (68Q25)

Abstract: Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that describes a natural process. The first one is unaccounted-for errors, which may make the system unpredictable beyond a very limited time horizon. This is especially true for chaotic systems, where a small change in the initial conditions may cause a dramatic shift in the trajectories. The second one is Turing-completeness. By the undecidability of the Halting Problem, the long-term prospects of a system that can simulate a Turing Machine cannot be determined computationally. We investigate the interplay between these two forces -- unaccounted-for errors and Turing-completeness. We show that the introduction of even a small amount of noise into a dynamical system is sufficient to "destroy" Turing-completeness, and to make the system's long-term behavior computationally predictable. On a more technical level, we deal with long-term statistical properties of dynamical systems, as described by invariant measures. We show that while there are simple dynamical systems for which the invariant measures are non-computable, perturbing such systems makes the invariant measures efficiently computable. Thus, noise that makes the short term behavior of the system harder to predict, may make its long term statistical behavior computationally tractable. We also obtain some insight into the computational complexity of predicting systems affected by random noise.

Recommendations

• Unpredictability and undecidability in dynamical systems
• The complexity of proving chaoticity and the Church-Turing thesis
• Computation with perturbed dynamical systems
• Computability and computational complexity of the evolution of nonlinear dynamical systems
• Probability, statistics and computation in dynamical systems

Cites work

• Asymptotic calibration
• Dimension in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• scientific article; zbMATH DE number 3227613 (Why is no real title available?)
• The Complexity of Forecast Testing
• The dimensions of individual strings and sequences
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• The reproducible properties of correct forecasts
• The Well-Calibrated Bayesian
• Universal prediction

Cited in

(9)

• Towards understanding the theoretical challenges of numerical modeling of dynamical systems
• Unpredictability and undecidability in dynamical systems
• Tight space-noise tradeoffs in computing the ergodic measure
• Mutation, Sexual Reproduction and Survival in Dynamic Environments
• A Survey on Analog Models of Computation
• Existence of noise induced order, a computer aided proof
• Computation with real numbers and continuous-time dynamical systems
• On the algorithmic descriptive complexity of attractors in topological dynamics
• Efficient computation of stationary measures and the Lyapunov landscape for families of random dynamical systems with smooth additive noise

This page was built for publication: Noise vs computational intractability in dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2826049)