Perhaps a stupid question, but is the challenge not also solvable with 'honest' comp.sci?
The way I think about it at the moment, is that I take a family of functions, C_k, which map the space of n elements strings to the space of [1, 2n] element strings ( the union of m element strings for 0 > m > 2n) in a essentially random way. The output is then in [1, n - sizeof(C_k) -1] with some probability p and if I try long enough, I find a compression scheme which compresses the given input.
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.
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.
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)
I 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.
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.
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.
> 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.
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.
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.
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.
