"Complexity, information, and incompleteness: a critical examination of algorithmic information theory"

Abstract

Algorithmic Information Theory, or the Theory of Kolmogorov Complexity, is a highly influential approach in theoretical computer science. It is widely known especially about its special incompleteness and undecidability results due to Gregory Chaitin. These are often presented as dramatic extensions of Gödel's theorem, or even the strongest possible incompleteness and undecidability results. It is also claimed that they explain why incompleteness really occurs. I shall discuss critically such interpretations and argue that the relevance and strength of these results has been highly exaggerated.

http://www.helsinki.fi/collegium/eng/Raatikainen/raatikainen.htm