Hacker News Reader

Comment by jgeralnik | Hacker News Reader

No.

Let's say you have a file of size X. You want to write a program of size Y which will decompress an X-Y-1 sized file back to the original program. Does such a program and file exist for every file of size X?

Using the pigeon hole principle, we can see that it does not. There are 2^X files of size X, but only 2^(X-1) inputs of length Y+X-Y-1. Therefore, not every file can be compressed this way. It doesn't matter what your decompressor is written in or how, you still can't do it.

View on HN

This is correct for the general case, but I think his argument is that for any specific file you can (almost certainly) find some redundancy and so find an algorithm to compress that specific file.

That is exactly my argument.

But now I think I'm wrong because what if you take the new data (i.e. the decompressor plus the compressed data), and try to compress that.

You can't compress indefinitely because presumably your algorithm does not shrink in size. If your algorithm was 200 bytes, you could never successfully use it to compress a 199 byte file.

If this were possible, there would be a minimum file size, beyond which further compression were impossible.

I feel like the reason this might be possible is that there is information contained in a program that is not contained in that language's files. Specifically, in how the operating system treats those bits. In other words, the same decompressor + data file combo could have different but deterministic results depending on which operating system or machine executes it. We can therefore escape the pigeon hole's grip.

That doesn't help, because at the end of the day we are running on a specific os and machine. And given that machine, there exists a file of size X which it is not possible to compress because of the pigeon hole principle.

Right, but if we find that we do have a file which is impossible to compress, we could just switch to a system where it does work. There may even be operating system variables you could change which would change the output of the program. The guy asked: "Does it have to run on any machine or is just one machine ok." But did not get an answer.

I agree, for any specific machine configuration there exist non-compressible files, but I don't think we are so restricted. *Edit, it might also be possible to include in your compression algorithm the logic: change the OS into a state where this file is compressible.

Obviously you can create a machine which already has the original file on it, and have your "decompressor" simply print out that file.

I think that it was an unwritten requirement that it would work on Goldman's computer, and I think even people who say that Patrick's technique was legit would agree with that.

I see your point.

Reply on news.ycombinator.com