W. Dembski's and R. Marks's The Search for a Search and my major problem with it

William Dembski and Robert Marks announced a new paper The Search for a Search: Measuring the Information Cost of Higher Level Search (draft) which should appear in a peer-reviewed journal at any moment.

My problem: When I read the term search for a target without any qualifier, I imagine that

1. the target is fix
2. the search is over when the target is found the first time

A model for this: a game of Battleship against a random generator with this additional rules:

1. all ships are of size one
2. you don't know how many ships there are
3. the game is over with the first hit

So, if your search space is Ω then there are 2^|&Omega| - 1 different targets.

But with this kind of target, the math of W. Dembski's and R. Marks's paper doesn't work: They claim that you can't find a strategy for that works better on average than random search. In the Battleship example: there is no better strategy than shooting at random each turn until your first hit. But this is obviously wrong: A better strategy is not to hit a square twice.

But W. Dembski and R. Marks proved their claim - how so? Well, they redefined the concept of target. The altered rules for the Battleship:

1. the position and the number of the ships changes each round
2. to succeed, you have to hit a ship each round

For this version - and not for the one above - they proved all their results. The problem: That's not search as we now it...

The technical details: In section III, B, they formalize a search

Suppose now ­ Ω denotes an arbitrary search space. In general, assume ­Ω is a compact metric space with metric D, though for most theorems and calculations assume ­Ω is finite (in which case D is a discrete metric). Let X₁, X₂,...,X_n denote ­Ω-valued random variables that are independent and identically distributed with uniform probability distribution U. X₁, X₂,...,X_m therefore represents a blind search of ­Ω. Next, let Y₁, Y₂,...,Y_m denote ­Ω-valued random variables that are arbitrarily distributed. X₁, X₂,...,X_n therefore characterizes an assisted search of ­Ω.

That's our first version of Battleship - I've no problem with this section. But the next paragraph states

If we now let ­Ω^m denote the m-fold Cartesian product of Ω­, then X₁, X₂,...,X_m and Y₁, Y₂,...,Y_m are ­m-valued random variables. Because the uniform probability on ­­Ω^m is just the m-fold product measure of U, X₁, X₂,...,X_m) is uniformly distributed on
­ = Ω^m. Thus, by attending solely to the probabilistic
structure of searches, we represent the blind search := (X₁, X₂,...,X_m) as having a m-dimensional uniform distribution with respect to a metric D~ that suitably extends to the metric D on Ω­. Moreover, we represent the assisted search := (Y₁, Y₂,...,Y_m ), in searching for an arbitrary subset of , as having distribution on .
But all these tildes are superfluous. Dropping them, we see that the probabilistic connection between a blind search and an assisted search can be entirely characterized in terms of a search space ­, a metric D that induces a compact topology on ­Ω, a target T included
in ­Ω, a uniform probability measure U on ­ induced by D, and an arbitrary probability measure φ on ­Ω. U represents the probabilistic structure of a blind search, and φ represents the probabilistic structure of an assisted search.

Now, is a subset of Ω^m - and there are 2^{|Ω| m} -1 non-empty subsets! A successful search means that ∈ , i.e., Y_n ∈ T_n for all 1 ≤ n ≤ m. So, a stationary target would be not represented by

Tⁿ

as one may naively expect, but by

T×Ω×...×Ω
∪ Ω×T×Ω×...×Ω
∪ Ω×Ω×T×Ω×...×Ω
∪...
∪ &Omega×Ω×...×&Omega×T

but most of the targets don't fit this pattern.

Of course you can claim that knowing that you target doesn't move is additional information. But I haven't encountered a definition of search which expects you to be right on target each time...

P.S.: I tried to reach R. Marks via email - and I left an entry at W. Dembski's blog...

P.P.S.: some details.