Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to see a proof or a sketch of a proof that the set of incompressible strings is undecidable.

Definition: Let x be a string, we say that x is c-compressible if K(x) $\leq$ |x|-c. If x is not c-compressible, we say that x is incompressible by c. K(x) represents the Kolmogorov complexity of a binary string x.

Theorem: incompressible strings of every length exist.

Proof: The number of binary strings of length n is $2^{n}$, but there exist $\displaystyle\sum\limits_{i=0}^{n-1} 2^i$=$2^{n}$-1 descriptions of lengths that is less than n. Since each description describes at most one string then there is at least one string of length n that is incompressible.

From here I feel it is natural to ask whether or not the set of incompressible strings is decidable, the answer is $\textit{no}$, but I would like to see the justification via a proof or proof sketch.

Edit: I would like to add I am already familiar/comfortable with the proof that Kolmogorov complexity is uncomputable.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Roughly speaking, incompressibility is undecidable because of a version of the Berry paradox. Specifically, if incompressibility were decidable, we could specify "the lexicographically first incompressible string of length 1000" with the description in quotes, which has length less than 1000.

For a more precise proof of this, consider the Wikipedia proof that $K$ is not computable. We can modify this proof as follows to show that incompressibility is undecidable. Suppose we have a function IsIncompressible that checks whether a given string is incompressible. Since there is always at least one incompressible string of length $n$, the function GenerateComplexString that the Wikipedia article describes can be modified as follows:

function GenerateComplexString(int n)
    for each string s of length exactly n
       if IsIncompressible(s)
          return s
          quit

This function uses IsIncompressible to produce roughly the same result that the KolmogorovComplexity function is used for in the Wikipedia article. The argument that this leads to a contradiction now goes through almost verbatim.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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