TY - GEN

T1 - Noise vs computational intractability in dynamics

AU - Braverman, Mark

AU - Grigo, Alexander

AU - Rojas, Cristobal

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - invariant distributions

KW - perturbation

KW - predictability

KW - robustness

KW - uncomputability

UR - http://www.scopus.com/inward/record.url?scp=84856487179&partnerID=8YFLogxK

U2 - 10.1145/2090236.2090247

DO - 10.1145/2090236.2090247

M3 - Conference contribution

AN - SCOPUS:84856487179

SN - 9781450311151

T3 - ITCS 2012 - Innovations in Theoretical Computer Science Conference

SP - 128

EP - 141

BT - ITCS 2012 - Innovations in Theoretical Computer Science Conference

T2 - 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012

Y2 - 8 January 2012 through 10 January 2012

ER -