If x is a string let Mx be a shortest program in your favori

If x is a string, let Mx be a shortest program in your favorite programming language that outputs x then halts. The Kolmogorov complexity of a string x, denoted K(x) is defined to be the length of the binary encoding of Mx. Let n be a positive integer. Show that there exists a binary string x of length n such that K(x) >= n. Hint : Use the pigeonhole principle

Solution

(Number of binary strings of length n) = 2n and (Number of descriptions of length < n)

(Number of binary strings of length < n) = 1 + 2 + 4 + L + 2n-1 = 2n – 1

Therefore there’s at least one n-bit string that does not have a description of length < n