Computability, Noncomputability, and Hyperbolic Systems

2011/12/30 by Daniel S. Graça, Ning Zhong, Graca, Daniel S. +3 · 1 citation
Computer Science · Mathematics · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1201.0164

openalex publication_date 2011/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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. We show that (i) locally these manifolds can be computed, but (ii) globally they cannot (though we prove they are semi-computable). 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.

Citations

• On the definitions of computable real continuous functions
• On Computable Numbers, with an Application to the Entscheidungsproblem

Cited by

• Computability of Julia sets for complex Hénon maps: The role of attracting and neutral cycles

Related

• On computability of equilibrium states
• On the shifts of stable and unstable manifolds of a hyperbolic cycle under perturbation
• An analytic system with a computable hyperbolic sink whose basin of attraction is non-computable
• A geometric criterion for the existence of chaos based on periodic orbits in continuous-time autonomous systems
• C¹ invariant, stable and inertial manifolds for non-autonomous dynamical systems