The "No Free Lunch" Theorem asserts that all search algorithms have the same expected behavior over all possible discrete search problems. Similar "No Free Lunch" results exists for machine learning: no method is better than another over all decision problems. We have recently proven that No Free Lunch holds over finite sets of functions, some of which are compressible and some of which are not. Other recent proofs show that the No Free Lunch Theorem does not hold over very broad sets of functions, including polynomial functions of bounded complexity. This talk will look at some of the theoretical and practical implications of No Free Lunch theorems. In particular, the use of Binary and Gray representations will be considered. These results have a very real impact on how we compare and evaluate search algorithms.