There are no free lunch theorems that show that no computable intelligences can perform well in all environments. As far as they go, these theorems are uninteresting, as we don't need intelligences that perform well in all environments, just in almost all/most.

They are also, in an important sense, false: the No Free Lunch theorem for statistical learning assumes that any underlying reality is as likely as any other (uniform distribution). Marcus Hutter published a paper years ago showing that when you make a simple Occam's Razor assumption, using the Solomonoff Measure over reality functions instead of a uniform distribution, you do, in fact, achieve a free lunch.

And of course, the Occam's Razor assumption is well-justified by the whole line of thought going from entropy in statistical mechanics through to both information-theoretic entropy and Kolmogorov complexity, viz: a simpler macrostate ("reality function" for classification/concept learning) can "be implemented by", emerge from, many microstates, so Occam's Razor and the Solomonoff Measure work in reductionist ontologies.