# How can I prove the languages of incompressible words is undecidable?

I have hard time understanding the proof by contradiction for the claim "$$L=\{x : K(x) \ge |x| \}$$" is undecidable ".

The proof is as follows :

M' = " On input $$n$$

1. Enumerate over all $$n$$-bit strings $$x$$ in lexicographical order
2. Simulate M on each $$x$$, where $$M$$ is the Turing machine that decides $$L$$.
3. Output first $$x$$ which $$M$$ accepts. "

Since TM $$M'$$ produced incompressible using only $$O(\log n)$$ to specify $$n$$, we can compress incompressible strings which is a contradiction.

I understood the $$M'$$ construction. However, I do not understand where exactly is the contradiction happening? According to me, $$M'$$ outputs $$x$$ which is in-compressible(ensured by TM $$M$$) but how does it is also compressible at same time?

Consider the word $$w_n$$ that is the output of $$M'$$ given input $$n$$.
Note that description of $$w_n$$ is the description of $$M'$$, whose length is some constant $$c$$, plus the description of $$n$$, whose length is $$O(\log n)$$ since we can express $$n$$ in the binary representation. So $$K(w_n)\le c + O(\log n)$$. If $$n$$ is large enough, we get $$K(w_n)\lt n = |w_n|.$$
That is a contradiction since, as you have noted, $$w_n$$ should be incompressible.
• The description of $w_n$, "the output of $M'$ given input $n$" is the sum of the description of $m'$, the description of $n$ and some string of constant length. Jul 7, 2019 at 7:45
• $c+O(\log n)$ is smaller than $n$ if $n$ is large enough since $\log n= o(n)$. Jul 7, 2019 at 7:46
• Can we say that string is compressable for smaller number of $n$ (then $O(logn)$ is needed to encode), for large values of $n$, we will need whole output $w_n$ ? Also this supports the intuition because I read somewhere that the K-complexity of majority of the strings is almost themselves. i.e $K(x)=|x|+c$ and large values are far more in number than smaller values. Jul 7, 2019 at 8:08
• Are you asking a new question or are you still on "how to understand that proof"? For what "we will need whole output $w_n$"? Jul 7, 2019 at 8:20