2
$\begingroup$

This paper claims to have a proof of Godel's Second Incompleteness Theorem using Kolmogorov Complexity: http://www.ams.org/notices/201011/rtx101101454p.pdf

As far as I can tell, it seems to assume that Kolmogorov complexity (over some language or Turing Machine) is definable in Peano Arithmetic, and refers to concepts like the Godel Number of the statement "K(x) > N", that is, the Kolmogorov Complexity of the number x is greater than N.

Is it true that Kolmogorov complexity is definable in a theory like PA?

$\endgroup$
5
$\begingroup$

Yes, Kolmogorov complexity is definable in Peano Arithmetic. The key to this and lots of similar definability results for PA is that one can define, in the language of PA, a system for coding finite sequences of natural numbers by single natural numbers, and one can prove in PA the basic combinatorial properties of (encoded) finite sequences (for example, that every two sequences have a concatenation, which has the expected length and the expected components). Repeating this, one can also deal, in PA, with finite sequences of finite sequences of natural numbers,etc. Once one sees how to formalize statements about finite sequences, it is routine, though rather tedious, to write down the basic definitions of computability theory, up to and including (and beyond) the notion of Kolmogorov complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.