5 ms·
Yes it does. Lets say for simplicity that you are coding your solution in python, and that your output should be written to standard out, and the output file sh
by im3w1l 14y ago
Yes it does. Lets say for simplicity that you are coding your solution in python, and that your output should be written to standard out, and the output file should be 10^6 bytes.
Consider the function that takes a source file of at most 10^6 to the standard output of said program when interpreted.
The set from which files you need to output, are drawn has cardinality 2^(10^6). The set of python programs (possibly invalid) that are strictly shorter has cardinality 2^(10^6-1). If all files were possible to compress, than a python interpreter would provide an injective map (one program gives maximum one output, possibly none if the program has errors) from a smaller set to a larger set. This is impossible. Therefore there is at least one file(actually a lot of them but this is beside the point) which cannot be compressed. Mike could send this one.
EDIT: Messed up my bits and bytes and fenceposts:
size 1: 256^(10^6). Size 2: sum (i=1 to 10^6) 256^(10^6-i)
- praptak 14y ago> Mike could send this one. Only assuming he'd be able to generate one. Is there a known algorithm for generating a provably Kolmogorov-uncompressible strings?
- Dylan16807 14y agoThat's a tricky question. I'll start with a couple ground limitations. First off, you can't have an algorithm to make incompressible strings of an arbitrary length, because then you could tell it to make an string larger than your algorithm, aka larger than its own complexity. You also can't measure the complexity of arbitrary strings or you could loop over all possible strings and use it to build a generator. But if you use the rules of your execution environment you can make sufficiently small incompressible strings. For example, if we used python, "abc" can't be compressed. There just aren't any operations that we can use to shrink it. But "abcabc" could be written as "abc"*2 Any algorithm you use is going to have to depend highly on whatever environment you choose, and it won't be able to produce very long strings, so I don't know if anyone has really bothered. In comparison, it's really easy to use random numbers such that the chance of being able to remove n bits is 1/2^n. If you have even a few bytes of overhead, as shell scripting has, you're safe from luck.
- im3w1l 14y agoPraptak: >Only assuming he'd be able to generate one. Is there a known algorithm for generating a provably Kolmogorov-uncompressible strings? In the theoretical case he has almost a 255/256 of doing it he generates a string in a truly random fashion. In the practical case his odds are much better. Many potential programs will a) refuse to run and b) give the same output.
- praptak 14y ago> In the theoretical case he has almost a 255/256 of doing it he generates a string in a truly random fashion. An interesting result. Do you have a link to the proof?
- Dylan16807 14y agoProof: There are k strings of bytelength n. There are k * 256 strings of bytelength n+1. k input strings can decompress to at most k output strings Therefore only k / (k * 256) of length n+1 strings can be compressed by a byte. The reason for 'almost' is the miniscule number of strings that will compress more than one bye.
- praptak 14y agoAh right, I totally missed the fact that compression by 1 bit doesn't beat the challenge!
- im3w1l 14y agoI really don't understand the mechanics of when a reply link appears. Anyway >An interesting result. Do you have a link to the proof? This is quite simple to understand. Just count how many files there are with size < n bytes (A), versus with size=n bytes (B). Size 1: sum (i=1 to n) 256^(n-i) ~= 256^(n-1). size 2: 256^(n). If you start pairing files from A up with files from B (equivalent to a compressing scheme), only 1/256 of files from B will be paired up. The remaining 255/256 of the files wont be paired up meaning they are not mapped to a smaller file, and cannot be compressed.