William A. Dembski and Robert J. Marks II

   

"The Information Cost of No Free Lunch"

Abstract: The No Free Lunch Theorem (NFLT) is a great leveler of search algorithms, showing that on average no search outperforms any other. Yet in practice searches do outperform others. In consequence, some have questioned the significance of the NFLT to the performance of search algorithms. To properly assess the significance of the NFLT for search, one must understand the precise sources of information that affect search performance. Our purpose in this paper is to elucidate the NFLT by introducing an elementary theoretical framework for identifying and measuring the information utilized in search. The theory we develop shows that the NFLT can be used to measure, in bits, the fundamental difficulty of search, known as endogenous information.  This quantity in turn enables us to measure, in bits, the effects of prescribed implicit knowledge for assisting a search, known as active information. Such knowledge often concerns search space structure as well as proximity to and identity of target. Active information\ can be explicitly teleological or can result implicitly from knowledge of the search space structure. The evolutionary simulations Avida and ev are shown to contain large amounts of active information.

Draft [pdf]