Serge Grigorieff (LIAFA, Université Paris 7)

La complexite syntaxique des programmes basee sur leur seule longueur donne lieu a une theorie, developpee par Kolmogorov en 1964, qui permet d’etablir une mesure du caractere aleatoire d’un objet fini. Dans le cas des objets infinis, Martin-Lof a introduit une effectivisation des notions de theorie de la mesure conduisant a une famille d’objets ayant toutes les proprietes permettant de les declarer aleatoires. Cette famille peut aussi se caracteriser par une variante de la complexite de Kolmogorov.