Noise versus computational intractability in dynamics

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 shall discuss 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.

Original languageEnglish (US)
Title of host publicationThe Nature of Computation
Subtitle of host publicationLogic, Algorithms, Applications - 9th Conference on Computability in Europe, CiE 2013, Proceedings
Number of pages1
DOIs
StatePublished - Jul 26 2013
Event9th Conference on Computability in Europe - The Nature of Computation: Logic, Algorithms, Applications, CiE 2013 - Milan, Italy
Duration: Jul 1 2013Jul 5 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7921 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th Conference on Computability in Europe - The Nature of Computation: Logic, Algorithms, Applications, CiE 2013
CountryItaly
CityMilan
Period7/1/137/5/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Noise versus computational intractability in dynamics'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M. (2013). Noise versus computational intractability in dynamics. In The Nature of Computation: Logic, Algorithms, Applications - 9th Conference on Computability in Europe, CiE 2013, Proceedings (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7921 LNCS). https://doi.org/10.1007/978-3-642-39053-1_4