I came across the No Free Lunch Theorem via Jürgen Schmidhuber's paper on Universal Search and there were a couple remarks on NFL which stood out to me. The first was that we can't define a uniform distribution on an infinite number of objects. Second, Schmidhuber argues that there's nothing inherently natural about the uniform distribution and I'm inclined to agree on this point as well.
Although I'm aware of maximum-entropy arguments in favour of uniform distributions, on an infinite number of objects it's more natural to observe an exponential distribution. Might there be a well-known counter-argument in the optimisation literature to the points raised by Jürgen Schmidhuber?