Noise vs computational intractability in dynamics

Mark Braverman, Alexander Grigo, Cristobal Rojas

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

8 Citas (Scopus)


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.

Idioma originalInglés
Título de la publicación alojadaITCS 2012 - Innovations in Theoretical Computer Science Conference
Número de páginas14
EstadoPublicada - 2012
Evento3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, Estados Unidos
Duración: 8 ene. 201210 ene. 2012

Serie de la publicación

NombreITCS 2012 - Innovations in Theoretical Computer Science Conference


Otros3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012
País/TerritorioEstados Unidos
CiudadCambridge, MA

Áreas temáticas de ASJC Scopus

  • Teoría computacional y matemáticas


Profundice en los temas de investigación de 'Noise vs computational intractability in dynamics'. En conjunto forman una huella única.

Citar esto