4 ms·

No, it is defInitely not possible. If it were, you could do it over and over again and compress any file down to an arbitrarily small size. Two things to search

No, it is defInitely not possible. If it were, you could do it over and over again and compress any file down to an arbitrarily small size. Two things to search for are "pigeonhole principle" and "kolmogerov complexity." Essentially the problem is that any encoding of a string either preserves the length of all possible inputs, or shortens some inputs and lengthens others, or lengthens all inputs. There is no encoding that shortens all strings because of the pigeonhole principle. To apply this to the challenge, see that the challenge is to encode the string as a program that when executed produces the string. Just because the encoding language is Turing complete does not mean that it can evade the pigeonhole principle.

unconed 14y ago
But the challenge isn't to compress random strings, the challenge is to compress a specific random string. This means that given enough time, you should be able to come up with an algorithm or transformation that turns that specific string into something of lower entropy. I'm not saying this is very feasible, but it doesn't violate the pigeonhole principle. For example, there is a fixed size algorithm to generate the digits of pi, even though pi is incompressible.
- napillo 14y ago
  Exactly. Given enough time, you could come up with a compression algorithm that would generate the original file. It would only work for that one single file though.
- 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 ago
      That'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 ago
    Praptak: >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?
- dmfdmf 14y ago
  > But the challenge isn't to compress random strings, the challenge is to compress a specific random string. I agree and I think that this challenge is vulnerable albeit very difficult but not impossible, at least not via the pigeonhole principle. To be clear, the pigeonhole principle says for a given compression aglo and an input file of size n the output file must get bigger than n for some inputs of size n, i.e. it cannot compress all possible permutations of size n. However, the way the challenge is setup it is saying; given a specific random file of size n, find an algo that can compress the file so that the output plus decompressor is less than the input file. The pigeonhole principle does not say this is impossible. Granted, finding the algo that does this may mean solving P=NP or may take 10^32 lifetimes of the universe in calc time to find it but in principle it is not impossible. I admit, my understanding may be wrong and would really appreciate it if someone can explain to me my error here.
romaniv 14y ago
I think the reason most people don't see this intuitively, is because pigeonhole principle explanation doesn't deal with the mechanism of compression they have in mind. It's just a general statement of impossibility. To give them intuition about it, you would need to show why exactly the compression approach they have in mind won't work.
- yk 14y ago
  I believe the pigeon hole principle does not realy apply here, since we are looking for an algorithm that encodes just one file. For example, if we have two programs and input: ( C, n) and ( D, n) which can both be encoded in n-1 bits and ( C, n) maps into the set of n bit strings with a leading 0 and ( D, n) into the set of strings with leading 1, then counting the number of bits, I end at 2^n-1 possible states for both the programs and the output. Effectively one bit is hidden in the choice of C or D.
praptak 14y ago
How exactly the pigeonhole principle help here? It only proves that you cannot compress all inputs. For the challenge to be unbeatable you need to prove something much stronger - namely that for each file size most of the strings are random in the Kolmogorov sense. Has this been proven? Edit: The above is too strict - obviously it would be sufficient to prove that for any size you can effectively compute a Kolmogorov-uncompressible string of this size. Anyway my point is that such proof would not be trivial.
- dmfdmf 14y ago
  I think I agree with you, please see my reply to unconed above; http://news.ycombinator.com/item?id=4618495 http://news.ycombinator.com/item?id=4618495 I'd love to know if I am wrong.

unconed 14y ago

But the challenge isn't to compress random strings, the challenge is to compress a specific random string. This means that given enough time, you should be able to come up with an algorithm or transformation that turns that specific string into something of lower entropy. I'm not saying this is very feasible, but it doesn't violate the pigeonhole principle. For example, there is a fixed size algorithm to generate the digits of pi, even though pi is incompressible.

napillo 14y ago
Exactly. Given enough time, you could come up with a compression algorithm that would generate the original file. It would only work for that one single file though.
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 ago
    That'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 ago
  Praptak: >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?
dmfdmf 14y ago
> But the challenge isn't to compress random strings, the challenge is to compress a specific random string. I agree and I think that this challenge is vulnerable albeit very difficult but not impossible, at least not via the pigeonhole principle. To be clear, the pigeonhole principle says for a given compression aglo and an input file of size n the output file must get bigger than n for some inputs of size n, i.e. it cannot compress all possible permutations of size n. However, the way the challenge is setup it is saying; given a specific random file of size n, find an algo that can compress the file so that the output plus decompressor is less than the input file. The pigeonhole principle does not say this is impossible. Granted, finding the algo that does this may mean solving P=NP or may take 10^32 lifetimes of the universe in calc time to find it but in principle it is not impossible. I admit, my understanding may be wrong and would really appreciate it if someone can explain to me my error here.

romaniv 14y ago

I think the reason most people don't see this intuitively, is because pigeonhole principle explanation doesn't deal with the mechanism of compression they have in mind. It's just a general statement of impossibility. To give them intuition about it, you would need to show why exactly the compression approach they have in mind won't work.

yk 14y ago
I believe the pigeon hole principle does not realy apply here, since we are looking for an algorithm that encodes just one file. For example, if we have two programs and input: ( C, n) and ( D, n) which can both be encoded in n-1 bits and ( C, n) maps into the set of n bit strings with a leading 0 and ( D, n) into the set of strings with leading 1, then counting the number of bits, I end at 2^n-1 possible states for both the programs and the output. Effectively one bit is hidden in the choice of C or D.

praptak 14y ago

How exactly the pigeonhole principle help here? It only proves that you cannot compress all inputs. For the challenge to be unbeatable you need to prove something much stronger - namely that for each file size most of the strings are random in the Kolmogorov sense. Has this been proven? Edit: The above is too strict - obviously it would be sufficient to prove that for any size you can effectively compute a Kolmogorov-uncompressible string of this size. Anyway my point is that such proof would not be trivial.

dmfdmf 14y ago
I think I agree with you, please see my reply to unconed above; http://news.ycombinator.com/item?id=4618495 http://news.ycombinator.com/item?id=4618495 I'd love to know if I am wrong.