3 ms·

For those like me who find it difficult to parse things like this without examples, here's an explanation of how the No-Free-Lunch Theorem applies to evolution

For those like me who find it difficult to parse things like this without examples, here's an explanation of how the No-Free-Lunch Theorem applies to evolution (specifically, why it doesn't apply): http://www.talkorigins.org/design/faqs/nfl/#nflt http://www.talkorigins.org/design/faqs/nfl/#nflt

btilly 17y ago
You can see this even more obviously if we add a third No-Free-Lunch theorem. "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!
- baddox 17y ago
  Regarding your last two paragraphs, you're right that probability is the key. The whole point of hashes is that small changes in input affect large changes in output. That works especially well for synchronization, since most changes will be incremental. In modern computing, like you say, there really are "free lunches," or perhaps one should call them "free increases in convenience and usability." Take programming languages, for example. Every programming language is Turing complete, and thus capable of solving any computable problem. However, no one would deny that there are performance gains from using a high order language rather than, say, assembly, even though technically high order programming is much less efficient (time spent compiling and optimizing, not to mention WRITING the compilers and optimizers, etc.). The whole no free lunch theorem is almost never applicable for any real-world scenario, hence gzip, rsync, md5, etc. are ubiquitous tools.
  - kd5bjo 17y ago
    > The whole point of hashes is that small changes in input affect large changes in output. I think you mean "effect" here.

btilly 17y ago

You can see this even more obviously if we add a third No-Free-Lunch theorem. "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!

baddox 17y ago
Regarding your last two paragraphs, you're right that probability is the key. The whole point of hashes is that small changes in input affect large changes in output. That works especially well for synchronization, since most changes will be incremental. In modern computing, like you say, there really are "free lunches," or perhaps one should call them "free increases in convenience and usability." Take programming languages, for example. Every programming language is Turing complete, and thus capable of solving any computable problem. However, no one would deny that there are performance gains from using a high order language rather than, say, assembly, even though technically high order programming is much less efficient (time spent compiling and optimizing, not to mention WRITING the compilers and optimizers, etc.). The whole no free lunch theorem is almost never applicable for any real-world scenario, hence gzip, rsync, md5, etc. are ubiquitous tools.
- kd5bjo 17y ago
  > The whole point of hashes is that small changes in input affect large changes in output. I think you mean "effect" here.