Let x be a binary string. The minimal description of x, written d(x), is the shortest string M, w where TM M on input w halts with x on its tape. If several such strings exist, select the lexicographically first among them. The descriptive complexity, or Kolmogorov complexity, of x, written K(x), is K(x) = |d(x)|. Show that the function K(x) is not a computable function.

HINTS: If K is a computable function, there is some TM which computes it. That TM can be used to find strings of large complexity. Try to design a program which outputs complex strings but which contradicts their supposed complexity, and even contradicting the supposed complexity of a single string suffices.