4 ms·

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 suc

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.

ars 14y ago
I see your point.
czr80 14y ago
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.
- ars 14y ago
  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.
  - bloaf 14y ago
    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.
bloaf 14y ago
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.
- jgeralnik 14y ago
  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.
  - bloaf 14y ago
    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.
    - jgeralnik 14y ago
      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.

ars 14y ago

I see your point.

czr80 14y ago

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.

ars 14y ago
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.
- bloaf 14y ago
  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.

bloaf 14y ago

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.

jgeralnik 14y ago
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.
- bloaf 14y ago
  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.
  - jgeralnik 14y ago
    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.