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]
