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

Panu Raatikainen

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.

Tarmo Uustalu
Last update 13.9.2004