Mathematical Proof That There’s No Such Thing As A Free Lunch

[Updated 02/02/2011:  A Comment on Active Entropy”.]

A recent published peer-reviewed paper entitled “The Search For A Search: Measuring The Information Cost of Higher Level Search” is one of the more interesting mathematical proofs of a type that I am particularly fond of. The authors of the paper, William Dembski and Robert Marks II (from the Discovery Institute and Baylor University, respectively), prove two interrelated mathematical theorems that provide some heft with regards to the No Free Lunch Theorems. I am fond of “No Free Lunch” Theorems as they provide some grounding for the conservation of information necessary to successfully solve the intractable problems of the origin of life.

What this paper does, in a very technical way [1], is to prove that in order to successfully search for information more effectively than blind chance, one must have information to guide one’s search. There are two different kinds of No Free Lunch Theorems, both of which are proved mathematically in this paper. Horizontal No Free Lunch Theorems prove that no searches without information will be more successful on average than unassisted or blind searches, and that searching with the wrong information will be less effective than blind or unassisted searches. Vertical No Free Lunch Theorems, on the other hand, prove that the length of time for searches for searches in the absence of information increase exponentially in time the further the regress for the search.

The implications of these theorems is massive, even if the language used in the paper is highly technical and accessible largely to those with a fondness for information theory and theoretical mathematics. For one, these theorems demonstrate that many of the supposed “blind” searches that try to model evolutionary behavior in reality have front-loaded information or assisted fitness from the researchers themselves. Evolutionary theorists find themselves in a bind—in order to find any kind of evidence for evolutionary development, even on a trivial scale (like the Urey and Miller origin of life experiments) there must be active intelligence on the part of the researchers stacking the deck in favor of even modest results, including information provided through the design of the experiment or through the order of its operations. This information is smuggled in like a magician engaging in parlor sleight-of-hand tricks, but it can be spotted by the watchful observer.

On the other hand, without such sleight-of-hand, the origin of life or its development through unguided and naturalistic means is hopeless. If the active efforts of intelligent and competent and well-trained scientists can only provide modest examples in favorable environmental settings (hardly a test of the real conditions), then unassisted means are hopeless. By proving rigorously and mathematically that without information on the “target” there can be no better results on average than blind chance, Demski and Marks make naturalistic evolutionary development mathematically impossible, since there is simply not enough time for life to develop unassisted according to scientific knowledge. That is what makes No Free Lunch Theorems so beautiful—it basically limits those who would posit inflationary cosmic resources to solve the information problems of life to two options—cheat or admit defeat. Given the stakes of the Evolution-Intelligent Design debate, defeat is not an option, so we should expect to see a lot of cheating, whether that means the positing of infinite universes or other means.

With a friendly graphical and mathematical approach, this paper on No Free Lunch Theorems ought to be a basic staple of any Intelligent Design-friendly course in mathematical logic, biology, or information theory. Despite its technical language, its conclusions are accessible to others, and I hope that Mr. Dembski is able to continue work on making the conclusion more accessible, as he has written books on No Free Lunch in the past.

In the meantime, though, let us celebrate this particular paper, which was published in the Journal of Advanced Computational Intelligence And Intelligence Informatics, a very appropriate journal for such a technical work on information theory. Having provided a bit of information on the matter, hopefully now a successful search for excellent peer-reviewed papers on Intelligent Design can be a little easier. In the meantime, I am looking for ward to more excellent research to examine.

Update:  02/02/2011:

It appears that my wish for more research to examine did not take long.  In a paper responding to the Dembski and Marks paper, a researcher steps into some trouble by attempting to refute without understanding precisely what he is refuting [2].  In seeking to find fault with the use of active entropy, he fails to understand that Dembski and Marks showed that “an informed assisted search will, on average, perform worse than a baseline search.”  That this is so ought not to be difficult to understand, even by the modest standard of intellectual capabilities found in origin of life debates.

