Kolmogorov complexity and the second incompleteness theorem(Mathematical Incompleteness in Arithmetic)
Makoto Kikuchi · Kyoto University Research Information Repository (Kyoto University) · 1995
It is well known that Kolmogorov complexity has a close relation with G\"odel's first incompleteness theorem.In this paper, we give a new formulation of the first incompleteness theorem in terms of Kolmogorov complexity, that is a generaliza- tion of Kolmogorov's theorem, and derive a semantic proof of the second incomplete- ness theroem from it.