Understanding the No Free Lunch Theorem 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? 


Optimal Ordered Problem Solver
No Free Lunch Theorem
You're asking about optimization and universal search, BUT machine-learning is tagged and you're wondering about "a uniform distribution on an infinite" discrete set so perhaps this will be helpful. There's a classic No-Free-Lunch result in PAC learning which says that you cannot learn the concept class of all boolean functions on the integers in a distribution-free fashion. Meaning: there is no function $m=m(\epsilon,\delta)$ such that if you request $m$ or more iid labeled examples from any unknown distribution, you'll be able to guarantee an $\epsilon$-accurate classifier with $\delta$-confidence. The proof proceeds by taking a uniform distribution over a large enough support size -- big enough to thwart any given purported sample complexity $m(\epsilon,\delta)$. A shorthand for saying this might be "take the uniform distribution over the integers". Now we all know that's absurd, and the explanation above is the only way I know to make sense out of it (and also jibes with the No-Free-Lunch context).