Why is this so?  If one assists a search without active information, on average one will do more harm than good, because one’s assistance will likely be based on incorrect information.  The origin of life debates have many useful examples of this phenomenon.  For example, the active search for mechanisms for prebiotic evolution, in the development of self-replicating RNA or DNA worlds, is itself an example of an uninformed assisted search, uninformed because it denies the possibility (indeed, requirement) of a designer and assisted because such efforts to show the existence of naturalistic evolution receive covert or open assistance from researchers who attempt to stack the deck in favor of evolution in experiments, like the Urey and Miller experiments.

Unless a search takes place in homogeneous space with active and correct information, imparted by an intelligent being with a target in mind, an assisted search is likely to perform worse on average than a random search because the biases of the uninformed “informer” is likely to get in the way by reducing the target space in an area that excludes what one is looking for, thus making any successful search impossible.  As the biological world supplies many such examples of uninformed assisted searches in the origin of life debate, and in the study of such wonders as biological machines, should Dembski and Marks wish to turn their mathematical paper into a sociological examination of the culture of science, they would have overwhelming evidence to apply their conclusions on the No Free Lunch Theorems to the actual behavior and results of biological experiments.  Whether they will do so, is, of course, up to them.

I'm a person with diverse interests who loves to read. If you want to know something about me, just ask.
This entry was posted in Musings and tagged , , , . Bookmark the permalink.

29 Responses to Mathematical Proof That There’s No Such Thing As A Free Lunch

1. R0b says:

and that searching with the wrong information will be less effective than blind or unassisted searches

It’s strange that this claim, which clearly contradicts Wolpert and Macready’s NFL theorems, would be found in a paper co-authored by someone who titled a book after those theorems. (See here.) There is no such thing as wrong or right information when performance is averaged over all potential targets.

And I see nothing in Marks and Dembski’s work to justify the idea that “active information” requires intelligent causation. On the contrary, their analysis of Thomas Schneider’s ev shows an example of unintentional active information as opposed to intelligent smuggling. As Tom English has said, “While an agent may introduce bias, the presence of bias does not signal agency.” Most people don’t infer intelligence from the fact that gravity biases objects toward the earth.

• It’s strange that a post like this would be so incoherent. It is not the existence of bias, but the existence of information, that would signal agency, and surely someone as intelligent as yourself ought to recognize that while seeing a sign saying “Welcome To Tampa” would lead for someone to infer intelligence, the gravitational pull of the earth towards smaller objects would not necessarily do so. Surely you ought to be able to understand that information requires intelligence both to create and to infer.

• R0b says:

I’m sorry that you found it incoherent, but you seem to be conflating “information” as defined by Marks and Dembski with the more common usages of the term.

surely someone as intelligent as yourself ought to recognize that while seeing a sign saying “Welcome To Tampa” would lead for someone to infer intelligence, the gravitational pull of the earth towards smaller objects would not necessarily do so

Of course I recognize that, which is why I pointed out that most people don’t infer intelligence from gravity. And that’s why Marks and Dembski’s “active information”, of which gravity is a example, is not a reliable indicator of design.

If you disagree that gravity is an example of active information, can you explain why it isn’t? Is the earth not an “intrinsic target” as Marks and Dembski define the term? Do objects not find their way to earth with greater-than-blind-search probability?

Surely you ought to be able to understand that information requires intelligence both to create and to infer.

Are you talking about “active information”? If so, what does it mean to create active information? Can an intelligent agent find a small target in a large informational void? No. If an intelligent agent has information that allows them to find a target with a probability of 1 out 1000, can they somehow achieve an average success rate of 1 out of 10? No, that’s self-contradictory. Marks and Dembski’s information accounting framework tautologically precludes any increases of active information, so the idea of creating active information simply doesn’t make sense.

