Computability, noncomputability, and hyperbolic systems

In this paper we study the computability of the stable and unstable manifolds of a hyperbolic equilibrium point. These manifolds are the essential feature which characterizes a hyperbolic system, having many applications in physical sciences and other fields. We show that (i) locally these manifolds can be computed, but (ii) globally they cannot, since their degree of computational unsolvability lies on the second level of the Borel hierarchy. We also show that Smale’s horseshoe, the first example of a hyperbolic invariant set which is neither an equilibrium point nor a periodic orbit, is computable.