Helsinki Collegium for Advanced Studies
University of Helsinki
Thursday, 23 September 2004, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101
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.