• You seem unduly fixated on the aspect of gravity, which was not a part of the paper by Dembski and Marks, as you ought to realize. Their “search for a search” was a needle in the haystack search of a homogeneous space as would be the case with a search for the mutations that would allow for the development of night vision rather than the search for the earth in a gravitational field. The whole point of the No Free Lunch Theorems is to make impossible an unguided algorithm in areas like genetics where no such issues of determinism are present, and where there is no intrinsic bias in the system (as there is in the case of gravity). The fact that you cannot properly distinguish what either I or the authors of that fine paper are discussing suggests that you lack sufficient epistemological understanding to engage in a rational or coherent discussion of the No Free Lunch Theorems or the issue of information. After all, a blind squirrel will still fall to the ground, but a billion monkeys with keyboards would still be unable to type a Shakespearean sonnet. This is hardly tautological, as you mistakenly say. I suggest you get back to the books and study up a little.

2. R0b says:

nathanalbright, let’s back up. I’m not impugning your competency, and I hope you’re not impugning mine. I’m offering specific challenges to what I see as misconceptions.

Their “search for a search” was a needle in the haystack search of a homogeneous space as would be the case with a search for the mutations that would allow for the development of night vision rather than the search for the earth in a gravitational field.

Marks and Dembski’s point is not to show us that small targets in large homogeneous spaces cannot tractably be found. Nobody disputes that obvious fact. Rather, their “search for a search” reasoning addresses situations in which the search space is not homogeneous and the search actually works (eg WEASEL, ev, Avida, etc.). Their point is that if Darwinian evolution works, it does so by exploiting active information. Of course, nobody disputes this either. What I and other critics dispute is the idea that this active information necessarily originated by design, either directly or via a regress of meta-searches.

Hence the counterexamples of Tom Schneider’s unintentional choice of an easy-to-find target, and gravity, which most people do not see as indicative of design. I explicitly stated why gravity is an example of active information: (a) The earth is an “intrinsic target”, as Marks and Dembski use the term, and (b) objects tend to find that target. I asked if you disagree with these premises, but you haven’t responded. Gravity is only an example — the same reasoning applies to all biased systems, which constitute most of nature. So I’ll ask again, what is wrong, if anything, with this reasoning?

The whole point of the No Free Lunch Theorems is to make impossible an unguided algorithm in areas like genetics where no such issues of determinism are present, and where there is no intrinsic bias in the system (as there is in the case of gravity).

That unbiased sampling cannot tractably find a small target is an obvious fact, not a result of the NFL theorems. And genetics certainly has biases. Even if the location and outcome of occasional mutations are not biased, replication, expression, and selection certainly are.

The fact that you cannot properly distinguish what either I or the authors of that fine paper are discussing suggests that you lack sufficient epistemological understanding to engage in a rational or coherent discussion of the No Free Lunch Theorems or the issue of information.

With regards to understanding what you’re saying, I’m trying. For instance, when you said that “information requires intelligence both to create and to infer”, I asked if you were referring to active information. Why not tell me?

With regards to understanding the authors, I do in fact understand their peer-reviewed papers. I have talked with them, pointed out errors, and offered corrections, one of which is in the paper that you’re reviewing here. Another paper was retracted because of the errors I pointed out, and yet another paper contains a proof that I originated.

I mention these things not to pretend to be smart, but to point out that these concepts are simple. The NFL principle was understood long before Wolpert and Macready formalized it and gave it a name. Olle Haggstrom illustrated it as follows (and Marks and Dembski borrowed this illustration in one of their papers):

If we spread a well-shuffled deck of cards face-down on a table and wish to find the ace of spades by turning over as few cards as possible, then no sequential procedure for doing so is better than any other.

All NFL theorems, including Marks and Dembski’s Vertical NFLT, are restatements of or corollaries to this principle. Deriving the Vertical NFLT from it is quite trivial. (Showing that the difficulty increases exponentially is non-trivial, but irrelevant to M&D’s point.) The Horizontal NFLT, on the other hand, is an attempt to apply the concept of relative entropy to searches, and it clearly doesn’t work. The NFL principle is simple enough that we can immediately see that it is contradicted by the statement, “searching with the wrong information will be less effective than blind or unassisted searche.” Dembski and Marks’ mathematical reasoning that led to that statement is wrong. The link I provided above explicitly describes the problems. Do you disagree with anything in the link?

