Hacker News Reader

Comment by unconed | Hacker News Reader

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.

View on HN

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)

> 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?

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.

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.

> 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?

Proof:

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.

Ah right, I totally missed the fact that compression by 1 bit doesn't beat the challenge!

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.

> 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.

Reply on news.ycombinator.com