Speaker: Panu RAATIKAINEN, University of Helsinki, Finland
Place: Room B 101, Institute of Cybernetics, Akadeemia tee 21, Tallinn, Estonia
Time: Thursday, September 23, 2004, 14:00

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


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.