No Free Lunch Theorems

"No compression algorithm can compress data on average."

This is trivially true by a pigeon hole principle argument. There are 2^n strings of n bits, and after compression there is no way to represent them all with the 2^(n-1) strings of n-1 bits. In fact every string you find a way to compress forces another string to have a worse representation.

However the theorem, while true, is very false when you look at the types of data we actually encounter. This is amply demonstrated by the practical utility of things like gzip.

For yet another example of a No-Free-Lunch theorem that is bypassed in practice, there is no way to verify that 2 files on 2 different machines are the same that is faster than copying one file over to the other and comparing bit by bit. This is true. However rsync demonstrates that you can make much faster comparisons if you're willing to accept a very, very small possibility of error. It just compares hash values.

Interestingly in reality you're not giving any reliability up for the performance gain! Sure, in theory you do. But in practice the odds of the algorithm being wrong are lower than the odds of cosmic radiation messing up the theoretically correct way to do it!