2023/11/26 by Cristóbal Rojas, Mathieu Sablik, Rojas, Cristobal +1
Computer Science · Mathematics · #37B02 #37B10 #68Q17 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.2311.15234
openalex publication_date 2023/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the computational problem of rigorously describing the asymptotic behaviour of topological dynamical systems up to a finite but arbitrarily small pre-specified error. More precisely, we consider the limit set of a typical orbit, both as a spatial object (attractor set) and as a statistical distribution (physical measure), and prove upper bounds on the computational resources of computing descriptions of these objects with arbitrary accuracy. We also study how these bounds are affected by different dynamical constrains and provide several examples showing that our bounds are sharp in general. In particular, we exhibit a computable interval map having a unique transitive attractor with Cantor set structure supporting a unique physical measure such that both the attractor and the measure are non computable.