Erik Thormarker: Chaitin's incompleteness theorem

Abstract:

In this thesis we look at an incompleteness result by Gregory Chaitin. Roughly Chaitin's result tells us that under certain assumptions on a formal system there exists a constant c such that no statements of the form "C(n)>c", where C(n) is the Kolmogorov complexity of a natural number n, are provable in that formal system. After Chaitin's result there has been a discussion concerning what the theorem actually implies, we will give a summary of this discussion. We also compare Chaitin's result to Gödel's famous incompleteness theorems and discuss if Chaitin's result can be said to be as strong as Gödel's result. Finally we will look at some  developments in recent years with a connection to Chaitin's result.