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?


1 Answer 1


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.

  • $\begingroup$ Why is the description of wn is the description of M' ? Also when you assumed large n, why did K(wn) < n = |wn| hold? $\endgroup$
    – Prithi
    Jul 7, 2019 at 6:02
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Jul 7, 2019 at 7:45
  • $\begingroup$ $c+O(\log n)$ is smaller than $n$ if $n$ is large enough since $\log n= o(n)$. $\endgroup$
    – John L.
    Jul 7, 2019 at 7:46
  • $\begingroup$ 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. $\endgroup$
    – Prithi
    Jul 7, 2019 at 8:08
  • $\begingroup$ 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$"? $\endgroup$
    – John L.
    Jul 7, 2019 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.