6 Kolmogorov Complexity Compression of a bit string x of length n involves creating a program shorter than n bits that returns x. The Kolmogorov complexity of a string K(x) is the length of shortest program that returns x(i.e the length of a maximally compressed version ofx) (a) Explain why "the smallest positive integer not definable in under 100 characters" is paradoxi cal (b) Prove that for any length n, there must be at least one bit string that cannot be compressed. (c) Imagine you had the program K, which outputs the Kolmogorov complexity of string. Design a program P that when given integer n outputs the bit string of length n with the highest Kolmogorov complexity. If there are multiple strings with the highest complexity, output the lexicographically first (i.e. the one that would come first in a dictionary (d) Suppose the program P you just wrote can be written in m bits. Show that P and by extension, K, cannot exist, for a sufficiently large input n 6 Kolmogorov Complexity Compression of a bit string x of length n involves creating a program shorter than n bits that returns x. The Kolmogorov complexity of a string K(x) is the length of shortest program that returns x(i.e the length of a maximally compressed version ofx) (a) Explain why "the smallest positive integer not definable in under 100 characters" is paradoxi cal (b) Prove that for any length n, there must be at least one bit string that cannot be compressed. (c) Imagine you had the program K, which outputs the Kolmogorov complexity of string. Design a program P that when given integer n outputs the bit string of length n with the highest Kolmogorov complexity. If there are multiple strings with the highest complexity, output the lexicographically first (i.e. the one that would come first in a dictionary (d) Suppose the program P you just wrote can be written in m bits. Show that P and by extension, K, cannot exist, for a sufficiently large input n