Hmm, but here the set of possible world states would be the domain of the function we're optimising, not the function itself. Like, No-Free-Lunch states (from wikipedia):

Theorem 1: Given a finite set and a finite set $S$ of real numbers, assume that $f : S \to V$ is chosen at random according to uniform distribution on the set $S^{V}$ of all possible functions from $V$ to $S$ . For the problem of optimizing $f$ over the set $V$ , then no algorithm performs better than blind search.

Here $V$ is the set of possible world arrangements, which is admittedly much smaller than all possible data structures, but the theorem still holds because we're averaging over all possible value functions on this set of worlds, a set which is not physically restricted by anything.

I'd be very interested if you can find Byrnes' writeup.