1
$\begingroup$

There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course: enter image description here

I think it is saying finding the optimal size of given data is undecidable. However, I thought there is a theorem in information theory that gives the limit of the lossless compression? I think I must have misinterpreted something in this slide but I cannot tell what that is.

$\endgroup$
2
  • 4
    $\begingroup$ You can have a look at Kolmogorov complexity for more on this. $\endgroup$
    – Bruno
    May 5, 2022 at 9:46
  • 1
    $\begingroup$ One is optimal size for a single string, the other is optimal expected size for a distribution over strings. $\endgroup$ May 5, 2022 at 16:36

1 Answer 1

4
$\begingroup$

The length of the shortest program to produce a given string is known as the Kolmogorov complexity of that given string. (Of course, some details are needed to give a formal definition, but this is the idea.) A proof of undecidability goes roughly as follows:

  • There exist strings of arbitrary large Kolmogorov complexity by a counting argument: A program produces (at most) one string, and there are a finite number of program of length at most $N$, so a finite number of string of Kolmogorov complexity at most $N$;
  • Assume that the Kolmogorov complexity of a string is computable. For any integer $N$, we can write a program that does the following: it enumerates all the strings (in some lexicographic order) until it finds one that has Kolmogorov complexity $\ge N$. The size of this program is roughly $O(\log N)$ (a constant number of instruction, and the value of $N$ hard-coded in the program).
  • We conclude the string $s$ produced by the program of the preceding item satisfies two contradictory statements:
    • it has Kolmogorov complexity $\ge N$, that is the smallest program to produce it has length $\ge N$;
    • the program we describe has length $<N$ and produces $s$.

I don't know what you have in mind exactly concerning lossless compression, but it may be related to the first part of the proof sketch: It is not possible that all strings be compressible, because to each description corresponds one string.

$\endgroup$
5
  • $\begingroup$ en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem states that lossless compression cannot have entropy less than certain threshold. Doesn't that correspond to the shortest program in some way? $\endgroup$
    – Sam
    May 5, 2022 at 15:26
  • $\begingroup$ The second bullet point is a bit hard to read, but it reminds me a lot of diagonalization, the halting problem, and en.wikipedia.org/wiki/Interesting_number_paradox . $\endgroup$
    – Nayuki
    May 5, 2022 at 15:53
  • 1
    $\begingroup$ @Zzy1130 Information theory only loosely apply here. That studies, roughly put, how to compress an unknown string generated by a known random source. In that setting you want the compressed value to have the shortest average length, and theorems state that you can only compress so far (on average). By contrast, the undecidable problem you mentioned does not involve probability or averages: there is only a given string and you need to find the shortest program. $\endgroup$
    – chi
    May 5, 2022 at 16:40
  • $\begingroup$ @Zzy1130 If you take a standard compression algorithm, and compress the string $s$, then a possible algorithm to generate $s$ is the application of the decompress algorithm to the compressed $s$. However, this is not optimal: if $s$ contains the first $10^{10}$ digits of $\pi$ the compressed $s$ is still very long, and much shorter algorithms exist. $\endgroup$
    – chi
    May 5, 2022 at 16:50
  • 1
    $\begingroup$ I rewrote the second bullet. And yes, it has a lot to do with diagonalization. $\endgroup$
    – Bruno
    May 5, 2022 at 19:17

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.