Very lost, need help on all parts of this question.

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 of x) (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 itsrngthtaot 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 of x) (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 itsrngthtaot 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