On 8 Jan 2002, at 14:27, Michael Motyka wrote:
Here we go :
"As Eric correctly points out, true random input simply cannot be compressed, it doesn't matter how clever you are or how much time and computing power you have access to."
This is a statement of belief isn't it? Odd.
Mike
No, it's s statement of mathematical fact, easily understandable by anyone of average intelligence with a little thought. The piegonhole principle states that if there are N pigeonholes and M > N objects that have to be stuffed into the piegonholes, at least one of the pigeonholes will have to contain more than one object. Any compression algorithm is a mapping between files. Therefore, there CANNOT exist an algorithm which will compress all files. Because there are always twice as many bit patterns N + 1 bits long as there are bit patterns N bits long. Clear enough? If not, consider this (which Eric also mentioned in his original post): If you really had an algorithm that could compress ANY file to 1/100 its size, you could run the output data through the algorithm again and get something 1/10000 the size of the original file. Now, the philsophically inclined might point out that, although there cannot exist an algorithm which can compress all files, and that any given "compression" algorithm is highly unlikely to be able to compress a truly random file, nonetheless there are no specific files of which you can say, "this file is uncompressible", since you could always devise an algorithm specifically designed to compress that particular file (for example, by mapping it to a file of zero length and mapping all other files to themselves with an extra 0 on the ebd). To which the paractical man replies, "you're in a balloon about 20 feet off the ground". George