3 ms·
You are recreating Kolmogorov complexity there. Kolmogorov complexity is defined as the minimal amount of program (for some programming language) to recreate th
by lifthrasiir 14y ago
You are recreating Kolmogorov complexity there. Kolmogorov complexity is defined as the minimal amount of program (for some programming language) to recreate the given string. By the definition, your strategy will compress the data no better than its Kolmogorov complexity. In this aspect, Kolmogorov complexity measures the data's true randomness. If the random data has been generated correctly its complexity should be near its length, however, so your strategy won't work. (And there is enough evidence that this was the case.) It does not matter whether the data is already known or not; it is the data's inherent randomness prohibiting you to compress it.
To be sure, of course, Patrick Craig did not compress it in the pure information theoretic sense. Mike Goldman failed to equate the goal to that information theoretic compression however.
- RyanZAG 14y agoIf you pipe a random process into an image viewer, eventually you will get an image that can be compressed with PNG compression. If you let the random process run, you will eventually get enough of these images compressible by PNG that will allow you to save enough bytes to fit in a PNG decompression library. This may only occur after a ridiculous amount of bytes, but it is guaranteed to eventually occur following the properties of randomness. So the method will work, but it may take a very large amount of data before it does. If the method does not work, it implies that a random process cannot generate an image that can be compressed with PNG - and that is definitely false.
- jgeralnik 14y agoBut you also have to store the index at which the image occurs, and the index is bigger than the gains from the compression. This is similar to the argument that since pi is (probably) normal, any sequence of characters appears in it and we can simply use indexes into pi instead of storing numbers. The problem is that given a file of size X, that sequence of X bytes probably only occurs at more than 2^X places into pi.