Effective symbolic dynamics, random points, statistical behavior, complexity and entropy

We consider the dynamical behavior of Martin-Löf random points in dynamical systems over metric spaces with a computable dynamics and a computable invariant measure. We use computable partitions to define a sort of effective symbolic model for the dynamics. Through this construction, we prove that s...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2010, Vol.208 (1), p.23-41
Main Authors: Galatolo, Stefano, Hoyrup, Mathieu, Rojas, Cristóbal
Format: Article
Language:English
Subjects:
Algorithmic randomness
Applied sciences
Computable partition
Computer Science
Computer science
control theory
systems
Dynamical Systems
Effective symbolic dynamics
Entropy
Exact sciences and technology
General topology
Global analysis, analysis on manifolds
Information Theory
Kolmogorov–Chaitin complexity
Mathematical analysis
Mathematics
Measure and integration
Miscellaneous
Orbit complexity
Sciences and techniques of general use
Theoretical computing
Topology. Manifolds and cell complexes. Global analysis and analysis on manifolds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the dynamical behavior of Martin-Löf random points in dynamical systems over metric spaces with a computable dynamics and a computable invariant measure. We use computable partitions to define a sort of effective symbolic model for the dynamics. Through this construction, we prove that such points have typical statistical behavior (the behavior which is typical in the Birkhoff ergodic theorem) and are recurrent. We introduce and compare some notions of complexity for orbits in dynamical systems and prove: (i) that the complexity of the orbits of random points equals the Kolmogorov–Sinaï entropy of the system, (ii) that the supremum of the complexity of orbits equals the topological entropy.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2009.05.001