Horizontal No Free Lunch Theorem

You keep using that word. I do not think it means what you think it means

Inigo Montoya


In their upcoming paper The Search for a Search: Measuring the Information Cost of Higher Level Search W. Dembski and R.Marks introduce a Horizontal No Free Lunch Theorem.

At Uncommon Descent, I tried to reach W. Dembski with the following post which is - of course - awaiting moderation at the moment.

The Horizontal No free Lunch Theorem doesn't work for a search of length m > 1 for a target T ⊆ Ω:

Let Ω be a finite search-space, T ⊆ Ω the target - a non-empty subset of Ω. A search is a (finite) sequence of Ω-valued random variables (φ₁, φ₂, ..., , φ_m). A search is successful, if φ_n ∈ T for one n, 1 ≤ n ≤ m.

I suppose we do agree here. Now, we look at a search Φ as a Ω^m-valued random variable, i.e., Φ := (φ₁, φ₂, ..., , φ_m).

When is it successful? If we are still looking for a T ⊆ Ω we can say that we found T during our search if

Φ ∈ Ω^m \ (Ω \ T)^m

Let's define Θ as the subspace of Ω^m which exists from the representations of targets in Ω, i.e.,

Θ := {Ω^m \ (Ω \ T)^m|T non-empty subset of Ω}

Obviously, Θ is much smaller than Ω^m.

But this Θ is the space of feasible targets. And if you take an exhaustive partition of Θ instead of Ω^m in Theorem III.1 Horizontal No Free Lunch, you'll find that you can indeed have positive values for the active entropy as defined in the same theorem.

But that's not much of a surprise, as random sampling without repetition works better than random sampling with repetition.

But if you allow T to be any subset of Ω^m, your results get somewhat trivial, as you are now looking at m independent searches of length 1 for different targets.

The searches which you state as examples in this paper and the previous one all work with a fixed target, i.e., elements of Θ. You never mention the possibility that the target changes between the steps of the search (one possible interpretation of taking arbitrary subsets of Ω^m into account).

So, I'm faced with two possibilities:

1. You didn't realize the switch from stationary targets to moving ones when you introduced searching for an arbitrary subset of Ω^m
2. You realized this switch to a very different concept, but chose not to stress the point.