It is not possible, without some amount of luck. The reason is, that you can think of the data + decompressor as a program which contains the data as some bina

It is not possible, without some amount of luck. The reason is, that you can think of the data + decompressor as a program which contains the data as some binary blob. There are less than 2^s different possible executables, where s is the filesize of the compressor together with the compressed data. And therefore 2^s different outputs. On the other hand, there are 2^l different original files (l is the filesize). Therefore only a few files can be compressed to a smaller file size. To be precise, you can compress at best 2^s files out of the 2^l ones by l-s bits. Thinking a bit further, for a file of length l, the probability getting a file that can be compressed is smaller than \sum_{k=1}^{l-1} 2^{-k} [1] which approaches 1 for l against infinity. ( So just based on the upper limit, your odds seem to get better for longer programs. :) [1]rendered formula for the equation (hope this works): http://latex.codecogs.com/gif.latex?\sum_{k=0}^{l-1}%202^{-k} http://latex.codecogs.com/gif.latex?\sum_{k=0}^{l-1}%202^{-k...