  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.