After all, a blind squirrel will still fall to the ground, but a billion monkeys with keyboards would still be unable to type a Shakespearean sonnet. This is hardly tautological, as you mistakenly say.

That statement is certainly not tautological — where did I say or imply that it was? What I said is that the assertion that active information cannot increase is tautological. Active info is defined in terms of probabilities, which M&D treat as frequentist probabilities. That is, the existence and quantity of active information are treated as being independent of anyone’s knowledge or lack thereof (which calls into question the validity of invoking the principle of indifference, a Bayesian heuristic). By definition, the frequentist probability of a given event under a given complete set of relevant conditions does not change. What then does it mean for a quantity of active info to change? This gets into some subleties of the definition of active info. Can you define active info such that it’s provably conserved, but its conservation isn’t tautological? That would seem to be a necessary step in showing that nature can’t create active info but design can.

• Where is the “bias” in biology that would account for the development of fantastically complicated processes and biological mechanisms with specified complexity? The fact that they exist in spades is not itself evidence that undirected means (such as Darwinian processes) are able to create them. Your assumption of facts not in evidence is in fact demonstration that you fail to account for the damaging effect of the No Free Lunch Theorems on evolution. The fact that your worldview is mistaken provides for your inability to grasp that there is no gravitational bias (i.e. determinism) that has led us to this point. The fact that you compare the existence and development of life, which is contingent, to a search that a blind squirrel could meet shows that you are lacking in understanding, and therefore incompetent to engage in this sort of discussion. Go back to the basics of your own mistaken worldview before you approach me again.

• R0b says:

Where is the “bias” in biology that would account for the development of fantastically complicated processes and biological mechanisms with specified complexity?

This question has nothing to do with the subject we’re discussing. Again, Marks and Dembski’s theorems do not call into question the viability of natural evolution. They are taking a different tack, saying that if natural conditions or laws are biased toward complex life (they even refer to Simon Conway Morris), then those natural conditions or laws were designed.

Your assumption of facts not in evidence is in fact demonstration that you fail to account for the damaging effect of the No Free Lunch Theorems on evolution.

Can you name a single fact not in evidence that I have assumed?

The fact that you compare the existence and development of life, which is contingent, to a search that a blind squirrel could meet shows that you are lacking in understanding, and therefore incompetent to engage in this sort of discussion. Go back to the basics of your own mistaken worldview before you approach me again.

I’ll leave you with this: I’ve asked several very specific questions in the course of our conversation. If you try to answer them, you’ll see the problems with Marks and Dembski’s arguments.

• Rob,

Au contraire, my question is an important one as it relates to the sort of bias you take for granted in Biology. You asserted, in error, that biology was biased. When I asked you where that bias was located given that there is no bias in terms of the actual DNA letters themselves making G or C or A or T more likely the chain, for example, you say the question is not relevant. You are correct in noticing that Dembski and Marks take a different tack, but to do so does not mean to abandon other lines of argument. The fact is that the mistaken naturalistic worldview can be attacked on numerous grounds, and correspondingly design can be demonstrated on similarly varied grounds. If one researcher examines the aspect of the irreducible complexity of mechanical machines and another researcher examines the higher order coding of DNA and the modular nature of homologous features in DNA, neither of them is implying in the least that the other means of argument are less valid. Again, you have shown nothing that would demonstrate that the examination of Dembski and Marks is lacking, except that it attacks your flawed worldview. I have given you specific questions and your refusal to answer demonstrates your own unwillingness (for whatever reason) to grapple with the issue.

3. R0b says:

You asserted, in error, that biology was biased. When I asked you where that bias was located given that there is no bias in terms of the actual DNA letters themselves making G or C or A or T more likely the chain, for example, you say the question is not relevant.

Why would you ask me that, when I already gave three examples of bias in biology, namely replication, expression, and selection?

