Laurent Bienvenu
(LIAFA, University of Paris 7)
The Axiomatic Power of Kolmogorov Complexity

A famous theorem of Chaitin shows that the Kolmogorov complexity of strings can never be proven to be high. More specifically, for every sufficiently rich, recursive and coherent theory T, T can only prove finitely many statement of the form "the Kolmogorov complexity of x is greater that of n". Using this fact, Chaitin gave an alternative proof of Gödel's first incompleteness theorem and recently, Kritchman and Raz were able, with a very ingenious argument, to give a new proof of Gödel's second incompleteness theorem. After surveying these results, we will consider the following questions: Given a base theory T (such as Peano arithmetic), how useful are the true statements of the form "the Kolmogorov complexity of x is greater that n"? Are they useful as a whole? Are they individually useful? For a given n, are they all equally useful?

[This is joint work with Andrei Romashchenko, Alexander Shen, Antoine Taveneaux and Stijn Vermeeren]