Searching Large Spaces: Displacement and the No Free Lunch Regress

DesignInference.com ^ | March, 2005 | William A. Dembski

[Michael_Michaelangelo]

Searching for small targets in large spaces is a common problem in the sciences. Because blind search is inadequate for such searches, it needs to be supplemented with additional information, thereby transforming a blind search into an assisted search. This additional information can be quantified and indicates that assisted searches themselves result from searching higher-level search spaces--by conducting, as it were, a search for a search. Thus, the original search gets displaced to a higher-level search. The key result in this paper is a displacement theorem, which shows that successfully resolving such a higher-level search is exponentially more difficult than successfully resolving the original search. Leading up to this result, a measure-theoretic version of the No Free Lunch theorems is formulated and proven. The paper shows that stochastic mechanisms, though able to explain the success of assisted searches in locating targets, cannot, in turn, explain the source of assisted searches.

[Michael_Michaelangelo]

"Searching Large Spaces" fills in the details of chapter 4 of No Free Lunch, which David Wolpert referred to as "written in jello." The key result is a displacement theorem, which I suspect will ultimately become the fundamental theorem qua mathematical underpinning of ID. In this paper, I also prove a measure-theoretic variant of the No Free Lunch theorems. This paper will be presented as part of my Trotter Prize lectures at Texas A&M this April, a prize that I'm sharing this year with Stuart Kauffman. Past recipients include Charlie Townes, Francis Crick, Paul Davies, and Alan Guth.

~Dembski

[Michael_Michaelangelo]

Hot off the press, ping.

[MacDorcha]

Enlightening.

[balrog666]

More idiocy on parade, a "biological proof by analogy".

BWAAAAAAAAAAAAAAAAAAHAHAHAHA!

[MacDorcha]

"Analogy"?

You're smoking something. Comeon, share it with the rest of us!

Look at the article, does anything about it say "it's as if we were" or "this is like."

An analogy is a comparrison using "like" or "as."

Did this fundamental aspect of the English language escape you in middle school?

[charleywhiskey]

Miss Galloway, my English teacher of many years ago, was quite adamant that a comparison using "like" or "as" should be known as a simile.

[MacDorcha]

Heh, lol, my bad. Yep, egg on my face.

However, this is still not a comparrison.

::blushes::

[mason-dixon]

My last course on set theory / abstract math was decades ago. Is there any way for you to explain this paper to me using a tangible example -- locating cancer cells in a human body or locating unfriendly folks (terrorists, criminals) in an urban setting?

I have the impression that your thesis has application in these examples.... but then I could be totally mistaken.
Thanks in advance.

[Michael_Michaelangelo]

Howdy! I'm just the messenger for this article. You're going to have to ask one of the resident experts that question.

FRegards, MM

[<1/1,000,000th%]

As an example to which we can put actual numbers for I(u₀|U), take the search for a given protein 100 amino acids in length (recall section 1). Call this protein the target T. There are roughly 10¹³⁰ amino acid sequences of length 100. This space of sequences is the search space Omega. The uniform probability U on Omega assigns equal probability to each point in the space. Thus U(T) = p is roughly equal to 10^-130.

So according to this article, no one can get AIDS because the probability of the transcribed viral DNA finding it's way to the correct binding site in the host cell DNA is too small.

Finally. A useful result of ID

[AndrewC]

In general, we may therefore characterize an assisted search A on the space O ; with target T , metric structure D, uniform probability U, and sample size m as a pairing of strategy function s and information function j, i.e., A = (s, j). In case of a blind search, j is just the indicator function for the target T and s is any sampling scheme with no inherent bias toward or prior knowledge about the target T . This last condition, which attempts to purify the strategy function of any special information from the environment regarding the target, is diffcult to formulate with full generality (cf. Culberson 1998). Nonetheless, there are clear instances where this condition is unproblematically fulfilled–exhaustive search, uniform random sampling, and random walks being cases in point.

Yep, the old needle in a haystack ploy.

[AndrewC]

More idiocy on parade, a "biological proof by analogy".

Mighty proud of yourself aren't ya? But I would suggest you learn a little more math than 1 + 1 = 3. It will help you to gain a little more understanding of a mathematically based argument.

[John Locke]

It seems Dembski is still peddling his "no free lunch" scam. For a brilliant and ruthless demolition of his earlier efforts, go here.

[AndrewC]

For a brilliant and ruthless demolition of his earlier efforts, go here.

Oh?? I don't think you even tried to read the paper that this thread is based on. Because if you had, you would notice a severe lack of mathematics in your link and notice the mathematics used in Dembski's paper. Could you cite the portion of the brilliant and ruthless demolition where the following is mathematically addressed?

This, in measure-theoretic terms, restates the No Free Lunch theorems ofWolpert and Macready (1997), which say that when averaged over all fitness functions (whether time-dependent or time-independent fitness functions), no evolutionary search procedure outperforms any other. Thus, in particular, these searches, when averaged, do not outperform blind search. If we now think of [theta]; under the integral in Integral_M([Omega])[theta] [delta] [bar]U([theta]) as an exchange probability for an assisted search, this formulation of the No Free Lunch theorem says that the average performance of all assisted searches is no better than uniform random sampling, which throughout this paper epitomizes blind search.

link above pg. 22

[Alamo-Girl]

Thanks for the ping!

[Doctor Stochastic]

The author is rather kind to Dembski.

[Michael_Michaelangelo]

For a brilliant and ruthless demolition of his earlier efforts, go here.

From your link...here's how Orr starts out:

The anti-Darwin movement, at least in its popular form, began in the primitive whoops and hollers of young-earthers and seven-day literalists.

Is that how you would try to "demolish" Dembski? I'd say he has no ammunition and is taking unecessary swipes.

Dembski has responded to Orr.

From Arn.org:

Evolution's Logic of Credulity: An Unfettered Response to Allen Orr

According to Orr, neither specified complexity nor irreducible complexity is beyond the reach of Darwinism. Yet to justify this claim, all Orr has done is describe supposedly possible Darwinian pathways, in highly abstract and schematic terms, to which, in the case of Darwinism, no significant details have been added since the time of Darwin (and, I would urge, none has been added even since the time of Empedocles and Epicurus). In consequence, critics of Darwinism who say it is merely a theory don't go far enough -- it doesn't even deserve to be called a theory. No Darwinist, for instance, has offered a hypothetical Darwinian production of any tightly integrated multi-part "adaptation" with enough specificity to make the hypothesis testable even in principle. When it comes to the large-scale evolutionary changes needed to account for the complexity and diversity of life, Darwinism is a pile of promissory notes for future theories, none of which has been redeemed since the publication of Darwin's Origin of Species almost 150 years ago.

[jwalsh07]

Dawkins' weasel simulation is a joke. The joke is on anybody who thinks it demonstrates anything.

[AndrewC]

From your link...here's how Orr starts out:

Then later he continues ....

And, yes, he believes—contrary to everything biologists told us for the last 150 years—that an intelligent agent helped shaped you and me.

He did use the correct word, "told", although the statement is false. "Told" is neither "convinced" nor "demonstrated". Even Dawkins admits life demonstrably appears designed, but he attributes that fact(thus showing both sides agree on the fact) to a "blind watchmaker". Somehow, a blind-folded chimp throwing paint at a canvas and allowed "do-overs" can create the "Mona Lisa".

[AndrewC]

The joke is on anybody who thinks it demonstrates anything.

But it does demonstrate something. It demonstrates that a human can buy a radiator cap drive a Rolls Royce under it and claim to have built a car.