Thèse de Hector Zenil

Une approche expérimentale à la théorie algorithmique de la complexité

Une caractéristique contraignante de la complexité de Kolmogorov-Chaitin (dénotée par K) est qu'elle n'est pas calculable à cause du problème de l'arrêt, ce qui limite son domaine d'application. Une autre critique concerne la dépendance de K à un langage ou une machine de Turing universelle particulière, surtout pour les suites assez courtes, par exemple, plus courtes que les longueurs typiques des compilateurs des langages de programmation. En pratique, on peut obtenir une approximation de K(s), grâce à des méthodes de compression. Mais les performances de ces méthodes de compression s'écroulent quand il s'agit des suites courtes pour lesquelles approcher K(s) ne fonctionne pas à cause des longueurs déjà trop courts. On présente une approche empirique pour surmonter ce problème. Nous proposons une méthode alternative qui permet d'envisager une définition plus stable de la complexité de Kolmogorov-Chaitin K(s) via la mesure de probabilité algorithmique de Solomonoff-Levin m(s) (la probabilité de produire s). L'idée est de faire fonctionner une machine universelle en lui donnant un programme au hasard pour calculer expérimentalement la probabilité m(s), pour ensuite évaluer numériquement K. La méthode consiste à : (a) faire fonctionner des machines de de façon systématique pour produire des suites (b) observer quelles sont les distributions de probabilité obtenues et puis (c) obtenir K(s) à partir de m(s) par moyen du théorème de codage de Levin-Chaitin

Jury

Thèse de l'équipe SMAC soutenue le 21/06/2011