Séminaire LIFL

Hector Zenil, Université de Paris 1 et LIFL
Jeudi 31 Janvier 2008, 14H00
Amphi Turing, Bat M3

Titre : Complexité de Kolmogorov des séquences courtes.

Résumé : Une caractéristique contraignante de la complexité algorithmique ou complexité de Kolmogorov, est qu'elle n'est pas calculable en général, ce qui limite son domaine d'application. En pratique, on peut obtenir des approximations grâce à des méthodes de compression. Cependant les performances de ces méthodes de compression s'écroulent quand il s'agit des séquences vraiment courtes. Courtes, par exemple, relativement à la taille de la machine universelle de référence.
Nous proposons une méthode qui permettrait formuler une définition stable d'une mesure de Kolmogorov K(s) "naturelle" via la mesure de probabilité algorithmique m(s) définie par Leonid Levin. Si on fait fonctionner une machine universelle en lui donnant un programme au hasard et une entrée quelconque, alors elle produit la suite s avec la probabilité m(s). Cela suggère qu'on pourrait donner un sens stable à m(s) et donc à K(s), même pour des séquences s petites, en procédant expérimentalement : (a) on fait fonctionner des mécanismes de calculs de manière systématique (machines de Turing, automates cellulaires, etc.) pour produire des suites et puis (b) on observe quelles sont les distributions de probabilité obtenues.