Computability, randomness and ergodic theory on metric spaces

Calculabilité, aléatoire et théorie ergodique sur les espaces métriques

Mathieu Hoyrup (1)

1 LIENS - Laboratoire d'informatique de l'école normale supérieure

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 K1 using an invariant probability measure, the other K2 inspired from the topological approach. We prove that the complexity K1 of the orbits of random points equal the measure-theoretical entropy of the system, that the supremum of the complexity K2 among all the orbits is the topological entropy, and that K1 and K2 coincide on random points. This work improves results established by Brudno and White.

L'objectif général de cette thèse est d'étudier les notions d'aléatoire et d'information algorithmiques - jusqu'ici restreints aux espaces symboliques - sur des espaces plus généraux, précisément les espaces métriques calculables, et d'appliquer ces notions à la théorie des systèmes dynamiques. Les principaux apports sont : (1) le développement d'un cadre robuste pour l'étude d'objets mathématiques (mesures de probabilité, systèmes dynamiques et leurs modèles symboliques) d'un point de vue algorithmique, notamment l'introduction et l'étude détaillée des treillis d'énumération effective; (2) l'extension de l'aléatoire algorithmique aux espaces métriques calculables, améliorant ainsi l'extension menée par Gacs qui imposait une condition supplémentaire à l'espace, et l'étude de quelques notions des probabilités classiques du point de vue de l'aléatoire; (3) un apport à la théorie des systèmes dynamiques, établissant des relations entre l'aléatoire algorithmique et l'aléatoire dynamique. Nous étudions notamment deux notions de complexité algorithmique des orbites, l'une K1 utilisant la mesure, l'autre K2 inspirée du point de vue topologique. Nous montrons que la complexité K1 des orbites partant des points aléatoires est l'entropie du système au sens de la mesure, que la borne supérieure des complexités K2 des orbites est l'entropie topologique, et que K1 et K2 coïncident pour les points aléatoires. Ce travail enrichit les résultats de Brudno et White.

Mots clés: Algorithmic randomness; universal test; computable measure; Kolmogorov complexity; algorithmic complexity of orbits; ergodic theorems; almost computable function

Mots clés: Aélatoire algorithmique; test universel; mesure calculable; complexité de Kolmogorov; complexité algorithmique des orbites; théorèmes ergodiques

Domaines: Mathématiques [math]

Mathieu Hoyrup. Calculabilité, aléatoire et théorie ergodique sur les espaces métriques. Mathématiques [math]. Université Paris-Diderot - Paris VII, 2008. Français. ⟨NNT : ⟩. ⟨tel-00322776⟩