On the algorithmic descriptive complexity of attractors in topological dynamics

Autor:	Rojas, Cristobal, Sablik, Mathieu
Rok vydání:	2023
Předmět:	Mathematics - Dynamical Systems Computer Science - Computational Complexity 37B02 37B10 68Q17
Druh dokumentu:	Working Paper
Popis:	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. Comment: 25 pages, 3 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2311.15234 Zobrazit plný text záznamu View this record from Arxiv