Draft of a letter to JACIII

In their article The Search for a Search¹ the authors William Dembski and Robert Marks seem to assume that any search on a space induces a probability measure on the search space, as they write in section 3.1 (Active Information):

"Let U denote a uniform distribution on Ω characteristic of an unassisted search and φ the (nonuniform) measure of Ω for an assisted search. Let U(T) and φ(T) denote the probability over the target set T ∈_[sic]Ω."

Such an induced measure gives the probability to find a subset T of Ω when performing the corresponding search. But for the assisted searches mentioned in the text (a "perfect search" - "indicating an assisted search guaranteed to succeed" - and another search "indicating an assisted search guaranteed to fail"), such probability measures obviously do not exist! Thus these cases are not covered by their Theorem 1 (Horizontal No Free Lunch), as the Kullback-Leibler-distance is defined only for probability measures.

But perhaps the authors intended their theorem only to be valid for those searches which induce a measure on the search space - indeed, they use the term uninformed assisted searches when describing their results. Unfortunately, this term is not defined - neither in the current text, nor in their previous publications Conservation of Information in Search - Measuring the Cost of Success² or Efficient Per Query Information Extraction from a Hamming Oracle³.

Unfortunately, even in this case, the theorem does not work: assuming the easiest nontrivial case of guessing an element of a set with two elements (tossing a coin), Ω = {head, tail}, the two strategies naming an element at random (uniform distribution on $\backslash Omega\backslash ,$) and sticking with one element (dirac distribution) give the same success rate for a fair coin. The same result occurs when averaging over the probability of showing head (assuming that this probability is uniformly distributed on [0,1]), contradicting the statement of William Dembski and Robert Marks:

"Because the active entropy is strictly negative, any uninformed assisted search (φ) will on average perform worse than the baseline search". (Highlighting mine)

In my opinion, the fundamental problem stems from identifying the search space Ω_(n) and the space of (deterministic) searches. This is doubtless elegant, but does not seem to work.

References:

¹W. A. Dembski and R. J. Marks II, "The Search for a Search: Measuring the Information Cost of Higher Level Search," Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 14, No. 5, pp. 475-486, September 2010

²W. A. Dembski and R. J. Marks II, "Conservation of Information in Search: Measuring the Cost of Success," IEEE Trans. on Systems, Man and Cybernetics A, Systems and Humans, Vol. 39, No. 5, pp. 1051-1061, September 2009

³W. Ewert, G. Montanez, W. A. Dembski, and R. J. Marks II, "Efficient Per Query Information Extraction from a Hamming Oracle," Proc. of the 42nd Meeting of the Southeastern Symposium on System Theory, IEEE, University of Texas at Tyler, pp. 290-297, March 7-9, 2010