What you actually asked is, “Where is the ‘bias’ in biology that would account for the development of fantastically complicated processes and biological mechanisms with specified complexity?” (Emphasis added.) But I never claimed that such bias exists. I haven’t tried to defend Darwinian evolution at all. Your post is about Marks and Dembski’s work, which doesn’t dispute Darwinian evolution.

You refer to “the sort of bias that [I] take for granted in Biology”. What sort of bias is that, and what makes you think that I take it for granted?

You are correct in noticing that Dembski and Marks take a different tack, but to do so does not mean to abandon other lines of argument. The fact is that the mistaken naturalistic worldview can be attacked on numerous grounds, and correspondingly design can be demonstrated on similarly varied grounds.

Certainly there are other lines of argument to attack the naturalistic worldview, but why bring them up when we aren’t debating that worldview and I’ve never tried to defend it? Your post promoted Marks and Dembski’s work, and I pointed out serious problems with it. Bringing up a different argument against naturalism doesn’t defend M&D’s work, nor does it address anything I’ve said.

Again, you have shown nothing that would demonstrate that the examination of Dembski and Marks is lacking, except that it attacks your flawed worldview.

Actually, I have shown some very specific things in that regard. Would you like me to repeat them?

I have given you specific questions and your refusal to answer demonstrates your own unwillingness (for whatever reason) to grapple with the issue.

I see only one question from you: “Where is the ‘bias’ in biology that would account for the development of fantastically complicated processes and biological mechanisms with specified complexity?” Again, I never claimed that such bias exists, so how is this “the issue”? I’ve challenged your statements with over a dozen questions. You won’t even respond when I simply ask what you’re referring to. You tell me that intelligence is required to create information, but you won’t tell me whether you’re referring to active information. You tell me that I assume facts not in evidence, but you won’t tell me where I did so.

With regards to my paper, you say:

If one assists a search without active information, on average one will do more harm than good, because one’s assistance will likely be based on incorrect information.

and

Unless a search takes place in homogeneous space with active and correct information, imparted by an intelligent being with a target in mind, an assisted search is likely to perform worse on average than a random search because the biases of the uninformed “informer” is likely to get in the way by reducing the target space in an area that excludes what one is looking for, thus making any successful search impossible.

These assertions are proven false by the line of trivial math at the end of the paper. It doesn’t matter if the search is assisted or unassisted, or if it’s based on certain information or on the opposite of that information. All searches perform exactly the same when averaged over the possible targets. That’s basic NFL. In fact, it’s a special case of NFL in which the math is particularly simple, as the paper shows. If you think the math is wrong, it should be very easy to point to the error.

• I have asked you how such areas are “biased,” and the areas that you have provided are areas where there is clearly “active information” and not uninformed assisted searches as was spoken about in the paper. There is a link to a paper featuring some pitiful arguments and poor mathematics that I commented on briefly; I assume that is what you posted/wrote on the matter? The “serious problems” alleged with the paper include such issues as their use of active entropy to define assistance as harmful, but it is far from problematic that any kind of uninformed assistance will be worse than useless. The fact is that the mathematics used by Dembski and Marks is not troublesome on a theoretical or mathematical level. If you have quibbles with them–take it up with them (neither of them is that hard to find, I suspect). The paper itself demonstrated that some searches will perform worse than average if the assistance is worse than useless (for example, by shrinking the target area in a way that excludes the actual target, something that routinely happens with regards to biological experimentation). Additionally, biological efforts to “prove” evolution or to make it plausible routinely smuggle active information, showing that the favorable (if still pitiful) results they get are still received because of the smuggling of active information by the biased researcher, rather than the bias inherent in nature itself. If there is bias in biology, the bias is far more in the biologists themselves than in the natural processes they examine.

4. R0b says:

nathanalbright, you seem like a great person, and I’m sure we could find quite a bit that we agree on. In this discussion we’re at an impasse, so I sincerely wish you well.

• I happen to agree with you, and echo your sentiments.