« In Which I Answer Tantalus Prime's Queries About Abortion | Main

William Dembski and Robert Marks Publish (Another) Peer-Reviewed Scientific Paper Supporting No Free Lunch Theorems

A peer-reviewed scientific paper published in 2010 by William Dembski and Robert Marks of the Evolutionary Informatics Lab supports no free lunch theorems. Published in Journal of Advanced Computational Intelligence and Intelligent Informatics and titled "The Search for a Search: Measuring the Information Cost of Higher Level Search," the paper's abstract states that unless one has information about a target, search engines often fail: "Needle-in-the-haystack problems look for small targets in large spaces. In such cases, blind search stands no hope of success." Their principle of Conservation of Information holds that "any search technique will work, on average, as well as blind search." However, in such a case "[s]uccess requires an assisted search. But whence the assistance required for a search to be successful?"

Dembski and Marks thus argue that "successful searches do not emerge spontaneously but need themselves to be discovered via a search." However, without information about the target, the search for a search itself is still no better than a blind search:

We prove two results: (1) The Horizontal No Free Lunch Theorem, which shows that average relative performance of searches never exceeds unassisted or blind searches, and (2) The Vertical No Free Lunch Theorem, which shows that the difficulty of searching for a successful search increases exponentially with respect to the minimum allowable active information being sought.

The implication of course, is that without the ultimate input from an intelligent agent--active information--such searches will fail.


TrackBack URL for this entry: