Résumé de la conférence de L. Bienvenu - Journée Annuelle 2011

Théorie effective de l'aléatoire
par Laurent Bienvenu (LIAFA, Université Paris Diderot)

Imaginons que l'on tire dix mille fois à pile ou face avec une pièce de monnaie équilibrée, et que l'on obtienne dix mille fois "face''. Bien que ce résultat ait a priori la même probabilité d'occurrence que tout autre, il est raisonnable d'affirmer a posteriori que ce dernier ne semble pas aléatoire, ou encore qu'il est fortement atypique. Comment formaliser mathématiquement cette intuition?
 
C'est à ce problème que Kolmogorov et Chaitin ont apporté une solution dans les années 1960, grâce à la notion connue aujourd'hui sous le nom de complexité de Kolmogorov, qui mesure la quantité d'aléatoire dans les objets discrets finis et dont la définition fait appel à la théorie de la calculabilité. Intuitivement, la complexité de Kolmogorov d'un objet fini discret est la taille du plus court programme permettant de la générer. Bien que non-calculable, la complexité de Kolmogorov permet de développer une théorie très élégante de l'aléatoire pour les objets finis, qui est de surcroît riche d'applications.
 
Je présenterai les grandes lignes de cette théorie, et expliquerai comment elle peut s'étendre aux objets infinis, grâce aux travaux de Martin-Löf, Levin, Schnorr et bien d'autres, aboutissant à une formalisation précise de la notion d'objet infini aléatoire, que l'on nomme "aléatoire au sens de Martin-Löf". Nous verrons que cette définition est robuste, en présentant un certain nombre de définitions équivalentes résultant de points de vue différents (théorie des jeux, analyse calculable, etc.). Si le temps le permet, nous donnerons un panorama des thématiques de recherche actuelles dans ce domaine, notamment l'étude des suites "anti-aléatoires" (appelées aussi K-triviales), qui présentent des propriétés calculatoires tout-à-fait surprenantes, et des liens avec l'analyse réelle et les systèmes dynamiques.