Abstract:
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.