Computability, Randomness and Ergodic Theory on Metric Spaces
Mathieu Hoyrup · ResearchSpace (University of Auckland) · 2008
The general aim of this thesis is the study of the notions of algorithmic randomness and information, which are defined on symbolic spaces, to more general spaces – namely computable metric spaces – allowing their applications to dynamical systems theory. The main results are: (1) the development of a robust framework to study classical mathematical objects (probability measures, dynamical systems and their symbolic models) from an algorithmic point of view, in particular the introduction and detailed study of the structure of enumerative lattice; (2) the extension of algorithmic randomness to all computable metric spaces, improving the previous extension by Gacs which required an additive assumption on the space, and the study of some classical probability notions from the point of view of randomness; (3) contributions to dynamical systems theory, establishing relations between algorithmic and dynamical randomness. In particular, we study two notions of algorithmic orbit complexity, the one (Kμ) using an invariant probability measure, the other (K) inspired from the topological approach. We prove that the complexity Kμ of the orbits of random points equal the measure-theoretical entropy of the system, that the supremum of the complexity K among all the orbits is the topological entropy, and that Kμ and K coincide on random points. This work improves results established by Brudno and White.